Dlaczego jest znacząca różnica w tym C++ Dla czasu wykonania pętli? [duplikat]

Różnica w wydajności jest spowodowana strategią buforowania komputera.

Tablica dwuwymiarowa matrix[i][j] jest reprezentowana jako długa lista wartości w pamięci.

Np. tablica A[3][4] wygląda następująco:

1 1 1 1   2 2 2 2   3 3 3 3

W tym przykładzie każdy wpis [0] [x] jest ustawiony na 1, każdy wpis [1] [x] jest ustawiony na 2, ...

Jeśli pierwsza pętla zostanie zastosowana do tej macierzy, kolejność dostępu jest następująca:

1 2 3 4   5 6 7 8   9 10 11 12

Podczas gdy kolejność dostępu do drugiej pętli wygląda następująco to:

1 4 7 10  2 5 8 11  3 6 9 12

Gdy program uzyskuje dostęp do elementu tablicy, ładuje również kolejne elementy.

Np. jeśli uzyskasz dostęp A[0][1], A[0][2] i A[0][3] są też załadowane.

Dlatego pierwsza pętla musi wykonywać mniej operacji ładowania, ponieważ niektóre elementy są już w pamięci podręcznej, gdy są potrzebne. Druga pętla ładuje do pamięci podręcznej wpisy, które nie są potrzebne w tym czasie, powodując więcej operacji ładowania.

Inni ludzie wykonali dobrą robotę wyjaśniając, dlaczego jedna forma kodu sprawia, że bardziej efektywne wykorzystanie pamięci podręcznej niż druga. Chciałbym dodać kilka podstawowych informacji, których możesz nie być świadomy: prawdopodobnie nie zdajesz sobie sprawy , Jak drogie są obecnie dostępy do głównej pamięci.

Liczby zamieszczone w to pytanie wydaje mi się, że są we właściwym miejscu i zamierzam je tutaj odtworzyć, ponieważ są tak ważne:

Core i7 Xeon 5500 Series Data Source Latency (approximate)
L1 CACHE hit, ~4 cycles
L2 CACHE hit, ~10 cycles
L3 CACHE hit, line unshared ~40 cycles
L3 CACHE hit, shared line in another core ~65 cycles
L3 CACHE hit, modified in another core ~75 cycles remote
remote L3 CACHE ~100-300 cycles
Local Dram ~60 ns
Remote Dram ~100 ns

Zauważ zmianę w jednostkach do dwóch ostatnich wpisów. W zależności od tego, który model masz, ten procesor działa w 2.9-3.2 GHz; aby uprościć matematykę, nazwijmy to po prostu 3 GHz. Więc jeden cykl wynosi 0,33333 nanosekund. Tak więc dostęp do pamięci DRAM wynosi również 100-300 cykli.

Chodzi o to, że procesor mógł wykonać setkiInstrukcji w czasie potrzebnym do odczytania jednej linii pamięci podręcznej z pamięci głównej. Jest to tzw. ściana pamięci . Dzięki temu efektywne wykorzystanie pamięci pamięć podręczna jest ważniejsza niż jakikolwiek inny czynnik w ogólnej wydajności nowoczesnych procesorów.

Odpowiedź zależy trochę od tego, jak dokładnie matrix jest zdefiniowana. W tablicy w pełni dynamicznie przydzielanej, będziesz miał:

T **matrix;
matrix = new T*[n];
for(i = 0; i < n; i++)
{
   t[i] = new T[m]; 
}

Więc każdy matrix[j] będzie wymagał nowego wyszukiwania pamięci dla wskaźnika. Jeśli wykonasz pętlę j Na Zewnątrz, pętla wewnętrzna może ponownie użyć wskaźnika dla matrix[j] dla całej pętli wewnętrznej.

Jeśli macierz jest prostą macierzą 2D:

T matrix[n][m];

Wtedy {[3] } będzie po prostu mnożeniem przez 1024 * sizeof(T) - co można zrobić dodając 1024 * sizeof(T) indeks pętli w zoptymalizowanym kodzie, więc powinien być stosunkowo szybki w obu kierunkach.

Na dodatek, mamy Cache location factors. Pamięć podręczna ma "linie" danych, które są zwykle od 32 do 128 bajtów na linię. Więc jeśli twój kod odczytuje adres X, pamięć podręczna załaduje się z wartościami od 32 do 128 bajtów wokół X. Więc jeśli następną rzeczą, której potrzebujesz, jest tylko sizeof(T) do przodu z bieżącej lokalizacji, to najprawdopodobniej już w pamięci podręcznej [i nowoczesne procesory wykrywają również, że idziesz w pętla odczytuje każdą lokalizację pamięci i wstępnie ładuje dane].

W przypadku pętli wewnętrznej j odczytujemy nową lokalizację sizeof(T)*1024 odległości dla każdej pętli [lub możliwą większą odległość, jeśli jest przydzielana dynamicznie]. Oznacza to, że ładowane dane nie będą przydatne dla następnej pętli, ponieważ nie znajdują się w następnych 32 do 128 bajtów.

I wreszcie, jest całkowicie możliwe, że pierwsza pętla jest bardziej zoptymalizowana, dzięki instrukcjom SSE lub podobnym, które pozwalają obliczenia mają być jeszcze szybsze. Ale jest to prawdopodobnie marginalne dla tak dużej matrycy, ponieważ wydajność jest silnie związana z pamięcią przy tej wielkości.

[2]}sprzęt pamięci nie jest zoptymalizowany pod kątem dostarczania pojedynczych adresów: zamiast tego działa na większych kawałkach pamięci ciągłej zwanych liniami pamięci podręcznej . Za każdym razem, gdy czytasz jeden wpis swojej matrycy, cała linia pamięci podręcznej, w której leży, jest ładowana do pamięci podręcznej wraz z nią.

Szybsze porządkowanie pętli jest ustawione tak, aby odczytywać pamięć w kolejności; za każdym razem, gdy ładujesz linię pamięci podręcznej, używasz wszystkich wpisów w tej linii pamięci podręcznej. Każde przejście przez zewnętrzną pętlę, odczytujesz każdą macierz wejście tylko raz.

Wolniejsza kolejność pętli, jednak używa tylko jednego wpisu z każdej linii bufora przed przejściem dalej. Tak więc każda linia pamięci podręcznej musi być ładowana wielokrotnie, raz dla każdego wpisu macierzy w linii. na przykład jeśli double jest 8 bajtów, a linia pamięci podręcznej ma długość 64 bajtów, to każde przejście przez zewnętrzną pętlę musi odczytać każdy wpis macierzy osiem razy, a nie jeden raz.

Wszystko to powiedziawszy, gdybyś włączył optymalizacje, prawdopodobnie nie widzę różnicy: optymalizatory rozumieją to zjawisko, a dobrzy są w stanie rozpoznać, że mogą zamienić, która pętla jest pętlą wewnętrzną, a która jest pętlą zewnętrzną dla tego konkretnego fragmentu kodu.

(również dobry optymalizator zrobiłby tylko jedno przejście przez najbardziej zewnętrzną pętlę, ponieważ rozpoznaje pierwsze 999 razy przez są nieistotne dla końcowej wartości sum)

Macierz przechowywana jest w pamięci jako wektor. Dostęp do niej pierwszy sposób uzyskuje dostęp do pamięci sekwencyjnie. Dostęp do niego w drugą stronę wymaga przeskakiwania po miejscach pamięci. Zobacz http://en.wikipedia.org/wiki/Row-major_order

Jeśli uzyskasz dostęp do j - i wymiar j jest buforowany, więc kod maszynowy nie musi go zmieniać za każdym razem, drugi wymiar nie jest buforowany, więc faktycznie usuwasz bufor za każdym razem, co powoduje różnicę.

Bazując na koncepcji lokalizacji odniesienia, jest bardzo prawdopodobne, że fragment kodu ma dostęp do miejsc pamięci, które są obok siebie. Więc więcej wartości są ładowane do pamięci podręcznej niż to, co jest wymagane. Oznacza to więcej trafień pamięci podręcznej. Twój pierwszy przykład spełnia to dobrze, podczas gdy kod w drugim przykładzie nie jest.