Anpassa koden för cacheminnen

Ska redovisa en gammal labb-rest i en kurs i Datorteknik på fredag. Labben handlar om cacheminnen så jag är ganska insnöad på det ämnet just nu.

Något jag lärt mig av labben är att väldigt små skillnader i kod kan ge enorma skillnader i körtid. Jämför t.ex. dessa två olika sätt att addera två matriser:

for(j=0; j < MATRIX_SIZE; ++j){
   for(i=0; i < MATRIX_SIZE; ++i){
      res[i][j] = a[i][j]+b[i][j];
   }
}

for(i=0; i < MATRIX_SIZE; ++i){
   for(j=0; j < MATRIX_SIZE; ++j){
      res[i][j] = a[i][j]+b[i][j];
   }
}

Enda skillnaden här är att exempel 1 loopar igenom matriserna kolumn för kolumn medan man i exempel 2 går igenom matriserna rad för rad. Båda exemplen ger exakt samma resultat men exempel nummer 2 är överlägset snabbare med vissa cacheminnen. Detta beror på att matriser lagras radvis i RAM-minnet (enligt C-standarden och många andra språkdefinitioner). När ett program refererar till en variabel som inte finns i cacheminnet så hämtas variabeln in från RAM-minnet. Dessutom hämtas närliggande data in eftersom man förmodligen kommer vilja använda närliggande data. I exempel 2 tjänar man mycket på detta eftersom man där läser i den ordning som matriserna ligger lagrade och alltså förhoppningsvis får ganska många träffar efter varje miss. I exempel nummer 1 kan det extra datat som hämtats in ha hunnit skrivas över innan man får användning av det.

Jag kodade ett snabbt test i Java där jag adderar två matriser i storleken 1000x1000 på de två olika sätten. Här är exekveringstiderna:

radvis  kolumnvis
8.0ms   27.0ms
8.0ms   30.0ms
8.0ms   27.0ms
10.0ms  28.0ms
8.0ms   28.0ms
9.0ms   27.0ms
8.0ms   29.0ms
8.0ms   27.0ms
9.0ms   27.0ms
8.0ms   27.0ms
--------------------------------
8.4ms   27.7ms

Att loopa igenom matriserna radvis är alltså i snitt mer än 3 gånger så snabbt som att göra det kolumnvis.

För den som vill lära sig mer har KTH en omfattande PDF om Cacheminnen och adressöversättning.