Mikro-optimizacije

Ponekad je potrebno brzinu izvođenja programa dovesti do savršenstva, tu u igru upadaju mikro-optimizacije. Najvažnija optimizacija koju ćemo ovdje spomenuti jest ona koja pazi na to da program ne uzrokuje previše pogrešaka u zalihošću (engl. cache) procesora.

Naime, između radne memorije i procesora postoji sloj cache-a koji se brine da svaki put kada procesor zatraži pristup memoriji na nekom polju ne mora trošiti vrijeme ako smo relativno nedavno već čitali memoriju na bliskim poljima.

Taj cache sloj radi otprilike ovako, ako procesor odluči čitati memoriju na adresi X, memorija dostavi u neko spremište bliže procesoru vrijednost na adresi X, ali i neki broj okolnih vrijednosti također. Ako bi procesor u idućem koraku htio čitati X+1, moći će brže doći do podatka.

Kako se to odnosi na nas?

Primjer

Promatrajmo sljedeća dva programa:

int main() {
  int a[1000][1000], i, j, k;
  for (k = 0; k < 100; ++k)
    for (i = 0; i < 1000; ++i)
      for (j = 0; j < 1000; ++j)
        a[i][j] = i * j;
  return 0;
}
int main() {
  int a[1000][1000], i, j, k;
  for (k = 0; k < 100; ++k)
    for (i = 0; i < 1000; ++i)
      for (j = 0; j < 1000; ++j)
        a[j][i] = i * j;
  return 0;
}

Oba programa obave točno operacija što na modernom računalu traje otprilike 1 sekundu. No prvi program memoriju obilazi u redosljedu redaka, dok drugi program memoriju obilazi po stupcima. Što mislite kako se odnose vremena izvršavanja ovih programa?

Odgovor će možda biti začuđujuč:

$ time ./prvo_retci; time ./prvo_stupci
 
user    0m1.304s
 
user    0m7.448s

Vidimo da vrijeme izvršavanja drugog programa traje oko 5 puta više! user stoji za ukupno potrošeno vrijeme koje je potrošio procesor u korisničkom načinu rada. Vrijeme real za realno vrijeme poprima gotovo iste vrijednosti. Ovo mjerenje je pokrenuto nekoliko puta da bi odstranili mogućnost zauzimanja procesora od strane treće aplikacije.

Proučimo više ovaj efekt.

Dvodimenzionalno polje u jednodimenzionalnoj memoriji

Pošto je memorija računala jednodimenzionalna, tj. možemo je promatrati kao funkciju koja svakoj cjelobrojnoj adresi pridružuje neku vrijednost, programski jezik se mora pobrinuti da simulira ponašanja višedimenzionalnih polja.

C, ali i mnogi drugi jezici to rade ovako. Za 2D polje definirano kao:

int a[100][100];

Program će alocirati 10000 uzastopnih memorijskih adresa. U prvih 100 će staviti prvih redak ovog dvodimenzionalnog polja, u drugih 100 će staviti drugi redak, itd. Općenito vrijedi:

a[x][y] = a[x * 100 + y] = *(a + x * 100 + y);

Uzimajući u obzir informacije iz prvog poglavlja, možemo zaključiti da će obilaženje 2d polja biti mnogo efikasnije po retcima nego po stupcima:

a[0][5];
a[0][10];

Ove dvije instrukcije će vjerojatno zahtjevati jedan upit na memoriju stroja (jer će memorija odmah odgovoriti sa više uzastopnih adresa), dok će:

a[2][0];
a[7][0];

Morati komunicirati sa memorijom dvaput. I u ovom slučaju će memorija odgovoriti sa više vrijednosti odjednom, no udaljenosti između zahtjevanih adresa drugi puta su za red veličine veće nego udaljenosti između adresa prvi puta.

0 * 100 + 10, 0 * 100 + 5 = 10, 5 // razlika je 5
2 * 100 + 0, 7 * 100 + 0 = 200, 700 // razlika je 500

Simuliranje rada procesora koristeći valgrind

Pod linuxom postoji alat koji može potvrditi ovu teoriju simulirajući rad modernog procesora, a zove se http://valgrind.org/.

Pogledajmo statistike koje je prikupio ovaj alat za naša dva programa:

$ valgrind --tool=cachegrind --cache-sim=yes ./prvo_retci
==19494== Cachegrind, a cache and branch-prediction profiler
==19494== Copyright (C) 2002-2011, and GNU GPL'd, by Nicholas Nethercote et al.
==19494== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==19494== Command: ./prvo_retci
==19494== 
--19494-- warning: Pentium 4 with 12 KB micro-op instruction trace cache
--19494--          Simulating a 16 KB I-cache with 32 B lines
==19494== 
==19494== I   refs:      1,000,818,620
==19494== I1  misses:            1,138
==19494== LLi misses:              644
==19494== I1  miss rate:          0.00%
==19494== LLi miss rate:          0.00%
==19494== 
==19494== D   refs:        700,456,942  (600,339,967 rd   + 100,116,975 wr)
==19494== D1  misses:        6,251,503  (      1,308 rd   +   6,250,195 wr)
==19494== LLd misses:        6,251,053  (        898 rd   +   6,250,155 wr)
==19494== D1  miss rate:           0.8% (        0.0%     +         6.2%  )
==19494== LLd miss rate:           0.8% (        0.0%     +         6.2%  )
==19494== 
==19494== LL refs:           6,252,641  (      2,446 rd   +   6,250,195 wr)
==19494== LL misses:         6,251,697  (      1,542 rd   +   6,250,155 wr)
==19494== LL miss rate:            0.3% (        0.0%     +         6.2%  )
$ valgrind --tool=cachegrind --cache-sim=yes ./prvo_stupci
==19520== Cachegrind, a cache and branch-prediction profiler
==19520== Copyright (C) 2002-2011, and GNU GPL'd, by Nicholas Nethercote et al.
==19520== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==19520== Command: ./prvo_stupci
==19520== 
--19520-- warning: Pentium 4 with 12 KB micro-op instruction trace cache
--19520--          Simulating a 16 KB I-cache with 32 B lines
==19520== 
==19520== I   refs:      1,000,818,615
==19520== I1  misses:            1,139
==19520== LLi misses:              644
==19520== I1  miss rate:          0.00%
==19520== LLi miss rate:          0.00%
==19520== 
==19520== D   refs:        700,456,939  (600,339,964 rd   + 100,116,975 wr)
==19520== D1  misses:      100,000,415  (      1,308 rd   +  99,999,107 wr)
==19520== LLd misses:        6,252,063  (        898 rd   +   6,251,165 wr)
==19520== D1  miss rate:          14.2% (        0.0%     +        99.8%  )
==19520== LLd miss rate:           0.8% (        0.0%     +         6.2%  )
==19520== 
==19520== LL refs:         100,001,554  (      2,447 rd   +  99,999,107 wr)
==19520== LL misses:         6,252,707  (      1,542 rd   +   6,251,165 wr)
==19520== LL miss rate:            0.3% (        0.0%     +         6.2%  )

Glavne razlike se vide u broju D1 pogrešaka. D1 je skraćenica za data cache sloj 1. Osim podatkovnog cache-a postoji i cache za instrukcije, koji se zove I1. Noviji procesori mogu imati i po više slojeva cache-ova koji se tada zovu L1, L2, L3 (L kao layer). Svaki viši sloj je većeg kapaciteta i procesor može sporije doći do njega. Ako procesor naiđe na podatak u prvom sloju cache-a, može nastaviti sa radom u najkraćem roku.

Za detalje o gornjim skraćenicama više informacija moguće je naći na:

Općenite brzine dohvata podataka

Od najbržeg prema najsporijem.

Uglavnom je svaka nova stavka u ovoj listi za red veličine sporija od prethodne! Numbers Every Programmer Should now

Zaključak

Imajući u vidu sve gore navedeno, višedimenzionalna polja u svim programskim jezicima efikasnije je obilaziti 'po redovima'. Formalnije rečeno, bolje je vrijednosti nižih dimenzija mijenjati rjeđe.

© 2013. Anton Grbin Creative Commons License

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License