Poniżej znajdują się dwa programy, które są prawie identyczne, z wyjątkiem tego, że zmieniłem zmienne i
i 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; }
}
}
Odpowiedzi:
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:
Twój komputer przechowuje go w pamięci jako pojedynczy wiersz:
W drugim przykładzie uzyskujesz dostęp do tablicy, zapętlając najpierw drugi numer, tj .:
Oznacza to, że uderzasz je wszystkie po kolei. Teraz spójrz na pierwszą wersję. Robisz:
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 .:
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
źródło
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 .
źródło
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.
źródło
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.
źródło
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:
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 += 4000
nie 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 .źródło
p += 4000
isop++
i
jest już zwiększany o wartość niejednostkową, biorąc pod uwagę, że jest to przyrost wskaźnika.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.Oto linia winowajcy:
Druga wersja wykorzystuje pamięć ciągłą, dzięki czemu będzie znacznie szybsza.
Próbowałem z
a czas wykonania wynosi 13 s dla wersji 1 w porównaniu z 0,6 s dla wersji 2.
źródło
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ściarray_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_height
iteracje fragmentów, a pomiędzy dowolnymi iteracjami fragmentami będziesz miałarray_width
tylko iteracjesizeof(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.
źródło