Jaka jest różnica między „ nieprzyjaznym dla cache'u kodem ” a „ przyjaznym dla cache'a ” kodem?

Jak mogę się upewnić, że piszę kod efektywny dla pamięci podręcznej?

Czynności wstępne

Na współczesnych komputerach tylko struktury pamięci najniższego poziomu ( rejestry ) mogą przenosić dane w pojedynczych cyklach zegara. Rejestry są jednak bardzo drogie, a większość rdzeni komputerowych ma mniej niż kilkadziesiąt rejestrów ( łącznie od kilkuset do może tysiąca bajtów ). Na drugim końcu spektrum pamięci ( DRAM ) pamięć jest bardzo tania (tj. Dosłownie miliony razy tańsza ), ale zajmuje setki cykli po otrzymaniu danych. Aby wypełnić tę lukę między superszybkim i drogim a super wolnym i tanim, są pamięci podręczne, o nazwie L1, L2, L3 o malejącej prędkości i koszcie. Chodzi o to, że większość wykonywanego kodu często uderza w mały zestaw zmiennych, a reszta (znacznie większy zestaw zmiennych) rzadko. Jeśli procesor nie może znaleźć danych w pamięci podręcznej L1, wówczas szuka w pamięci podręcznej L2. Jeśli nie, to pamięć podręczna L3, a jeśli nie, pamięć główna. Każdy z tych „braków” jest z czasem drogi.

(Analogią jest pamięć podręczna pamięci systemowej, ponieważ pamięć systemowa jest zbyt dyskiem twardym. Dysk twardy jest super tani, ale bardzo wolny).

Buforowanie jest jedną z głównych metod zmniejszania wpływu opóźnienia . Parafrazując Herb Sutter (por. Linki poniżej): zwiększenie przepustowości jest łatwe, ale nie możemy kupić drogi wyjścia z opóźnień .

Dane są zawsze pobierane przez hierarchię pamięci (najmniejsze == najszybsze do najwolniejszych). Cache hit / Panna odnosi się zwykle do przeboju / brakuje w najwyższym poziomie w pamięci podręcznej procesora - o najwyższym poziomie to znaczy największa == najwolniej. Współczynnik trafień w pamięci podręcznej ma kluczowe znaczenie dla wydajności, ponieważ każde pominięcie pamięci podręcznej powoduje pobranie danych z pamięci RAM (lub gorzej ...), co zajmuje dużo czasu (setki cykli dla RAM, dziesiątki milionów cykli dla HDD). Dla porównania, odczyt danych z pamięci podręcznej (najwyższego poziomu) zwykle zajmuje tylko garść cykli.

We współczesnych architekturach komputerowych wąskim gardłem wydajności jest opuszczanie procesora (np. Uzyskiwanie dostępu do pamięci RAM lub wyższej). Z czasem sytuacja się pogorszy. Wzrost częstotliwości procesora nie jest obecnie istotny dla zwiększenia wydajności. Problemem jest dostęp do pamięci. W związku z tym wysiłki związane z projektowaniem sprzętu w procesorach koncentrują się obecnie na optymalizacji pamięci podręcznej, pobierania wstępnego, potoków i współbieżności. Na przykład nowoczesne procesory wydają około 85% pamięci na pamięci podręczne i do 99% na przechowywanie / przenoszenie danych!

Na ten temat można wiele powiedzieć. Oto kilka świetnych odniesień do pamięci podręcznych, hierarchii pamięci i właściwego programowania:

• Strona Agner Fog . W jego doskonałych dokumentach można znaleźć szczegółowe przykłady obejmujące języki, od asemblera po C ++.
• Jeśli lubisz filmy, zdecydowanie polecam zapoznanie się z wykładem Herb Suttera na temat architektury maszyn (youtube) (w szczególności sprawdź 12:00 i więcej!).
• Slajdy na temat optymalizacji pamięci autorstwa Christera Ericsona (dyrektor ds. Technologii @ Sony)
• Artykuł LWN.net „ Co każdy programista powinien wiedzieć o pamięci ”

Główne pojęcia dotyczące kodu przyjaznego dla pamięci podręcznej

Bardzo ważnym aspektem kodu przyjaznego dla pamięci podręcznej jest zasada lokalności , której celem jest umieszczenie powiązanych danych w pamięci, aby umożliwić efektywne buforowanie. Jeśli chodzi o pamięć podręczną procesora, należy pamiętać o liniach pamięci podręcznej, aby zrozumieć, jak to działa: Jak działają linie pamięci podręcznej?

Następujące szczególne aspekty mają duże znaczenie dla optymalizacji buforowania:

1. Lokalizacja czasowa : po uzyskaniu dostępu do danej lokalizacji w pamięci prawdopodobne jest, że w niedalekiej przyszłości ponownie będzie dostępna ta sama lokalizacja. W idealnym przypadku informacje te będą nadal buforowane w tym miejscu.
2. Lokalizacja przestrzenna : dotyczy to umieszczania powiązanych danych blisko siebie. Buforowanie odbywa się na wielu poziomach, nie tylko w procesorze. Na przykład, gdy czytasz z pamięci RAM, zwykle pobierana jest większa część pamięci niż ta, o którą konkretnie poprosiliśmy, ponieważ bardzo często program będzie wkrótce wymagał tych danych. Pamięci podręczne dysków twardych są zgodne z tą samą myślą. Szczególnie w przypadku pamięci podręcznych procesorów ważne jest pojęcie linii pamięci podręcznej .

Użyj odpowiedniego c ++ pojemniki

Prostym przykładem przyjaznych pamięci podręcznej i nieprzyjaznych pamięci podręcznej jest c ++w std::vectorporównaniu z std::list. Elementy a std::vectorsą przechowywane w ciągłej pamięci, dlatego dostęp do nich jest o wiele bardziej przyjazny dla pamięci podręcznej niż dostęp do elementów w a std::list, które przechowują jego zawartość w dowolnym miejscu. Wynika to z lokalizacji przestrzennej.

Bardzo ładną ilustracją tego jest Bjarne Stroustrup w tym klipie na youtube (dzięki @Mohammad Ali Baydoun za link!).

Nie zaniedbuj pamięci podręcznej w strukturze danych i projekcie algorytmu

W miarę możliwości staraj się dostosowywać struktury danych i kolejność obliczeń w taki sposób, aby maksymalnie wykorzystać pamięć podręczną. Powszechną techniką w tym zakresie jest blokowanie pamięci podręcznej (wersja Archive.org) , która ma ogromne znaczenie w obliczeniach o wysokiej wydajności (np. ATLAS ).

Znać i wykorzystywać ukrytą strukturę danych

Innym prostym przykładem, o którym wielu ludzi w tej dziedzinie czasami zapomina, jest kolumna główna (np. fortran,Matlab) a porządkowanie według rzędów (np. do,c ++) do przechowywania tablic dwuwymiarowych. Rozważmy na przykład następującą macierz:

1 2
3 4

W porządku rzędów głównych jest to przechowywane w pamięci jako 1 2 3 4; w uporządkowaniu według głównych kolumn byłoby to przechowywane jako 1 3 2 4. Łatwo zauważyć, że implementacje, które nie wykorzystują tego porządku, szybko napotkają (łatwo uniknąć!) Problemy z pamięcią podręczną. Niestety, widzę rzeczy, jak to bardzo często w mojej domeny (uczenia maszynowego). @MatteoItalia pokazał ten przykład bardziej szczegółowo w swojej odpowiedzi.

Podczas pobierania określonego elementu macierzy z pamięci elementy w jego pobliżu zostaną również pobrane i zapisane w linii pamięci podręcznej. Jeśli zostanie wykorzystana kolejność, spowoduje to mniejszy dostęp do pamięci (ponieważ kilka kolejnych wartości potrzebnych do kolejnych obliczeń znajduje się już w linii pamięci podręcznej).

Dla uproszczenia załóżmy, że pamięć podręczna zawiera pojedynczą linię pamięci podręcznej, która może zawierać 2 elementy macierzy i że gdy dany element jest pobierany z pamięci, następny też jest następny. Powiedzmy, że chcemy przejąć sumę nad wszystkimi elementami w powyższej przykładowej macierzy 2x2 (nazwijmy to M):

Wykorzystanie kolejności (np. Zmiana indeksu kolumny najpierw w c ++):

M[0][0] (memory) + M[0][1] (cached) + M[1][0] (memory) + M[1][1] (cached)
= 1 + 2 + 3 + 4
--> 2 cache hits, 2 memory accesses

Niewykorzystywanie kolejności (np. Zmiana indeksu wierszy najpierw w c ++):

M[0][0] (memory) + M[1][0] (memory) + M[0][1] (memory) + M[1][1] (memory)
= 1 + 3 + 2 + 4
--> 0 cache hits, 4 memory accesses

W tym prostym przykładzie wykorzystanie zamówienia w przybliżeniu podwaja szybkość wykonywania (ponieważ dostęp do pamięci wymaga znacznie więcej cykli niż obliczanie sum). W praktyce różnica wydajności może być znacznie większa.

Unikaj nieprzewidywalnych gałęzi

Nowoczesne architektury zawierają potoki, a kompilatory stają się bardzo dobre w zmianie kolejności kodu, aby zminimalizować opóźnienia z powodu dostępu do pamięci. Gdy kod krytyczny zawiera (nieprzewidywalne) gałęzie, pobranie danych jest trudne lub niemożliwe. To pośrednio doprowadzi do większej liczby braków w pamięci podręcznej.

Wyjaśnia to bardzo dobrze (dzięki @ 0x90 dla łącza): Dlaczego przetwarzanie posortowanej tablicy jest szybsze niż przetwarzanie nieposortowanej tablicy?

Unikaj funkcji wirtualnych

W kontekście c ++, virtualmetody stanowią kontrowersyjny problem z brakami pamięci podręcznej (istnieje ogólna zgoda, że ​​należy ich unikać, jeśli to możliwe, pod względem wydajności). Funkcje wirtualne mogą powodować brak pamięci podręcznej podczas wyszukiwania, ale dzieje się tak tylko wtedy, gdy konkretna funkcja nie jest często wywoływana (w przeciwnym razie prawdopodobnie byłaby buforowana), więc niektórzy uważają to za problem. Aby uzyskać informacje na temat tego problemu, sprawdź: Jaki jest koszt wydajności posiadania metody wirtualnej w klasie C ++?

Częste problemy

Częstym problemem we współczesnych architekturach z wieloprocesorowymi pamięciami podręcznymi jest fałszywe współdzielenie . Dzieje się tak, gdy każdy procesor próbuje użyć danych w innym regionie pamięci i próbuje zapisać je w tej samej linii pamięci podręcznej . Powoduje to, że wiersz pamięci podręcznej - który zawiera dane, których może użyć inny procesor - jest wielokrotnie zastępowany. W efekcie różne wątki zmuszają się do wzajemnego oczekiwania, powodując w tej sytuacji brak pamięci podręcznej. Zobacz także (dzięki @Matt za link): Jak i kiedy wyrównać do rozmiaru linii pamięci podręcznej?

Ekstremalnym objawem słabego buforowania w pamięci RAM (co prawdopodobnie nie jest tym, co masz na myśli w tym kontekście), jest tak zwane thrashowanie . Dzieje się tak, gdy proces w sposób ciągły generuje błędy strony (np. Uzyskuje dostęp do pamięci, której nie ma na bieżącej stronie), które wymagają dostępu do dysku.

Oprócz odpowiedzi @Marc Claesen uważam, że pouczającym klasycznym przykładem nieprzyjaznego dla pamięci podręcznej kodu jest kod, który skanuje tablicę dwuwymiarową C (np. Obraz bitmapowy) pod względem kolumny zamiast wiersza.

Elementy sąsiadujące w rzędzie również sąsiadują w pamięci, a zatem dostęp do nich w kolejności oznacza dostęp do nich w kolejności rosnącej; jest to przyjazne dla pamięci podręcznej, ponieważ pamięć podręczna ma tendencję do pobierania sąsiadujących bloków pamięci.

Zamiast tego dostęp do takich elementów pod względem kolumn jest nieprzyjazny dla pamięci podręcznej, ponieważ elementy w tej samej kolumnie są odległe od siebie w pamięci (w szczególności ich odległość jest równa wielkości wiersza), więc kiedy używasz tego wzorca dostępu, skaczą w pamięci, potencjalnie marnując wysiłek związany z pamięcią podręczną wyszukiwania elementów znajdujących się w pobliżu w pamięci.

I wszystko, czego potrzeba, aby zrujnować wydajność, to przejść

// Cache-friendly version - processes pixels which are adjacent in memory
for(unsigned int y=0; y<height; ++y)
{
    for(unsigned int x=0; x<width; ++x)
    {
        ... image[y][x] ...
    }
}

do

// Cache-unfriendly version - jumps around in memory for no good reason
for(unsigned int x=0; x<width; ++x)
{
    for(unsigned int y=0; y<height; ++y)
    {
        ... image[y][x] ...
    }
}

Efekt ten może być dość dramatyczny (kilka rzędów wielkości w prędkości) w systemach z małymi pamięciami podręcznymi i / lub pracą z dużymi macierzami (np. Ponad 10 megapikseli obrazów 24 bpp na obecnych maszynach); z tego powodu, jeśli musisz wykonać wiele skanów w pionie, często lepiej jest najpierw obrócić obraz o 90 stopni, a następnie wykonać różne analizy, ograniczając nieprzyjazny dla pamięci podręcznej kod tylko do obrotu.

Optymalizacja użycia pamięci podręcznej sprowadza się w dużej mierze do dwóch czynników.

Lokalizacja odniesienia

Pierwszym czynnikiem (do którego nawiązywali inni) jest lokalizacja odniesienia. Lokalizacja odniesienia ma jednak naprawdę dwa wymiary: przestrzeń i czas.

• Przestrzenny

Wymiar przestrzenny sprowadza się również do dwóch rzeczy: po pierwsze, chcemy gęsto upakować nasze informacje, aby więcej informacji zmieściło się w tej ograniczonej pamięci. Oznacza to (na przykład), że potrzebna jest znaczna poprawa złożoności obliczeniowej, aby uzasadnić struktury danych oparte na małych węzłach połączonych wskaźnikami.

Po drugie, chcemy, aby informacje, które będą przetwarzane razem, również były zlokalizowane razem. Typowa pamięć podręczna działa w „liniach”, co oznacza, że ​​gdy uzyskasz dostęp do niektórych informacji, inne informacje z pobliskich adresów zostaną załadowane do pamięci podręcznej wraz z dotkniętą częścią. Na przykład po dotknięciu jednego bajtu pamięć podręczna może załadować 128 lub 256 bajtów w pobliżu tego. Aby z tego skorzystać, zazwyczaj chcesz, aby dane były uporządkowane tak, aby zmaksymalizować prawdopodobieństwo, że użyjesz również innych danych, które zostały załadowane w tym samym czasie.

Na przykład bardzo trywialny przykład może to oznaczać, że wyszukiwanie liniowe może być znacznie bardziej konkurencyjne w przypadku wyszukiwania binarnego, niż można się spodziewać. Po załadowaniu jednego elementu z wiersza pamięci podręcznej korzystanie z reszty danych w tym wierszu pamięci podręcznej jest prawie bezpłatne. Wyszukiwanie binarne staje się zauważalnie szybsze tylko wtedy, gdy dane są na tyle duże, że wyszukiwanie binarne zmniejsza liczbę linii pamięci podręcznej, do których masz dostęp.

• Czas

Wymiar czasu oznacza, że ​​wykonując niektóre operacje na niektórych danych, chcesz (w jak największym stopniu) wykonywać wszystkie operacje na tych danych jednocześnie.

Odkąd określili to jako C ++, będę wskazywać na klasyczny przykład konstrukcji stosunkowo cache-nieprzyjazny: std::valarray. valarrayPrzeciążenia najbardziej arytmetyczne operatory, więc może (na przykład) powiedzieć a = b + c + d;(gdzie a, b, ci dsą valarrays) zrobić element mądry dodanie tych tablic.

Problem polega na tym, że przechodzi przez jedną parę danych wejściowych, umieszcza wyniki tymczasowo, przechodzi przez inną parę danych wejściowych i tak dalej. Przy dużej ilości danych wynik jednego obliczenia może zniknąć z pamięci podręcznej, zanim zostanie wykorzystany w następnym obliczeniu, więc kończymy odczytywanie (i zapisywanie) danych wielokrotnie, zanim uzyskamy końcowy wynik. Jeśli każdy element końcowy rezultat będzie coś takiego (a[n] + b[n]) * (c[n] + d[n]);, to na ogół wolą czytać każdy a[n], b[n], c[n]i d[n]raz, wykonać obliczenia, pisać rezultacie przyrost ni powtórzyć „til skończymy. ²⁾

Udostępnianie linii

Drugim ważnym czynnikiem jest unikanie dzielenia linii. Aby to zrozumieć, prawdopodobnie musimy wykonać kopię zapasową i przyjrzeć się trochę, w jaki sposób organizowane są pamięci podręczne. Najprostsza forma pamięci podręcznej jest mapowana bezpośrednio. Oznacza to, że jeden adres w pamięci głównej można zapisać tylko w jednym konkretnym miejscu w pamięci podręcznej. Jeśli używamy dwóch elementów danych, które są mapowane do tego samego miejsca w pamięci podręcznej, działa to źle - za każdym razem, gdy używamy jednego elementu danych, drugi musi zostać usunięty z pamięci podręcznej, aby zrobić miejsce dla drugiego. Reszta pamięci podręcznej może być pusta, ale te elementy nie będą używać innych części pamięci podręcznej.

Aby temu zapobiec, większość pamięci podręcznych to tak zwane „ustawianie asocjacyjne”. Na przykład w 4-kierunkowej pamięci podręcznej skojarzonej z zestawem dowolny element z pamięci głównej można przechowywać w dowolnym z 4 różnych miejsc w pamięci podręcznej. Kiedy więc pamięć podręczna ma załadować element, szuka ostatnio używanego ³ elementu spośród tych czterech, opróżnia go do pamięci głównej i ładuje nowy element na swoim miejscu.

Problem jest prawdopodobnie dość oczywisty: w przypadku pamięci podręcznej z bezpośrednim odwzorowaniem dwa operandy, które akurat mapują do tej samej lokalizacji pamięci podręcznej, mogą prowadzić do złego zachowania. Pamięć podręczna skojarzona z zestawem N-way zwiększa liczbę z 2 do N + 1. Zorganizowanie pamięci podręcznej na więcej „sposobów” wymaga dodatkowych obwodów i ogólnie działa wolniej, więc (na przykład) 8192-drogowe skojarzenie pamięci podręcznej rzadko jest dobrym rozwiązaniem.

Ostatecznie ten czynnik jest trudniejszy do kontrolowania w przenośnym kodzie. Twoja kontrola nad tym, gdzie znajdują się Twoje dane, jest zwykle dość ograniczona. Co gorsza, dokładne odwzorowanie adresu na pamięć podręczną różni się w zależności od podobnych procesorów. W niektórych przypadkach warto jednak wykonać takie czynności, jak przydzielenie dużego bufora, a następnie użycie tylko części tego, co zostało przydzielone, aby zabezpieczyć dane przed współużytkowaniem tych samych linii pamięci podręcznej (nawet jeśli prawdopodobnie konieczne będzie wykrycie dokładnego procesora i działaj odpowiednio, aby to zrobić).

• Fałszywe udostępnianie

Jest jeszcze jeden powiązany element zwany „fałszywym udostępnianiem”. Powstaje to w systemie wieloprocesorowym lub wielordzeniowym, w którym dwa (lub więcej) procesorów / rdzeni ma oddzielne dane, ale mieszczą się w tej samej linii pamięci podręcznej. Zmusza to dwa procesory / rdzenie do koordynowania dostępu do danych, nawet jeśli każdy ma swój własny, osobny element danych. Zwłaszcza, jeśli obydwoje modyfikują dane naprzemiennie, może to prowadzić do ogromnego spowolnienia, ponieważ dane muszą być stale przesyłane między procesorami. Nie można tego łatwo wyleczyć, organizując pamięć podręczną na więcej „sposobów” lub coś w tym rodzaju. Podstawowym sposobem zapobiegania temu jest zapewnienie, że dwa wątki rzadko (najlepiej nigdy) modyfikują dane, które mogą znajdować się w tej samej linii pamięci podręcznej (z tymi samymi zastrzeżeniami dotyczącymi trudności w kontrolowaniu adresów, pod którymi dane są przydzielane).

1. Ci, którzy dobrze znają C ++, mogą się zastanawiać, czy można to zoptymalizować za pomocą szablonów wyrażeń. Jestem prawie pewien, że odpowiedź brzmi: tak, można by to zrobić i gdyby tak było, prawdopodobnie byłaby to całkiem spora wygrana. Nie wiem jednak, że ktoś to zrobił, a biorąc pod uwagę, jak mało valarraysię przyzwyczaiłem, byłbym przynajmniej trochę zaskoczony, gdy ktoś to zrobił.

2. W przypadku, gdy ktoś zastanawia się, w jaki sposób valarray(zaprojektowany specjalnie pod kątem wydajności) może być tak bardzo źle, sprowadza się to do jednej rzeczy: został naprawdę zaprojektowany dla maszyn takich jak starsze Crays, które korzystały z szybkiej pamięci głównej i bez pamięci podręcznej. Dla nich był to naprawdę idealny projekt.

3. Tak, upraszczam: większość pamięci podręcznych tak naprawdę nie mierzy dokładnie ostatnio używanego przedmiotu, ale używa heurystyki, która ma być do tego zbliżona, bez konieczności zachowania pełnego znacznika czasu dla każdego dostępu.

Witamy w świecie projektowania zorientowanego na dane. Podstawową mantrą jest Sortowanie, Eliminowanie Oddziałów, Partia, Eliminowanie virtualpołączeń - wszystkie kroki w kierunku lepszej lokalizacji.

Ponieważ otagowałeś pytanie C ++, oto obowiązkowa typowa bzdura C ++ . Pułapki programowania obiektowego Tony'ego Albrechta to także świetne wprowadzenie do tematu.

Po prostu stos: klasyczny przykład kodu nieprzyjaznego dla pamięci podręcznej w porównaniu z kodem przyjaznym dla pamięci podręcznej to „blokowanie pamięci podręcznej” macierzy.

Naiwna macierz mnożenia wygląda następująco:

for(i=0;i<N;i++) {
   for(j=0;j<N;j++) {
      dest[i][j] = 0;
      for( k==;k<N;i++) {
         dest[i][j] += src1[i][k] * src2[k][j];
      }
   }
}

Jeśli Njest duży, np. Jeśli N * sizeof(elemType)jest większy niż rozmiar pamięci podręcznej, wówczas każdy pojedynczy dostęp do src2[k][j]będzie brakiem pamięci podręcznej.

Istnieje wiele różnych sposobów optymalizacji tego pod kątem pamięci podręcznej. Oto bardzo prosty przykład: zamiast czytać jeden element na linię pamięci podręcznej w wewnętrznej pętli, użyj wszystkich elementów:

int itemsPerCacheLine = CacheLineSize / sizeof(elemType);

for(i=0;i<N;i++) {
   for(j=0;j<N;j += itemsPerCacheLine ) {
      for(jj=0;jj<itemsPerCacheLine; jj+) {
         dest[i][j+jj] = 0;
      }
      for( k=0;k<N;k++) {
         for(jj=0;jj<itemsPerCacheLine; jj+) {
            dest[i][j+jj] += src1[i][k] * src2[k][j+jj];
         }
      }
   }
}

Jeśli rozmiar linii bufora wynosi 64 bajty, a działamy na liczbach zmiennoprzecinkowych 32-bitowych (4 bajty), wówczas w linii bufora jest 16 elementów. A liczba braków pamięci podręcznej dzięki tej prostej transformacji jest zmniejszona około 16-krotnie.

Bardziej zaawansowane transformacje działają na kafelkach 2D, optymalizują pod kątem wielu pamięci podręcznych (L1, L2, TLB) i tak dalej.

Niektóre wyniki „blokowania pamięci podręcznej” w Google:

http://stumptown.cc.gt.atl.ga.us/cse6230-hpcta-fa11/slides/11a-matmul-goto.pdf

http://software.intel.com/en-us/articles/cache-blocking-techniques

Ładna animacja wideo zoptymalizowanego algorytmu blokowania pamięci podręcznej.

http://www.youtube.com/watch?v=IFWgwGMMrh0

Układanie pętli jest bardzo ściśle powiązane:

http://en.wikipedia.org/wiki/Loop_tiling

Procesory współdziałają dziś z wieloma poziomami kaskadowych obszarów pamięci. Więc procesor będzie miał sporo pamięci, która znajduje się w samym układzie procesora. Ma bardzo szybki dostęp do tej pamięci. Istnieją różne poziomy pamięci podręcznej, z których każdy ma wolniejszy dostęp (i większy) niż następny, dopóki nie dojdziesz do pamięci systemowej, która nie jest na CPU i jest stosunkowo wolniejsza.

Logicznie, do zestawu instrukcji CPU odwołujesz się tylko do adresów pamięci w gigantycznej wirtualnej przestrzeni adresowej. Gdy uzyskasz dostęp do pojedynczego adresu pamięci, procesor go pobierze. w dawnych czasach pobierał tylko ten jeden adres. Ale dzisiaj procesor pobierze sporo pamięci wokół żądanego bitu i skopiuje go do pamięci podręcznej. Zakłada się, że jeśli poprosiłeś o określony adres, istnieje duże prawdopodobieństwo, że wkrótce poprosisz o adres w pobliżu. Na przykład, jeśli kopiujesz bufor, możesz czytać i pisać z kolejnych adresów - jeden bezpośrednio po drugim.

Więc dzisiaj, kiedy pobierasz adres, sprawdza on pierwszy poziom pamięci podręcznej, aby sprawdzić, czy już odczytał ten adres do pamięci podręcznej, jeśli go nie znajdzie, to jest to brak pamięci podręcznej i musi przejść do następnego poziomu pamięć podręczną, aby ją znaleźć, aż w końcu musi wyjść do pamięci głównej.

Kod przyjazny dla pamięci podręcznej stara się utrzymywać dostęp do pamięci blisko siebie, aby zminimalizować błędy pamięci podręcznej.

Przykładem może być wyobraźnia, że ​​chcesz skopiować gigantyczny 2-wymiarowy stół. Jest on uporządkowany z wierszem zasięgu w pamięci, a jeden wiersz następuje po drugim zaraz po.

Jeśli skopiowałeś elementy pojedynczo od lewej do prawej - byłoby to przyjazne dla pamięci podręcznej. Jeśli zdecydujesz się skopiować tabelę po jednej kolumnie na raz, skopiujesz dokładnie taką samą ilość pamięci - ale byłoby to nieprzyjazne dla pamięci podręcznej.

Należy wyjaśnić, że nie tylko dane powinny być przyjazne dla pamięci podręcznej, ale są równie ważne dla kodu. Jest to dodatek do przewidywania gałęzi, zmiany kolejności instrukcji, unikania faktycznych podziałów i innych technik.

Zazwyczaj im gęstszy kod, tym mniej linii pamięci podręcznej będzie wymaganych do jego przechowywania. Powoduje to, że dla danych dostępnych jest więcej wierszy pamięci podręcznej.

Kod nie powinien wywoływać funkcji w dowolnym miejscu, ponieważ zazwyczaj będą wymagały jednej lub więcej własnych linii pamięci podręcznej, co spowoduje zmniejszenie liczby linii pamięci podręcznej dla danych.

Funkcja powinna rozpoczynać się od adresu przyjaznego do wyrównania linii w pamięci podręcznej. Chociaż istnieją przełączniki kompilatora (gcc), należy pamiętać, że jeśli funkcje są bardzo krótkie, może być marnowanie czasu na zajęcie całej linii pamięci podręcznej. Na przykład, jeśli trzy z najczęściej używanych funkcji mieszczą się w jednej 64-bajtowej linii pamięci podręcznej, jest to mniej marnotrawstwo niż wtedy, gdy każda z nich ma swoją własną linię i powoduje, że dwie linie pamięci podręcznej są mniej dostępne do innych zastosowań. Typowa wartość wyrównania może wynosić 32 lub 16.

Poświęć więc trochę czasu na zagęszczenie kodu. Testuj różne konstrukcje, kompiluj i przeglądaj wygenerowany kod i rozmiar kodu.

Jak wspomniał @Marc Claesen, jednym ze sposobów pisania kodu przyjaznego dla pamięci podręcznej jest wykorzystanie struktury, w której przechowywane są nasze dane. Oprócz tego innym sposobem pisania przyjaznego dla pamięci podręcznej kodu jest: zmiana sposobu przechowywania danych; następnie napisz nowy kod, aby uzyskać dostęp do danych przechowywanych w tej nowej strukturze.

Ma to sens w przypadku, w jaki systemy baz danych linearyzują krotki tabeli i przechowują je. Istnieją dwa podstawowe sposoby przechowywania krotek tabeli, tj. Magazyn wierszy i magazyn kolumn. W magazynie wierszy, jak sama nazwa wskazuje, krotki są przechowywane w wierszach. Załóżmy, że tabela o nazwie, Productktóra jest przechowywana, ma 3 atrybuty, int32_t key, char name[56]a int32_t pricewięc całkowity rozmiar krotki to 64bajty.

Możemy symulować bardzo podstawowe wykonywanie zapytań magazynu wierszy w pamięci głównej, tworząc tablicę Productstruktur o rozmiarze N, gdzie N jest liczbą wierszy w tabeli. Taki układ pamięci nazywany jest również tablicą struktur. Struktura produktu może więc wyglądać następująco:

struct Product
{
   int32_t key;
   char name[56];
   int32_t price'
}

/* create an array of structs */
Product* table = new Product[N];
/* now load this array of structs, from a file etc. */

Podobnie możemy symulować bardzo podstawowe wykonanie zapytania do magazynu kolumn w pamięci głównej, tworząc 3 tablice o rozmiarze N, po jednej tablicy dla każdego atrybutu Producttabeli. Taki układ pamięci nazywany jest również strukturą tablic. Zatem 3 tablice dla każdego atrybutu produktu mogą wyglądać następująco:

/* create separate arrays for each attribute */
int32_t* key = new int32_t[N];
char* name = new char[56*N];
int32_t* price = new int32_t[N];
/* now load these arrays, from a file etc. */

Teraz po załadowaniu zarówno tablicy struktur (Układ wierszy), jak i 3 oddzielnych tablic (Układ kolumn), mamy Productw pamięci tabelę wierszy i kolumnę .

Teraz przechodzimy do części przyjaznej pamięci podręcznej. Załóżmy, że obciążenie naszego stołu jest takie, że mamy zapytanie agregacyjne dotyczące atrybutu ceny. Jak na przykład

SELECT SUM(price)
FROM PRODUCT

Dla magazynu wierszy możemy przekonwertować powyższe zapytanie SQL na

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + table[i].price;

Dla magazynu kolumn możemy przekonwertować powyższe zapytanie SQL na

int sum = 0;
for (int i=0; i<N; i++)
   sum = sum + price[i];

Kod dla magazynu kolumn byłby szybszy niż kod dla układu wierszy w tym zapytaniu, ponieważ wymaga tylko podzbioru atrybutów, a w układzie kolumn robimy tylko to, tj. Tylko dostęp do kolumny ceny.

Załóżmy, że rozmiar linii pamięci podręcznej to 64bajty.

W przypadku układu wiersza podczas odczytywania wiersza pamięci podręcznej odczytywana jest wartość ceny tylko 1 ( cacheline_size/product_struct_size = 64/64 = 1) krotki, ponieważ nasz strukturalny rozmiar wynosi 64 bajty i wypełnia całą naszą linię pamięci podręcznej, więc w przypadku każdej krotki brakuje pamięci podręcznej w przypadku układu wiersza.

W przypadku układu kolumny podczas odczytywania wiersza pamięci podręcznej odczytywana jest wartość ceny 16 ( cacheline_size/price_int_size = 64/4 = 16) krotek, ponieważ 16 ciągłych wartości cen przechowywanych w pamięci jest wprowadzanych do pamięci podręcznej, więc w przypadku każdej szesnastej krotki pamięć podręczna nie występuje w przypadku układ kolumny.

Tak więc układ kolumn będzie szybszy w przypadku danego zapytania i szybszy w takich zapytaniach agregacyjnych w podzbiorze kolumn tabeli. Możesz wypróbować taki eksperyment na własną rękę, korzystając z danych z testu porównawczego TPC-H i porównać czasy działania dla obu układów. Artykuł w Wikipedii na temat systemów baz danych zorientowanych na kolumny również jest dobry.

Tak więc w systemach baz danych, jeśli obciążenie kwerendą jest znane, możemy przechowywać nasze dane w układach, które będą pasować do zapytań w obciążeniu i uzyskać dostęp do danych z tych układów. W przypadku powyższego przykładu utworzyliśmy układ kolumny i zmieniliśmy nasz kod na obliczanie sumy, aby stał się przyjazny dla pamięci podręcznej.

Pamiętaj, że pamięci podręczne nie tylko buforują ciągłą pamięć. Mają wiele linii (co najmniej 4), więc nieciągła i nakładająca się pamięć często może być przechowywana równie skutecznie.

We wszystkich powyższych przykładach brakuje mierzonych wzorców. Istnieje wiele mitów na temat wydajności. Jeśli tego nie zmierzysz, nie wiesz. Nie komplikuj kodu, chyba że masz mierzoną poprawę.