Keskustelu: Ohjelmointikysymykset: Ulottuvuusjärjestys (C)

Onko taulukoiden lukemisjärjestyksellä mitään nopeuteen tai toimintaan vaikuttavaa etua? Esimerkiksi taulukko int kartta[y][x] on kaksiuloitteinen. Kannattako se lukea näin vai näin:

for (a = 0; a < 20; a++) {
  for (b = 0; b < 20; b++) {
    //if (kartta[a][b] == 'a') tms.
  }
}
// vai
for (a = 0; a < 20; a++) {
  for (b = 0; b < 20; b++) {
    //if (kartta[b][a] == 'a') tms.
  }
}

Jos näillä on suuri ero, niin miten suuri se on?

Yleensä taulukot järjestetään muistissa niin, että kaksiulotteinen taulukko muuttuu yksiulotteiseksi normaaliin lukusuuntaan:
11 12 13
21 22 23
=> 11 12 13 21 22 23

Tämän perusteella siis on kannattavampaa tehdä silmukka niin, että ensimmäinen indeksi on ulommassa silmukassa, kuten ensimmäisessä esimerkissäsi on. Tällöin peräkkäiset muistiosoitukset osoittavat peräkkäisiin muistipaikkoihin eivätkä kauas eri puolille muistia, jolloin prosessorin välimuistista on enemmän etua suurtenkin taulukoiden kanssa. Myös kääntäjä voi saada tilanteesta enemmän irti: jos koko taulukko käydään läpi, niin oikeastaan käydäänkin läpi vain suoraan peräkkäisiä muistipaikkoja, jolloin kääntäjä voi ehkä optimoida silmukkaa niin, ettei joka kierroksella tarvitse laskea uutta osoitetta vaan voidaan vain korottaa edellistä osoitetta yhdellä alkiolla.

Ero tulee ehkä merkittäväksi, jos kyseessä on todella iso taulukko (megatavuja) ja sitä oikeasti pyöritellään kovasti ympäri. Jos taulukko-operaatioihin kuitenkin kuluu vain joitakin millisekunteja, asialla ei ole mitään merkitystä. Lisäksi asiaan vaikuttaa tietenkin silmukan sisältö: jos operaatioita on paljon, ei ole juuri merkitystä, miten päin silmukka on, kun taas yksinkertaisessa silmukassa on suhteessa enemmän sitä silmukkaa kuin sisältöä.

Joskus testailin tätä. Yksinkertaisissa tapauksissa tuo eka vaihtoehto on noin 30-50% nopeampi kuin toka. Mutta ei kannata uskoa, sillä a) tosielämässä kaikki riippuu sitten kuitenkin kaikesta (eli mittaa oma tapauksesi itse) ja b) tämä luupitus ei ehkä kumminkaan ole se pullonkaula, joka tappaa koko ohjelman suorituskyvyn. Saattaa olla kannattavampaa keskittyä yleisemmän tason algoritmien ja tietorakenteiden viilaamiseen.