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

Poniżej znajdują się dwa programy, które są prawie identyczne, z wyjątkiem tego, że zmieniłem zmienne ii j. Oba działają w różnym czasie. Czy ktoś mógłby wyjaśnić, dlaczego tak się dzieje?

Wersja 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

Wersja 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}

Jak powiedzieli inni, problemem jest przechowywanie w pamięci w tablicy: x[i][j] . Oto trochę wglądu dlaczego:

Masz dwuwymiarowy układ, ale pamięć w komputerze jest z natury jednowymiarowa. Więc kiedy wyobrażasz sobie swoją tablicę w ten sposób:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

Twój komputer przechowuje go w pamięci jako pojedynczy wiersz:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

W drugim przykładzie uzyskujesz dostęp do tablicy, zapętlając najpierw drugi numer, tj .:

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

Oznacza to, że uderzasz je wszystkie po kolei. Teraz spójrz na pierwszą wersję. Robisz:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

Ze względu na sposób, w jaki C ułożył tablicę 2-d w pamięci, prosisz ją, aby skakała po całym miejscu. Ale teraz kicker: dlaczego to ma znaczenie? Wszystkie dostępy do pamięci są takie same, prawda?

Nie: z powodu pamięci podręcznych. Dane z pamięci są przenoszone do procesora w małych porcjach (zwanych „liniami pamięci podręcznej”), zwykle 64 bajtami. Jeśli masz 4-bajtowe liczby całkowite, oznacza to, że otrzymujesz 16 kolejnych liczb całkowitych w zgrabnym małym pakiecie. Pobieranie tych fragmentów pamięci jest dość powolne; Twój procesor może wykonać wiele pracy w czasie potrzebnym do załadowania pojedynczej linii pamięci podręcznej.

Spójrzmy teraz na kolejność dostępów: Drugi przykład to (1) chwytanie fragmentu 16 liczb wewnętrznych, (2) modyfikowanie ich wszystkich, (3) powtarzanie 4000 * 4000/16 razy. Jest to przyjemne i szybkie, a procesor zawsze ma coś do pracy.

Pierwszy przykład to (1) weź kawałek 16 liczb wewnętrznych, (2) zmodyfikuj tylko jedną z nich, (3) powtórz 4000 * 4000 razy. Będzie to wymagało 16-krotnej liczby „pobrań” z pamięci. Twój procesor będzie musiał spędzać czas, czekając, aż pojawi się ta pamięć, a gdy siedzisz, marnujesz cenny czas.

Ważna uwaga:

Teraz, gdy znasz odpowiedź, oto interesująca uwaga: nie ma nieodłącznego powodu, że twój drugi przykład musi być szybki. Na przykład w Fortranie pierwszy przykład byłby szybki, a drugi wolny. Wynika to z faktu, że zamiast rozszerzać elementy na koncepcyjne „wiersze”, podobnie jak C, Fortran rozwija się w „kolumny”, tj .:

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

Układ C nazywa się „major-row”, a Fortran nazywa się „major-kolumna”. Jak widać, bardzo ważne jest, aby wiedzieć, czy Twój język programowania jest dur-dur czy kolumna-dur! Oto link, aby uzyskać więcej informacji: http://en.wikipedia.org/wiki/Row-major_order

Nie ma nic wspólnego z montażem. Jest to spowodowane brakami pamięci podręcznej .

Tablice wielowymiarowe C są przechowywane z ostatnim wymiarem jako najszybszym. Tak więc pierwsza wersja będzie pomijać pamięć podręczną przy każdej iteracji, podczas gdy druga wersja nie. Druga wersja powinna być znacznie szybsza.

Zobacz także: http://en.wikipedia.org/wiki/Loop_interchange .

Wersja 2 będzie działać znacznie szybciej, ponieważ lepiej wykorzystuje pamięć podręczną komputera niż wersja 1. Jeśli się nad tym zastanowić, tablice to tylko ciągłe obszary pamięci. Gdy poprosisz o element w tablicy, Twój system operacyjny prawdopodobnie przyniesie stronę pamięci do pamięci podręcznej zawierającej ten element. Ponieważ jednak kilka kolejnych elementów znajduje się również na tej stronie (ponieważ są one ciągłe), następny dostęp będzie już w pamięci podręcznej! To właśnie robi wersja 2, aby przyspieszyć.

Z drugiej strony, wersja 1 ma dostęp do elementów pod względem kolumny, a nie wiersza. Ten rodzaj dostępu nie jest ciągły na poziomie pamięci, więc program nie może w tak dużym stopniu korzystać z buforowania systemu operacyjnego.

Przyczyną jest lokalny dostęp do pamięci podręcznej. W drugim programie skanujesz liniowo przez pamięć, która korzysta z buforowania i pobierania wstępnego. Wzorzec wykorzystania pamięci w pierwszym programie jest znacznie bardziej rozproszony 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 będzie prawdopodobnie zoptymalizowana przez kompilator w coś równoważnego do:

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

Jest to mniej prawdopodobne w przypadku pierwszej pętli, ponieważ musiałby za każdym razem zwiększać wskaźnik „p” o 4000.

EDYCJA: p++ a nawet *p++ = ..może być skompilowana do instrukcji jednego procesora w większości procesorów. *p = ..; p += 4000nie może, więc optymalizacja jest mniej korzystna. Jest to również trudniejsze, ponieważ kompilator musi znać rozmiar wewnętrznej tablicy i używać go. I nie zdarza się tak często w wewnętrznej pętli w normalnym kodzie (występuje tylko dla tablic wielowymiarowych, w których ostatni indeks jest utrzymywany na stałym poziomie w pętli, a od drugiego do ostatniego jest zwiększany), więc optymalizacja nie ma większego znaczenia .

Oto linia winowajcy:

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];

a czas wykonania wynosi 13 s dla wersji 1 w porównaniu z 0,6 s dla wersji 2.

_{Próbuję udzielić ogólnej odpowiedzi.}

Ponieważ i[y][x]to skrót od *(i + y*array_width + x)C (wypróbuj klasę int P[3]; 0[P] = 0xBEEF;).

Podczas iteracji y, iterujesz po kawałkach wielkości array_width * sizeof(array_element). Jeśli masz to w swojej wewnętrznej pętli, to będziesz miałarray_width * array_height iteracje nad tymi fragmentami.

Odwracając kolejność, będziesz mieć tylko array_heightiteracje fragmentów, a pomiędzy dowolnymi iteracjami fragmentami będziesz miał array_widthtylko iteracje sizeof(array_element).

Podczas gdy na naprawdę starych procesorach x86 nie miało to większego znaczenia, obecnie x86 często pobiera i buforuje dane. Prawdopodobnie generujesz wiele braków pamięci podręcznej w wolniejszej kolejności iteracji.