To może brzmieć jak subiektywne pytanie, ale szukam konkretnych przypadków, z którymi mogłeś się spotkać w związku z tym.
Jak sprawić, by kod był efektywny w pamięci podręcznej / przyjazny dla pamięci podręcznej (więcej trafień w pamięci podręcznej, jak najmniej braków w pamięci podręcznej)? Z obu perspektyw, pamięć podręczna danych i pamięć podręczna programu (pamięć podręczna instrukcji), czyli jakie rzeczy w kodzie, związane ze strukturami danych i konstrukcjami kodu, należy zadbać, aby pamięć podręczna była efektywna.
Czy istnieją jakieś szczególne struktury danych, których należy używać / unikać, czy też istnieje określony sposób uzyskiwania dostępu do elementów tej struktury itp., Aby pamięć podręczna kodu była efektywna.
Czy są jakieś konstrukcje programu (if, for, switch, break, goto, ...), code-flow (wewnątrz if, if inside a for, etc ...), których należy przestrzegać / unikać w tej sprawie?
Z niecierpliwością czekam na indywidualne doświadczenia związane z generowaniem wydajnego kodu pamięci podręcznej. Może to być dowolny język programowania (C, C ++, Assembly, ...), dowolny cel sprzętowy (ARM, Intel, PowerPC, ...), dowolny system operacyjny (Windows, Linux, S ymbian, ...) itp. .
Różnorodność pomoże lepiej ją głębiej zrozumieć.
źródło
Odpowiedzi:
Pamięć podręczna ma na celu zmniejszenie liczby przypadków, w których procesor zatrzymałby się w oczekiwaniu na wypełnienie żądania pamięci (unikając opóźnienia pamięci ), a jako drugi efekt, prawdopodobnie w celu zmniejszenia całkowitej ilości danych, które muszą być przesłane (zachowując przepustowość pamięci ).
Techniki unikania opóźnień w pobieraniu pamięci są zazwyczaj pierwszą rzeczą do rozważenia i czasami pomagają na dłuższą metę. Ograniczona przepustowość pamięci jest również czynnikiem ograniczającym, szczególnie w przypadku wielordzeniowych i wielowątkowych aplikacji, w których wiele wątków chce używać magistrali pamięci. Inny zestaw technik pomaga rozwiązać ten ostatni problem.
Poprawa lokalności przestrzennej oznacza, że każda linia pamięci podręcznej jest używana w całości po zmapowaniu jej do pamięci podręcznej. Kiedy przyjrzeliśmy się różnym standardowym testom porównawczym, zauważyliśmy, że zaskakująco duża część z nich nie wykorzystuje 100% pobranych wierszy pamięci podręcznej, zanim wiersze pamięci podręcznej zostaną eksmitowane.
Poprawa wykorzystania linii pamięci podręcznej pomaga w trzech aspektach:
Typowe techniki to:
Powinniśmy również zauważyć, że istnieją inne sposoby ukrywania opóźnień pamięci niż używanie pamięci podręcznych.
Nowoczesne procesory często mają jeden lub więcej sprzętowych modułów wstępnych . Trenują na chybieniach w skrytce i próbują dostrzec prawidłowości. Na przykład, po kilku chybieniach w kolejnych wierszach pamięci podręcznej, moduł wstępnego pobierania hw rozpocznie pobieranie wierszy pamięci podręcznej do pamięci podręcznej, przewidując potrzeby aplikacji. Jeśli masz regularny wzorzec dostępu, sprzętowy moduł wstępnego pobierania zwykle wykonuje bardzo dobrą robotę. A jeśli twój program nie wyświetla regularnych wzorców dostępu, możesz poprawić rzeczy, dodając samodzielnie instrukcje pobierania wstępnego .
Instrukcje przegrupowania w taki sposób, że te, które zawsze są pomijane w pamięci podręcznej, występują blisko siebie, procesor może czasami nakładać się na te pobrania, tak że aplikacja może wytrzymać tylko jedno uderzenie w opóźnienie ( równoległość poziomu pamięci ).
Aby zmniejszyć ogólne obciążenie magistrali pamięci, musisz zacząć zajmować się tym, co nazywa się lokalnością czasową . Oznacza to, że musisz ponownie wykorzystać dane, dopóki nie zostały one usunięte z pamięci podręcznej.
Łączenie pętli, które dotykają tych samych danych ( fuzja pętli ) i stosowanie technik przepisywania znanych jako kafelkowanie lub blokowanie, ma na celu uniknięcie tych dodatkowych pobrań pamięci.
Chociaż istnieją pewne praktyczne zasady dotyczące tego ćwiczenia przepisywania, zwykle trzeba dokładnie rozważyć zależności danych przenoszonych w pętli, aby upewnić się, że nie wpłynie to na semantykę programu.
Są to rzeczy, które naprawdę się opłaca w świecie wielordzeniowym, w którym zazwyczaj nie widać dużej poprawy przepustowości po dodaniu drugiego wątku.
źródło
Nie mogę uwierzyć, że nie ma więcej odpowiedzi na to. W każdym razie jednym z klasycznych przykładów jest iteracja wielowymiarowej tablicy „na lewą stronę”:
Przyczyną tego, że pamięć podręczna jest nieefektywna, jest to, że nowoczesne procesory ładują linię pamięci podręcznej „bliskimi” adresami pamięci z pamięci głównej, gdy uzyskujesz dostęp do pojedynczego adresu pamięci. Przechodzimy przez wiersze „j” (zewnętrzne) w tablicy w pętli wewnętrznej, więc przy każdym przejściu przez pętlę wewnętrzną wiersz pamięci podręcznej spowoduje opróżnienie i załadowanie linią adresów, które są bliskie [ j] [i] wpis. Jeśli zostanie to zmienione na odpowiednik:
Będzie działać znacznie szybciej.
źródło
Podstawowe zasady są w rzeczywistości dość proste. Problematyczne jest to, jak stosują się do Twojego kodu.
Pamięć podręczna działa na dwóch zasadach: lokalności czasowej i lokalności przestrzennej. Pierwsza z nich polega na tym, że jeśli niedawno użyłeś określonej porcji danych, prawdopodobnie wkrótce będziesz jej ponownie potrzebować. To ostatnie oznacza, że jeśli ostatnio używałeś danych pod adresem X, prawdopodobnie wkrótce będziesz potrzebować adresu X + 1.
Pamięć podręczna próbuje to uwzględnić, zapamiętując ostatnio używane fragmenty danych. Działa z liniami pamięci podręcznej, zwykle o rozmiarze 128 bajtów, więc nawet jeśli potrzebujesz tylko jednego bajtu, cała linia pamięci podręcznej, która go zawiera, zostanie wciągnięta do pamięci podręcznej. Więc jeśli później będziesz potrzebować następującego bajtu, będzie on już w pamięci podręcznej.
A to oznacza, że zawsze będziesz chciał, aby Twój własny kod wykorzystywał te dwie formy lokalności w jak największym stopniu. Nie przeskakuj całej pamięci. Wykonuj tyle pracy, ile możesz na jednym małym obszarze, a następnie przejdź do następnego i wykonaj tam tyle pracy, ile możesz.
Prostym przykładem jest przechodzenie przez tablicę 2D, które pokazała odpowiedź z 1800 roku. Jeśli przechodzisz przez wiersz na raz, czytasz pamięć sekwencyjnie. Jeśli zrobisz to na podstawie kolumn, przeczytasz jeden wpis, a następnie przeskoczysz do zupełnie innej lokalizacji (początek następnego wiersza), przeczytasz jeden wpis i skoczysz ponownie. A kiedy w końcu wrócisz do pierwszego wiersza, nie będzie go już w pamięci podręcznej.
To samo dotyczy kodu. Skoki lub rozgałęzienia oznaczają mniej wydajne wykorzystanie pamięci podręcznej (ponieważ nie czytasz instrukcji po kolei, ale skaczesz na inny adres). Oczywiście małe instrukcje if prawdopodobnie niczego nie zmienią (pomijasz tylko kilka bajtów, więc nadal znajdziesz się w obszarze pamięci podręcznej), ale wywołania funkcji zwykle sugerują, że skaczesz do zupełnie innego adres, który nie może być zapisany w pamięci podręcznej. Chyba że został ostatnio wywołany.
Jednak użycie pamięci podręcznej instrukcji jest zwykle znacznie mniejszym problemem. To, o co zwykle musisz się martwić, to pamięć podręczna danych.
W strukturze lub klasie wszystkie składowe są rozmieszczone w sposób ciągły, co jest dobre. W tablicy wszystkie wpisy są również ułożone w sposób ciągły. Na listach połączonych każdy węzeł jest przydzielany w zupełnie innej lokalizacji, co jest złe. Wskaźniki na ogół wskazują na niepowiązane adresy, co prawdopodobnie spowoduje pominięcie pamięci podręcznej, jeśli ją wyłuskujesz.
A jeśli chcesz wykorzystać wiele rdzeni, może to być naprawdę interesujące, jak zwykle tylko jeden procesor może mieć dany adres w swojej pamięci podręcznej L1 na raz. Więc jeśli oba rdzenie stale uzyskują dostęp do tego samego adresu, spowoduje to ciągłe chybienia pamięci podręcznej, ponieważ walczą o adres.
źródło
Polecam przeczytanie 9-częściowego artykułu Ulricha Dreppera Co każdy programista powinien wiedzieć o pamięci , jeśli interesuje Cię interakcja pamięci i oprogramowania. Jest również dostępny jako 104-stronicowy plik PDF .
Sekcjami szczególnie istotnymi dla tego pytania mogą być Część 2 (pamięci podręczne procesora) i Część 5 (Co mogą zrobić programiści - optymalizacja pamięci podręcznej).
źródło
Oprócz wzorców dostępu do danych, głównym czynnikiem w kodzie przyjaznym dla pamięci podręcznej jest rozmiar danych . Mniej danych oznacza, że więcej mieści się w pamięci podręcznej.
Jest to głównie czynnik związany ze strukturami danych wyrównanymi do pamięci. „Konwencjonalna” mądrość mówi, że struktury danych muszą być wyrównane na granicach słów, ponieważ procesor ma dostęp tylko do całych słów, a jeśli słowo zawiera więcej niż jedną wartość, musisz wykonać dodatkową pracę (odczyt-modyfikacja-zapis zamiast prostego zapisu) . Ale pamięci podręczne mogą całkowicie unieważnić ten argument.
Podobnie tablica logiczna Java wykorzystuje cały bajt dla każdej wartości, aby umożliwić bezpośrednie działanie na poszczególnych wartościach. Możesz zmniejszyć rozmiar danych o współczynnik 8, jeśli używasz rzeczywistych bitów, ale wtedy dostęp do poszczególnych wartości staje się znacznie bardziej złożony, wymagając operacji przesunięcia bitów i maskowania (
BitSet
klasa robi to za Ciebie). Jednak ze względu na efekty pamięci podręcznej może to być nadal znacznie szybsze niż użycie wartości logicznej [], gdy tablica jest duża. IIRC I osiągnęło kiedyś w ten sposób przyspieszenie o współczynnik 2 lub 3.źródło
Najbardziej efektywną strukturą danych dla pamięci podręcznej jest tablica. Pamięci podręczne działają najlepiej, jeśli struktura danych jest ułożona sekwencyjnie, podczas gdy procesory odczytują całe linie pamięci podręcznej (zwykle 32 bajty lub więcej) na raz z pamięci głównej.
Każdy algorytm, który uzyskuje dostęp do pamięci w kolejności losowej, kasuje pamięci podręczne, ponieważ zawsze potrzebuje nowych wierszy pamięci podręcznej, aby pomieścić losowo dostępną pamięć. Z drugiej strony algorytm, który działa sekwencyjnie w tablicy, jest najlepszy, ponieważ:
Daje to procesorowi szansę na odczyt z wyprzedzeniem, np. Spekulacyjnie umieszczenie większej ilości pamięci w pamięci podręcznej, do której będzie później potrzebny. Ten odczyt z wyprzedzeniem zapewnia ogromny wzrost wydajności.
Uruchamianie ścisłej pętli na dużej macierzy pozwala również procesorowi na buforowanie kodu wykonywanego w pętli, aw większości przypadków pozwala na wykonanie algorytmu całkowicie z pamięci podręcznej bez konieczności blokowania dostępu do pamięci zewnętrznej.
źródło
Jednym z przykładów, które widziałem w silniku gry, było przenoszenie danych z obiektów do ich własnych tablic. Obiekt gry, który podlegał fizyce, może mieć również dołączonych wiele innych danych. Ale podczas pętli aktualizacji fizyki wszystko, o co dbał silnik, dotyczyło danych o pozycji, prędkości, masie, obwiedni itp. Wszystko to zostało więc umieszczone we własnych tablicach i zoptymalizowane tak bardzo, jak to możliwe dla SSE.
Tak więc podczas pętli fizyki dane fizyczne były przetwarzane w kolejności tablicowej przy użyciu matematyki wektorowej. Obiekty gry używały swojego identyfikatora obiektu jako indeksu w różnych tablicach. Nie był to wskaźnik, ponieważ wskaźniki mogłyby zostać unieważnione, gdyby trzeba było przenieść tablice.
Pod wieloma względami naruszało to wzorce projektowe zorientowane obiektowo, ale znacznie przyspieszyło kod, umieszczając blisko siebie dane, które musiały być obsługiwane w tych samych pętlach.
Ten przykład jest prawdopodobnie nieaktualny, ponieważ spodziewam się, że większość nowoczesnych gier korzysta z gotowego silnika fizycznego, takiego jak Havok.
źródło
Poruszył go tylko jeden post, ale pojawia się duży problem podczas udostępniania danych między procesami. Chcesz uniknąć sytuacji, w których wiele procesów próbuje jednocześnie modyfikować tę samą linię pamięci podręcznej. Coś, na co należy zwrócić uwagę, to „fałszywe” udostępnianie, w którym dwie sąsiednie struktury danych współdzielą linię pamięci podręcznej, a modyfikacje jednej unieważniają linię pamięci podręcznej dla drugiej. Może to powodować niepotrzebne przemieszczanie się linii pamięci podręcznej między pamięcią podręczną procesora udostępniającą dane w systemie wieloprocesorowym. Aby tego uniknąć, należy wyrównać i uzupełnić struktury danych, aby umieścić je w różnych wierszach.
źródło
Uwaga dotycząca „klasycznego przykładu” użytkownika 1800 INFORMACJE (zbyt długi na komentarz)
Chciałem sprawdzić różnice czasu dla dwóch rzędów iteracji („zewnętrzny” i „wewnętrzny”), więc wykonałem prosty eksperyment z dużą tablicą 2D:
a drugi przypadek z rozszerzeniem
for
zamienionymi pętlami.Wolniejsza wersja („x first”) miała 0,88 sekundy, a szybsza 0,06 sekundy. To jest moc buforowania :)
Użyłem
gcc -O2
i nadal pętle nie zostały zoptymalizowane. Komentarz Ricardo, że „większość współczesnych kompilatorów potrafi samodzielnie to rozgryźć” nie jest trafnyźródło
Mogę odpowiedzieć (2), mówiąc, że w świecie C ++ połączone listy mogą łatwo zabić pamięć podręczną procesora. W miarę możliwości lepszym rozwiązaniem są tablice. Brak doświadczenia, czy to samo dotyczy innych języków, ale łatwo sobie wyobrazić, że pojawią się te same problemy.
źródło
Pamięć podręczna jest ułożona w „wierszach pamięci podręcznej”, a (rzeczywista) pamięć jest odczytywana i zapisywana we fragmentach o tym rozmiarze.
Struktury danych zawarte w pojedynczej linii pamięci podręcznej są zatem bardziej wydajne.
Podobnie algorytmy, które uzyskują dostęp do ciągłych bloków pamięci, będą bardziej wydajne niż algorytmy, które przeskakują przez pamięć w losowej kolejności.
Niestety rozmiar linii pamięci podręcznej różni się znacznie między procesorami, więc nie ma sposobu, aby zagwarantować, że struktura danych optymalna na jednym procesorze będzie wydajna na innym.
źródło
Aby zapytać, jak utworzyć kod, buforować efektywną pamięć podręczną i większość innych pytań, zwykle zapytać, jak zoptymalizować program, ponieważ pamięć podręczna ma tak ogromny wpływ na wydajność, że każdy zoptymalizowany program jest pamięcią podręczną przyjazny dla efektywnej pamięci podręcznej.
Sugeruję przeczytanie o optymalizacji, na tej stronie jest kilka dobrych odpowiedzi. Jeśli chodzi o książki, polecam książkę Computer Systems: A Programmer's Perspective, która zawiera drobny tekst na temat prawidłowego korzystania z pamięci podręcznej.
(btw - tak źle, jak może być brak pamięci podręcznej, jest gorzej - jeśli program stronicuje z dysku twardego ...)
źródło
Było wiele odpowiedzi dotyczących ogólnych porad, takich jak wybór struktury danych, wzorzec dostępu, itp. W tym miejscu chciałbym dodać kolejny wzorzec projektowania kodu, zwany potokiem oprogramowania, który wykorzystuje aktywne zarządzanie pamięcią podręczną.
Pomysł jest zapożyczony z innych technik potokowych, np. Potokowania instrukcji procesora.
Ten typ wzoru najlepiej pasuje do procedur, które
Weźmy prosty przypadek, w którym jest tylko jedna procedura podrzędna. Zwykle kod chciałby:
Aby uzyskać lepszą wydajność, możesz chcieć przekazać wiele danych wejściowych do funkcji w partii, aby zamortyzować narzut wywołania funkcji, a także zwiększyć lokalność pamięci podręcznej kodu.
Jednak, jak wspomniano wcześniej, jeśli wykonanie kroku jest mniej więcej takie samo jak czas dostępu do pamięci RAM, możesz dalej ulepszyć kod do czegoś takiego:
Przepływ wykonania wyglądałby następująco:
Może być zaangażowanych więcej kroków, wtedy możesz zaprojektować wieloetapowy potok, o ile czas kroków i opóźnienie dostępu do pamięci pasują do siebie, cierpiałbyś na niewielką utratę pamięci podręcznej kodu / danych. Jednak proces ten wymaga wielu eksperymentów, aby znaleźć prawidłowe grupowanie kroków i czas pobierania wstępnego. Ze względu na wymagany wysiłek, widzi większą adaptację w wydajnym przetwarzaniu strumieni danych / pakietów. Dobry przykład kodu produkcyjnego można znaleźć w DPDK QoS Enqueue pipeline design: http://dpdk.org/doc/guides/prog_guide/qos_framework.html Rozdział 21.2.4.3. Kolejkuj potok.
Więcej informacji można znaleźć:
https://software.intel.com/en-us/articles/memory-management-for-optimal-performance-on-intel-xeon-phi-coprocessor-alignment-and
http://infolab.stanford.edu/~ullman/dragon/w06/lectures/cs243-lec13-wei.pdf
źródło
Napisz swój program tak, aby miał jak najmniejszy rozmiar. Dlatego nie zawsze dobrym pomysłem jest stosowanie optymalizacji -O3 dla GCC. Zajmuje większy rozmiar. Często -Os jest tak samo dobre jak -O2. Wszystko zależy jednak od używanego procesora. YMMV.
Pracuj z małymi porcjami danych naraz. Dlatego mniej wydajne algorytmy sortowania mogą działać szybciej niż szybkie sortowanie, jeśli zestaw danych jest duży. Znajdź sposoby na podzielenie większych zbiorów danych na mniejsze. Inni to sugerowali.
Aby pomóc ci lepiej wykorzystać lokalność czasową / przestrzenną instrukcji, możesz chcieć przestudiować, w jaki sposób twój kod jest konwertowany na asembler. Na przykład:
Dwie pętle generują różne kody, mimo że po prostu analizują tablicę. W każdym razie twoje pytanie jest bardzo specyficzne dla architektury. Tak więc jedynym sposobem ścisłej kontroli wykorzystania pamięci podręcznej jest zrozumienie, jak działa sprzęt i optymalizacja kodu.
źródło
Oprócz wyrównywania struktury i pól, jeśli twoja struktura jest przydzielona sterta, możesz chcieć użyć alokatorów, które obsługują wyrównane alokacje; jak _aligned_malloc (sizeof (DANE), SYSTEM_CACHE_LINE_SIZE); w przeciwnym razie możesz mieć losowe fałszywe udostępnianie; pamiętaj, że w systemie Windows domyślna sterta ma 16-bajtowe wyrównanie.
źródło