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

360

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; }
   }
}
znak
źródło
26
en.wikipedia.org/wiki/…
Brendan Long
7
Czy możesz dodać jakieś wyniki testów?
naught101
3
Powiązane: stackoverflow.com/questions/9888154/...
Thomas Padron-McCarthy
14
@ naught101 Testy porównawcze pokażą różnicę wydajności w dowolnym miejscu od 3 do 10 razy. To jest podstawowa wersja C / C ++, jestem całkowicie zakłopotany tym, jak zdobyło tak wiele głosów ...
TC1
12
@ TC1: Nie sądzę, że to takie podstawowe; może pośredni. Nie powinno być jednak zaskoczeniem, że „podstawowe” rzeczy są przydatne dla większej liczby osób, stąd wiele pozytywnych opinii. Co więcej, to pytanie jest trudne do znalezienia w Google, nawet jeśli jest „podstawowe”.
LarsH

Odpowiedzi:

595

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

Robert Martin
źródło
14
To dość dokładna odpowiedź; tego nauczyłem się, gdy mam do czynienia z brakami pamięci podręcznej i zarządzaniem pamięcią.
Makoto
7
Masz „pierwszą” i „drugą” wersję w niewłaściwy sposób; pierwszy przykład zmienia pierwszy indeks w wewnętrznej pętli i będzie wolniejszym przykładem wykonania.
caf
Świetna odpowiedź. Jeśli Mark chce dowiedzieć się więcej o takich drobiazgach, poleciłbym książkę taką jak Write Great Code.
wkl
8
Punkty bonusowe za wskazanie, że C zmienił kolejność wierszy z Fortran. W przypadku obliczeń naukowych rozmiar pamięci podręcznej L2 jest wszystkim, ponieważ jeśli wszystkie tablice mieszczą się w L2, obliczenia można zakończyć bez przechodzenia do pamięci głównej.
Michael Shopsin
4
@ birryree: Dobrze dostępna lektura, którą każdy programista powinien wiedzieć o pamięci .
caf
68

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 .

Oliver Charlesworth
źródło
23

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.

Oleksi
źródło
Przy tych rozmiarach tablic prawdopodobnie odpowiedzialny jest tutaj menedżer pamięci podręcznej w CPU, a nie w systemie operacyjnym.
krlmlr
12

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.

Koder o zmiennej długości
źródło
11

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 .

fishinear
źródło
Nie rozumiem, co „bo musiałoby przeskoczyć wskaźnik„ p ”z 4000 za każdym razem”.
Veedrac
@ Veedrac Wskaźnik musiałby zostać zwiększony o 4000 wewnątrz wewnętrznej pętli: p += 4000isop++
fishinear
Dlaczego kompilator miałby taki problem? ijest już zwiększany o wartość niejednostkową, biorąc pod uwagę, że jest to przyrost wskaźnika.
Veedrac
Dodałem więcej wyjaśnień
fishinear
Spróbuj wpisać int *f(int *p) { *p++ = 10; return p; } int *g(int *p) { *p = 10; p += 4000; return p; }na gcc.godbolt.org . Oba wydają się kompilować w zasadzie tak samo.
Veedrac
7

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.

Nicolas Modrzyk
źródło
4

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.

Sebastian Mach
źródło