Dlaczego kolejność pętli wpływa na wydajność podczas iteracji na tablicy 2D?

Nic wspólnego z montażem. Jest to spowodowane pominięciem pamięci podręcznej .

C wielowymiarowe tablice są przechowywane z ostatnim wymiarem jako najszybszym. Tak więc pierwsza wersja będzie brakowało pamięci podręcznej na każdej iteracji, podczas gdy druga wersja nie będzie. więc druga wersja powinna być znacznie szybsza.

Zobacz też: http://en.wikipedia.org/wiki/Loop_interchange .

Wersja 2 będzie działać znacznie szybciej, ponieważ używa pamięci podręcznej komputera lepiej niż wersja 1. Jeśli się nad tym zastanowić, tablice są tylko sąsiadującymi ze sobą obszarami pamięci. Gdy zażądasz elementu w tablicy, Twój system operacyjny prawdopodobnie wprowadzi stronę pamięci do pamięci podręcznej, która zawiera ten element. Ponieważ jednak kilka kolejnych elementów znajduje się również na tej stronie (ponieważ sąsiadują ze sobą), następny dostęp będzie już w pamięci podręcznej! To właśnie robi Wersja 2, aby przyspieszyć.

Wersja 1, z drugiej strony, jest dostęp do elementów mądre kolumny, a nie mądry wiersz. Ten rodzaj dostępu nie jest sąsiadujący z poziomem pamięci, więc program nie może korzystać z buforowania systemu operacyjnego tak bardzo.

Powodem jest Cache-local data access. W drugim programie skanujesz liniowo przez pamięć, która korzysta z buforowania i wstępnego ustawiania. Wzorzec użycia pamięci pierwszego programu jest znacznie bardziej rozłożony i dlatego ma gorsze zachowanie pamięci podręcznej.

Oprócz innych doskonałych odpowiedzi na trafienia w pamięci podręcznej, istnieje również możliwa różnica w optymalizacji. Twoja druga pętla prawdopodobnie zostanie zoptymalizowana przez kompilator do czegoś równoważnego:

  for (j=0; j<4000; j++) {
    int *p = x[j];
    for (i=0; i<4000; i++) {
      *p++ = i+j;
    }
  }

Jest to mniej prawdopodobne dla pierwszej pętli, ponieważ musiałaby zwiększyć wskaźnik " p " O 4000 za każdym razem.

Edytuj: p++ i nawet *p++ = .. może być skompilowana do jednej instrukcji procesora w większości procesorów. *p = ..; p += 4000 nie może, więc jest mniej korzyści w jej optymalizacji. On również trudniejsze, ponieważ kompilator musi znać i używać rozmiaru tablicy wewnętrznej. I nie występuje tak często w pętli wewnętrznej w normalnym kodzie (występuje tylko dla tablic wielowymiarowych, gdzie ostatni indeks jest utrzymywany na stałym poziomie W pętli, a przedostatni jest schodkowany), więc optymalizacja jest mniej priorytetowa.

Ten wiersz winowajca:

x[j][i]=i+j;

Druga wersja wykorzystuje pamięć ciągłą, dzięki czemu będzie znacznie szybsza.

Próbowałem z

x[50000][50000];

I czas wykonania to 13s dla wersji1 vs 0.6 s dla wersji2.

_{staram się udzielić ogólnej odpowiedzi.}

Ponieważ i[y][x] jest skrótem *(i + y*array_width + x) W C (wypróbuj classy int P[3]; 0[P] = 0xBEEF;).

Kiedy iterację nad y, iterację nad kawałkami wielkości array_width * sizeof(array_element). Jeśli masz to w swojej wewnętrznej pętli, wtedy będziesz miał array_width * array_height iteracje nad tymi kawałkami.

Odwracając kolejność, będziesz miał tylko array_height iteracje chunk, a pomiędzy dowolną iteracją chunk, będziesz miał array_width iteracje tylko sizeof(array_element).

Podczas gdy na naprawdę starym x86-Procesory to nie miało większego znaczenia, w dzisiejszych czasach' x86 robi dużo wstępnego ustawiania i buforowania danych. Prawdopodobnie produkujesz wiele braków pamięci podręcznej w swojej wolniejszej kolejności iteracji.