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.