Keskustelu: Ohjelmointikysymykset: C: 2D-taulukko funktiolle

Olen joutunut viime viikkoina opiskelemaan C:tä opiskeluiden puolesta ja olen pohtinut, että kuinka kaksiulotteisen taulukon saa välitettyä funktiolle. Kuten moni varmasti tietääkin, että taulukot eivät ole C:ssä olioita, vaan taulukon nimi osoittaa sen ensimmäiseen alkioon ja loput alkiot ovatkin sitten ensimmäisen alkion jälkeen vierekkäin jne... Monien eri yritysten jälkeen sainkin kun sainkin välitettyä 2D-taulukon funktiolle pointtereiden avulla. Nyt lähinnä haluan teiltä hieman C:tä enemmän käyttäneiltä tietää, että onko tämä toteutukseni hyvä vai löytyykö jotain parempia vaihtoehtoja...

#include <stdio.h>
#include <stdlib.h>

void array_2d_func( int **array );

int main()
{
    int i;
    int nums[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } };
    int *temp[ 2 ];

    for (  i = 0; i < 2; i++ ) {
        temp[ i ] = nums[ i ];
    }

    array_2d_func( temp );

    system( "PAUSE" );
    return EXIT_SUCCESS;

}

void array_2d_func( int **array )
{
     int i, j;

     for ( i = 0; i < 2; i++ ) {
         for ( j = 0; j < 2; j++ ) {
             printf( "%d\n", array[ i ][ j ] );
         }
     }

}

Kaksiulotteinen taulukko tuolla tavalla määriteltynä ei ole suinkaan taulukollinen osoittimia (kuten dynaamisesti varattu taulukko olisi), joten sitä ei voi välittää noin. Ainoa tapa välittää kaksiulotteinen taulukko on kertoa funktiolle sen koko. Vain ensimmäisen dimension voi jättää kertomatta:

void array_2d_func(int array[2][4][6]);
void array_2d_func(int (*array)[4][6]); // int arr[123][4][6]

Yleisesti ottaen on käytännöllisempää toteuttaa moniulotteinen taulukko niin, että taulukko on yksiulotteinen ja indeksit lasketaan kaavalla x + leveys * y. Jos ulottuvuuksia tulee useampi, on helpointa tehdä struct, joka sisältää osoittimen ja dimensiot, jolloin ei tarvitse välittää funktioille kuin yksi parametri. Myös yllä mainitusta kaavasta voi tehdä funktion tai makron.

Eli se on siis tiedettävä jo funktiota määrittäessä, että minkä kokoinen (tai ainakin minkä korkuinen) taulukosta tulee... Tuohan on todella epäkäytännöllistä, sillä harvoin sitä tietää etukäteen, että minkä kokoinen taulukko on.

Voidaanko siis sanoa niin, että jos kyseessä olisi dynaamisesti varattu taulukko (jota tässä haen), niin tuo tekemäni koodi on ihan asiallinen? Olen nähnyt vastaavanlaisen konseptin (tosin hieman eri tarkoitukseen) eräässä C:tä käsittelevässä 90-luvun monisteessa, joten näin ollen voisi päätellä, etten ihan hakoteillä ole...

Kyllä, voisit siis käsitellä taulukkoa näin:

int d1 = 123, d2 = 456;
int** t;
int i;

t = malloc(sizeof(*t) * d1);
for (i = 0; i < d1; ++i) {
  t[i] = malloc(sizeof(**t) * d2);
}

t[1][2] = 3;

for (i = 0; i < d1; ++i) {
  free(t[i]);
}
free(t);

Tai vähemmillä malloceilla:

int d1 = 123, d2 = 456;
int** t;
int i;

t = malloc(sizeof(*t) * d1);
t[0] = malloc(sizeof(**t) * d1 * d2);
for (i = 1; i < d1; ++i) {
  t[i] = t[i-1] + d2;
}

t[1][2] = 3;

free(t[0]);
free(t);

Tuon voit helposti paketoida funktioiksi malloc_2d ja free_2d, jolloin ei puutu paljon muuta kuin tuo helppo alustuslista.

Lopuksi vielä se toinen vaihtoehto eli yksiulotteinen taulukko:

#define INDEX_2D(i1, i2, d1) ((i1) + (d1) * (i2))
int d1 = 123, d2 = 456;
int t[d1 * d2];

t[INDEX_2D(1, 2, d1)] = 3;

Tämä selvä. Kiitos.

Entäs sitten kumpi on tehokkaampaa taulukkoja läpi käydessä indeksit vai pointerit? Tuossa em. monisteessa sanottiin, että pointterit, mutta eräässä forumin threadissa väitettiin, ettei sillä ole suurempaa merkitystä. Kumpi siis on oikeassa tai ainakin lähempänä totuutta?

Ei merkitysta. Indeksit ovat lopulta pelkkaa syntaksia, jolla muistiosoite muodostetaan pointterin kautta. Dataan kiinni paasemiseksi muistiosoite tarvitaan joka tapauksessa. Joissain tapauksissa yhteen suuntaan iteroidessa pointterissa on se etu, ettei tarvita toista muuttujaa ollenkaan (ts. kasvatetaan pointteria). Siita ei kuitenkaan kannata huolehtia; turhaa mikro-optimointia, jolla todennakoisesti ei ole edes mitattavaa vaikutusta (satunnaistekijat vaikuttavat enemman).

Sen sijaan yksiulotteisen ja "kaksiulotteisen" taulukon valilla voi olla suurempia, jos jalkimmaisen rivit sijaitsevat eri paikoissa muistia, eika niita saada tehokkaasti etukateen haettua. Tastakaan ei tosin kannata huolehtia.

Ylipaansa suorituskykykysymyksiin paras vastaus on profilointi ja oikean algoritmin & tietorakenteen valinta.

Puhutko nyt siis edelleen "2D-taulukon" eli int**:n ja "1D-taulukon" eli int*:n erosta?

Teknisesti ajatellen 2D-tapauksessa pitää laskea indeksi, hakea muistista rivin osoitin, laskea toinen indeksi ja hakea riviltä arvo. Sen sijaan 1D-tapauksessa pitää laskea kertolasku, yhteenlasku ja indeksilasku ja hakea arvo. Niinpä 2D on hitaampi, koska muistioperaatiot ovat hitaita. Käytännössä ero voi olla lähes nolla, jos kääntäjä optimoi koodin oikein. Silti optimoinnista riippumatta riviltä seuraavalle siirtyminen vaatii 2D:ssä seuraavan rivin osoittimen hakemisen.

Ja varoituksen sana: vaikka jossain foorumilla ehkä neuvotaankin "tehokas" tapa käydä rivejä läpi vain yhtä pointteria kasvattamalla, todellisuudessa kääntäjä tuottaa yleensä vähintään yhtä hyvää koodia aivan tavallisella indeksoinnilla. Muista vain pitää vähintään -O2 tai vastaava optimointi käytössä.

jdc3nton, koodissasi on aika graavi bugi: et suinkaan laske alkioita yhteen, vaan lasket yhteen nmemb kertaa alkion, jota ei pitäisi ollakaan. Ei ihme, että kesti hetki tajuta, mitä Clang (kuten myös uusin GCC) suoltaa:

0000000000000000 <tabiter>:
   0:   85 f6                   test   %esi,%esi
   2:   7f 03                   jg     7 <tabiter+0x7>
   4:   31 c0                   xor    %eax,%eax
   6:   c3                      retq
   7:   48 63 c6                movslq %esi,%rax
   a:   0f af 04 87             imul   (%rdi,%rax,4),%eax
   e:   c3                      retq

Tässä nähdään sitä todellista optimointia: kääntäjä poisti silmukan ja laittoi tilalle kertolaskun!

Jos kuitenkin korjataan koodi niin, että silmukassa summataan tab[i], saadaan vähän toisenlainen tulos, jota en nyt viitsi tähän laittaa. Joka tapauksessa silmukka on niin hyvin optimoitu, että millään kikkailulla sitä ei saa nopeammaksi. Tällaisiin yksinkertaisiin on varmasti optimoijan suunnittelussa panostettukin.

En ymmärrä, mikä idea jdc3ntonin viestissä yleensäkään oli. Vaatii kohtalaista tietämystä konekielestä, ennen kuin tuosta pystyy sanomaan, onko kääntäjä optimoinut hyvin vai huonosti. (Ja kuten tässä nähtiin, minun kääntäjäni optimoi paremmin.)

Heh, joskus kay noin, kun arpoo palan merkityksetonta esimerkkikoodia kieli poskella. Enivei, mulla tuossa korjatussa versiossa ainut ero on movslq:ssa, joka ottaa indeksin edx:sta niin kuin kuuluu. Ja kuten nakyy, kaantajan ulosteessa on tuo indeksimuuttuja, jonka olisi voinut optimoida pois kokonaan. Mutta niin ei tehnyt :P

Hanki siis uudempi kääntäjä. :) Minulla silmukasta tulee paljon tiiviimpi, vain neljä riviä (sinulla kuusi):

  10:   03 07                   add    (%rdi),%eax
  12:   48 83 c7 04             add    $0x4,%rdi
  16:   48 ff c9                dec    %rcx
  19:   75 f5                   jne    10 <tabiter+0x10>