Oprócz odpowiedzi @ Marc Claesen, myślę, że klasycznym przykładem nieprzyjaznego kodu cache jest kod, który skanuje tablicę dwuwymiarową C (np. obraz bitmapowy) w kolumnach zamiast w wierszach.

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

Zamiast tego, dostęp do takich Elements column-wise jest Cache-nieprzyjazny, ponieważ elementy w tej samej kolumnie są odległe w pamięci od siebie (w szczególności, ich odległość jest równa wielkości wiersza), więc gdy używasz tego wzorca dostępu, przeskakujesz w pamięci, potencjalnie marnując wysiłek cache pobierania elementów znajdujących się w pobliżu pamięci.

I wszystko, co trzeba, aby zepsuć występ, to iść z

// 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 w systemach z małymi pamięciami podręcznymi i / lub pracujących z dużymi tablicami (np. 10 + megapikseli 24 obrazy bpp na obecnych maszynach); z tego powodu, jeśli trzeba wykonać wiele skanów pionowych, często lepiej najpierw obrócić obraz o 90 stopni, a później wykonać różne analizy, ograniczając nieprzyjazny dla pamięci podręcznej Kod tylko do obrotu.

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

Miejsce odniesienia

Pierwszym czynnikiem (do którego inni już nawiązali) jest lokalizacja odniesienia. Miejsce odniesienia ma jednak w rzeczywistości dwa wymiary: przestrzeń i czas.

• Spatial

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

Po drugie, chcemy informacji, które będą przetwarzane razem również 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 z częścią, której dotknęliśmy. Na przykład, gdy dotknę jednego bajtu, pamięć podręczna może załadować 128 lub 256 bajtów w pobliżu tego. Do wzięcia zaletą tego jest to, że zazwyczaj chcesz, aby dane były uporządkowane, aby zmaksymalizować prawdopodobieństwo, że będziesz używać również innych danych, które zostały załadowane w tym samym czasie.

Dla naprawdę trywialnego przykładu może to oznaczać, że wyszukiwanie liniowe może być znacznie bardziej konkurencyjne z wyszukiwaniem binarnym, niż można by się spodziewać. Po załadowaniu jednego elementu z linii pamięci podręcznej korzystanie z pozostałych danych w tej linii 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 gdy wykonujesz pewne operacje na niektórych danych, chcesz (jak najwięcej) wykonać wszystkie operacje na tych danych na raz.

Ponieważ otagowałeś to jako C++, wskażę klasyczny przykład stosunkowo nieprzyjaznego dla pamięci podręcznej projektu: std::valarray. valarray przeciąża większość operatorów arytmetycznych, więc mogę (na przykład) powiedzieć a = b + c + d; (Gdzie a, b, c oraz d są wszystkie valarrays), aby wykonać elementowe dodawanie tych tablic.

Problem polega na tym, że przechodzi przez jedną parę wejść, umieszcza wyniki w tymczasowym, przechodzi przez inną parę wejść i tak dalej. Przy dużej ilości danych wynik z jednego obliczenia może zniknąć z pamięci podręcznej, zanim zostanie użyty w następnym obliczeniu, więc kończymy wielokrotne czytanie (i zapisywanie) danych, zanim otrzymamy nasz końcowy wynik. Jeśli każdy element wyniku końcowego będzie czymś w rodzaju (a[n] + b[n]) * (c[n] + d[n]);, generalnie wolimy czytać każdy a[n], b[n], c[n] i d[n] raz, wykonaj obliczenia, napisz wynik, zwiększ n i powtarzaj, dopóki nie skończymy.²

Dzielenie Linii

Drugim ważnym czynnikiem jest unikanie dzielenia linii. Aby to zrozumieć, prawdopodobnie musimy wykonać kopię zapasową i przyjrzeć się trochę organizacji pamięci podręcznych. Najprostszą formą pamięci podręcznej jest mapowanie bezpośrednie. Oznacza to, że jeden adres w pamięci głównej może być przechowywany tylko w jednym konkretnym miejscu w pamięci podręcznej. Jeśli jesteśmy używanie dwóch pozycji danych, które mapują to samo miejsce w pamięci podręcznej, działa źle - za każdym razem, gdy używamy jednego elementu danych, drugi musi być wypłukany z pamięci podręcznej, aby zrobić miejsce dla drugiego. Reszta bufora może być pusta, ale te elementy nie będą używać innych części bufora.

Aby temu zapobiec, większość pamięci podręcznych nazywa się"zestawami asocjacyjnymi". Na przykład, w 4-way set-asocjacyjnym buforze, dowolny element z pamięci głównej może być przechowywany w dowolnym z 4 różnych miejsc w buforze. Więc, kiedy cache ładuje element, szuka ostatnio używanych³ element spośród tych czterech, spłukuje go do pamięci głównej i ładuje nowy element w jego miejsce.

Problem jest prawdopodobnie dość oczywisty: w przypadku pamięci podręcznej mapowanej bezpośrednio dwa operandy, które mapują tę samą lokalizację pamięci podręcznej, mogą prowadzić do złego zachowania. N-way set-asocjacyjny bufor zwiększa liczbę z 2 do n+1. Organizowanie pamięci podręcznej na więcej "sposobów" zajmuje dodatkowe obwody i generalnie działa wolniej, więc (dla przykład) asocjacyjny bufor zestawu 8192 rzadko jest dobrym rozwiązaniem.

Ostatecznie ten czynnik jest trudniejszy do kontrolowania w kodzie przenośnym. Twoja kontrola nad miejscem umieszczania danych jest zwykle dość ograniczona. Co gorsza, dokładne mapowanie z adresu do pamięci podręcznej różni się w zależności od podobnych procesorów. W niektórych przypadkach jednak warto zrobić takie rzeczy jak przydzielanie dużego bufora, a następnie używać tylko części tego, co przydzielono, aby zapewnić udostępnianie danych te same linie pamięci podręcznej (nawet jeśli prawdopodobnie będziesz musiał wykryć dokładny procesor i postępować zgodnie z tym).

• Fałszywe Dzielenie Się

Jest jeszcze jeden, powiązany element o nazwie "fałszywe dzielenie się". Powstaje to w systemie wieloprocesorowym lub wielordzeniowym, gdzie dwa (lub więcej) procesory / rdzenie mają dane, które są oddzielne, ale mieszczą się w tej samej linii pamięci podręcznej. Zmusza to dwa procesory/rdzenie do koordynowania dostępu do danych, mimo że każdy z nich ma własną, oddzielną pozycję danych. Zwłaszcza jeśli te dwa modyfikują dane na przemian, 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 stylu. Podstawowym sposobem zapobiegania temu jest zapewnienie, że dwa wątki rzadko (najlepiej nigdy) modyfikują dane, które mogłyby 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ą przydzielone).

1. Ci, którzy dobrze znają C++, mogą się zastanawiać, czy jest to otwarte na optymalizację za pomocą czegoś w rodzaju szablonów wyrażeń. Jestem pewien, że odpowiedź brzmi: tak, można to zrobić, a gdyby tak było, prawdopodobnie byłoby to dość znaczące zwycięstwo. Nie jestem jednak świadoma, że ktoś to zrobił, a biorąc pod uwagę, jak mało valarray jest używany, byłbym przynajmniej trochę zaskoczony, widząc kogoś, kto to robi.

2. Gdyby ktoś się zastanawiał jak valarray (zaprojektowany specjalnie dla wydajności) może być to bardzo źle, sprowadza się do jednej rzeczy: to było naprawdę zaprojektowane dla maszyn takich jak starsze kredki, które używały 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 nie mierzy dokładnie ostatnio używanego elementu, ale używa heurystyki, która ma być zbliżona do tego bez konieczności utrzymywania pełnego znacznika czasu dla każdego dostępu.

Witamy w świecie projektowania zorientowanego na dane. Podstawową mantrą jest sortowanie, eliminowanie gałęzi, partii, eliminowanie virtual połą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 są również świetnym wprowadzeniem do tematu.

Po prostu piling na: klasyczny przykład Cache-nieprzyjazny versus Cache-friendly kod jest "cache blocking" mnożenie macierzy.

Naiwne mnożenie macierzy wygląda jak

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 N jest duży, np. jeśli {[3] } jest większy niż rozmiar pamięci podręcznej, wtedy każdy dostęp do src2[k][j] będzie miss pamięci podręcznej.

Istnieje wiele różnych sposobów optymalizacji tego dla pamięci podręcznej. Oto bardzo prosty przykład: zamiast odczytu jednej pozycji na linię pamięci podręcznej w pętli wewnętrznej, użyj wszystkich items:

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==;k<N;i++) {
         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 operujemy na pływakach 32-bitowych( 4-bajtowych), to na linię bufora przypada 16 pozycji. A liczba braków pamięci podręcznej dzięki tej prostej transformacji jest zmniejszona około 16-krotnie.

Ekstrawaganckie transformacje działają na płytkach 2D, optymalizują dla wielu pamięci podręcznych (L1, L2, TLB) i tak dalej.

Niektóre wyniki googlowania " cache blokowanie": {]}

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 blisko powiązane:

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

Procesory pracują dziś z wieloma poziomami kaskadowych obszarów pamięci. Tak więc procesor będzie miał kilka pamięci, która znajduje się na samym chipie procesora. Ma bardzo szybki dostęp do tej pamięci. Istnieją różne poziomy pamięci podręcznej każdy z nich wolniejszy dostęp (i większy)niż następny, dopóki nie dojdziesz do pamięci systemowej, która nie jest na procesorze i jest stosunkowo dużo wolniejsza.

Logicznie rzecz biorąc, do zestawu instrukcji procesora odnosisz się tylko do adresów pamięci w gigantycznej wirtualnej przestrzeni adresowej. Kiedy ty dostęp do pojedynczego adresu pamięci procesor go pobierze. w dawnych czasach pobierał tylko ten jeden adres. Ale dzisiaj procesor pobierze trochę pamięci wokół bitu, o który prosiłeś, i skopiuje ją do pamięci podręcznej. Zakłada, że jeśli poprosiłeś o konkretny adres, który jest wysoce prawdopodobne, że wkrótce poprosisz o adres w pobliżu. Na przykład, jeśli kopiujesz bufor, czytasz i zapisujesz z następujących po sobie adresów-jeden po drugim.

Więc dzisiaj po pobraniu adresu 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 błąd pamięci podręcznej i musi przejść do następnego poziomu pamięci podręcznej, aby go znaleźć, aż w końcu musi wyjść do pamięci głównej.

Cache friendly code próbuje trzymać dostępy blisko siebie w pamięci, aby zminimalizować chybione pamięci podręcznej.

Przykładem może być wyobraź sobie, że chcesz skopiować gigantyczną dwuwymiarową tabelę. Organizowany jest z osiągnij wiersz w kolejnych w pamięci, a jeden wiersz po następnym zaraz po.

Jeśli skopiujesz elementy jeden wiersz na raz od lewej do prawej-będzie to przyjazne dla pamięci podręcznej. Jeśli zdecydujesz się skopiować tabelę jedną kolumną na raz, skopiujesz dokładnie taką samą ilość pamięci-ale byłaby to nieprzyjazna pamięć podręczna.

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 oprócz przewidywania gałęzi, zmiany kolejności instrukcji, unikania rzeczywistych podziałów i innych technik.

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

Kod nie powinien wywoływać funkcji w dowolnym miejscu, ponieważ zazwyczaj wymagają one jednego lub więcej pamięci podręcznej linie własne, co skutkuje mniejszą liczbą linii pamięci podręcznej dla danych.

Funkcja powinna zaczynać się od adresu przyjaznego dla wyrównania linii bufora. Chociaż istnieją przełączniki kompilatora (gcc) do tego należy pamiętać, że jeśli funkcje są bardzo krótkie, może to być marnotrawstwo dla każdej z nich, aby zająć całą linię pamięci podręcznej. Na przykład, jeśli trzy najczęściej używane funkcje mieszczą się w jednej 64-bajtowej linii pamięci podręcznej, jest to mniej marnotrawne niż Jeśli każda z nich ma 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.

Więc poświęć trochę czasu, aby Kod był gęsty. Testuj różne konstrukcje, Kompiluj i przeglądaj wygenerowany rozmiar kodu i profil.

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

Ma to sens w przypadku linearyzacji krotek tabeli przez systemy baz danych i ich przechowywania. Istnieją dwa podstawowe sposoby przechowywania krotek tabeli, np. i magazyn kolumnowy. W row store jak sama nazwa wskazuje krotki są przechowywane w row wise. Załóżmy, że przechowywana tabela o nazwie Product mA 3 atrybuty, tj. int32_t key, char name[56] i int32_t price, więc całkowity rozmiar krotki wynosi 64 bajty.

Możemy symulować bardzo podstawowe wykonywanie zapytań przechowujących wiersz w pamięci głównej, tworząc tablicę Product struktur o rozmiarze N, gdzie N jest liczbą wierszy w tabeli. Taki układ pamięci jest również nazywany tablicą struktur. Tak więc struktura produktu może być like:

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 wykonywanie zapytań przechowujących kolumny w pamięci głównej, tworząc 3 tablice o rozmiarze N, po jednej tablicy dla każdego atrybutu tabeli Product. Taki układ pamięci jest również nazywany strukturą tablic. Tak więc 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 row store i column store w naszej tabeli Product obecne w naszym pamięć.

Teraz przechodzimy do części kodu przyjaznego pamięci podręcznej. Załóżmy, że obciążenie naszej tabeli jest takie, że mamy zapytanie agregacyjne dotyczące atrybutu ceny. Takie jak

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 atrybuty i w układzie kolumn robimy właśnie to, czyli tylko dostęp do kolumny cen.

Załóżmy, że rozmiar linii bufora wynosi 64 bajty.

W przypadku układu wiersza, gdy odczytywana jest linia bufora, wartość ceny tylko 1 (cacheline_size/product_struct_size = 64/64 = 1) jest odczytywana krotka, ponieważ nasza struktura ma rozmiar 64 bajtów i wypełnia całą linię bufora, więc dla każdej krotki w przypadku układu wiersza następuje pominięcie bufora.

W przypadku układu kolumn podczas odczytu linii bufora, wartość ceny 16 (cacheline_size/price_int_size = 64/4 = 16) krotki są odczytywane, ponieważ 16 sąsiadujących ze sobą wartości cen przechowywanych w pamięci podręcznej są wprowadzane do pamięci podręcznej, więc dla każdej szesnastej krotki pamięć podręczna pomija ocurs w przypadku układu kolumn.

Tak więc układ kolumn będzie szybszy w przypadku danego zapytania i będzie szybszy w takich zapytaniach agregacyjnych na podzbiorze kolumn tabeli. Możesz wypróbować taki eksperyment samodzielnie, korzystając z danych z benchmarka TPC-H i porównać czasy uruchomienia dla obu układów. Na wikipedia artykuł o kolumnowych systemach bazodanowych jest również dobry.

Więc w systemach bazodanowych, jeśli obciążenie zapytań jest znane wcześniej, 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 stworzyliśmy układ kolumn i zmieniliśmy nasz kod na sumę obliczeniową tak, że stał się przyjazny dla pamięci podręcznej.

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

To czego brakuje we wszystkich powyższych przykładach to mierzone benchmarki. Istnieje wiele mitów na temat wydajności. Jeśli nie mierzysz, nie wiesz. Nie komplikuj kodu, chyba że masz zmierzoną poprawę.