20 sierpnia 2008

Wierszami czy kolumnami? cz II.

Szybkość działania programu nie zależy wyłącznie od ilości wykonanych operacji. Na to czy program zadziała szybko ma wpływ wiele innych czynników. Dzisiaj poznamy jeden z nich.
Procesor posiada specjalną pamięć podręczną zwaną pamięcią cache. Jest ona o wiele szybsza od pamięci RAM. Gdy procesor potrzebuje jakiś danych to najpierw sprawdza czy są one dostępne w pamięci cache. Jeśli tak to świetnie! Dostaniemy do nich dostęp bardzo szybko. Jeśli nie - dostęp do tych danych potrwa nieco dłużej. Często będzie nam zależeć na tym, aby ten drugi przypadek starać się wykluczyć.
Procesor stara się przewidzieć jakie dane będą potrzebne w najbliższej przyszłości. Dwa podstawowe warunki jakimi sugeruje się procesor to:
  • Jeśli jakiś obiekt był ostatnio używany, to istnieje duże prawdopodobieństwo, że będzie używany w najbliższej przyszłości
  • Jeśli jakiś obiekt był ostatnio używany, to istnieje duże prawdopodobieństwo, że w najbliższej przyszłości będą używane obiekty leżące blisko niego
Jako elementy "blisko niego" rozumiemy tutaj elementy, które znajdują się koło niego w pamięci RAM (mają podobny adres maszynowy). Zadeklarujmy tablicę dwuwymiarową i sprawdźmy które elementy znajdują się koło których w pamięci. Podejrzewamy, że bezpośrednio koło elementu T[0][0] znajduje się albo element T[0][1], albo T[1][0]. Poniższy program rozwieje nasze wątpliwości.
const int N = 1000;
static char T[N][N];

printf("0x%08x\n0x%08x\n0x%08x\n0x%08x\n",
&T[0][0], &T[0][1], &T[1][0], &T[0][N-1]);

Po uruchomieniu programu dostałem następujące wyniki (zachęcam do uruchomienia programu na własnym sprzęcie):
0x00404040
0x00404041
0x00404428
0x00404427

Zatem koło adresu T[0][0] znajduje się element T[0][1]. Natomiast element T[1][0] znajduje się o 1000 adresów dalej. Zachęcam do dalszych eksperymentów, w których wykażemy, że koło elementu T[0][1] znajduje się element T[0][2] itd.
Po analizie naszego programu możemy wywnioskować również, że w pamięci po elemencie T[0][N-1] występuje element T[1][0]. Najlepiej iterować tablicę dwuwymiarową w kolejności występowania elementów w pamięci - czyli w kolejności: T[0][0], T[0][1], ..., T[0][N-1], T[1][0], ..., T[N-1][N-1].
Wyjaśniło się nam zatem dlaczego algorytm iterujący po wierszach działa szybciej niż program iterujący po kolumnach. Starajmy się iterować w ten sposób tablice wielowymiarowe zawsze wtedy, kiedy mamy taką możliwość!
W następnej notce przedstawię często spotykany algorytm, w którym stosując poznaną tu sztuczkę zwiększymy szybkość jego działania o kilka sekund.

Brak komentarzy: