Co każdy programista powinien wiedzieć o pamięci?

164

Zastanawiam się, ile z książki Ulricha Dreppera What Every Programmer Should Know About Memory z 2007 roku jest nadal aktualna. Nie mogłem też znaleźć nowszej wersji niż 1.0 lub erraty.

Framester
źródło
1
czy ktoś wie, czy mogę gdzieś pobrać ten artykuł w formacie mobi, żebym mógł go łatwo przeczytać na Kindle?
Plik
1
To nie jest mobi, ale LWN opublikował artykuł jako zestaw artykułów, które są łatwiejsze do odczytania na telefonie / tablecie. Pierwsza jest na lwn.net/Articles/250967
Nathan

Odpowiedzi:

111

O ile pamiętam, treść Dreppera opisuje podstawowe pojęcia dotyczące pamięci: jak działa pamięć podręczna procesora, czym jest pamięć fizyczna i wirtualna oraz jak jądro Linuksa radzi sobie z tym zoo. Prawdopodobnie w niektórych przykładach znajdują się przestarzałe odniesienia do API, ale to nie ma znaczenia; nie wpłynie to na znaczenie podstawowych pojęć.

Tak więc żadnej książki lub artykułu, który opisuje coś fundamentalnego, nie można nazwać przestarzałą. „Co każdy programista powinien wiedzieć o pamięci” jest zdecydowanie warte przeczytania, ale cóż, nie sądzę, aby było to dla „każdego programisty”. Jest bardziej odpowiedni dla facetów z systemu / embedded / kernel.

Dan Kruchinin
źródło
3
Tak, naprawdę nie rozumiem, dlaczego programista miałby wiedzieć, jak SRAM i DRAM działają na poziomie analogowym - to niewiele pomoże przy pisaniu programów. A ludzie, którzy naprawdę potrzebują tej wiedzy, powinni lepiej poświęcić czas na czytanie podręczników o szczegółach dotyczących rzeczywistych czasów itp. Ale dla osób zainteresowanych niskopoziomowymi sprzętami HW? Może nieprzydatne, ale przynajmniej zabawne.
Voo
47
Obecnie wydajność wydajność == pamięć, więc pamięć zrozumienie jest najważniejszą rzeczą w każdym zastosowaniu wysokiej wydajności. To sprawia, że ​​papier jest niezbędny dla każdego, kto zajmuje się: tworzeniem gier, obliczeniami naukowymi, finansami, bazami danych, kompilatorami, przetwarzaniem dużych zbiorów danych, wizualizacją, wszystkim, co musi obsługiwać wiele żądań ... Więc tak, jeśli pracujesz w aplikacji to jest bezczynne przez większość czasu, jak edytor tekstu, papier jest całkowicie nieinteresujący, dopóki nie będziesz musiał zrobić czegoś szybko, jak znaleźć słowo, policzyć słowa, sprawdzić pisownię ... och, czekaj ... nieważne.
gnzlbg
144

Przewodnik w formacie PDF znajduje się pod adresem https://www.akkadia.org/drepper/cpumemory.pdf .

Nadal jest ogólnie doskonały i wysoce zalecany (przeze mnie i myślę, że przez innych ekspertów od dostrajania wydajności). Byłoby fajnie, gdyby Ulrich (lub ktokolwiek inny) napisał aktualizację na 2017 rok, ale wymagałoby to dużo pracy (np. Ponowne uruchomienie benchmarków). Zobacz także inne łącza optymalizacji wydajności x86 i SSE / asm (i C / C ++) w tag wiki . (Artykuł Ulricha nie jest specyficzny dla x86, ale większość (wszystkie) jego testów porównawczych dotyczy sprzętu x86).

Niskopoziomowe szczegóły sprzętowe dotyczące działania pamięci DRAM i pamięci podręcznych nadal mają zastosowanie . DDR4 używa tych samych poleceń, co opisane dla DDR1 / DDR2 (seria odczytu / zapisu). Ulepszenia DDR3 / 4 nie są fundamentalnymi zmianami. AFAIK, wszystkie kwestie niezależne od archów nadal mają zastosowanie ogólnie, np. Do AArch64 / ARM32.

Zobacz także sekcję Platformy związane z opóźnieniami w tej odpowiedzi, aby uzyskać ważne szczegóły dotyczące wpływu opóźnień pamięci / L3 na przepustowość jednowątkową: bandwidth <= max_concurrency / latencyi jest to w rzeczywistości główne wąskie gardło dla przepustowości jednowątkowej w nowoczesnym wielordzeniowym procesorze, takim jak Xeon . Ale czterordzeniowy komputer stacjonarny Skylake może zbliżyć się do maksymalnego wykorzystania przepustowości DRAM za pomocą jednego wątku. To łącze zawiera bardzo dobre informacje o sklepach NT w porównaniu ze zwykłymi sklepami na platformie x86. Dlaczego Skylake jest o wiele lepszy niż Broadwell-E pod względem przepustowości pamięci jednowątkowej? to podsumowanie.

Dlatego sugestia Ulricha w 6.5.8 Wykorzystanie całej przepustowości, dotycząca używania pamięci zdalnej w innych węzłach NUMA, jak również we własnym, przynosi efekt przeciwny do zamierzonego na nowoczesnym sprzęcie, w którym kontrolery pamięci mają większą przepustowość niż pojedynczy rdzeń. Cóż, prawdopodobnie możesz sobie wyobrazić sytuację, w której jest korzyść netto z uruchamiania wielu żądnych pamięci wątków w tym samym węźle NUMA w celu komunikacji między wątkami o małych opóźnieniach, ale korzystanie z pamięci zdalnej do rzeczy o dużej przepustowości, które nie są wrażliwe na opóźnienia. Ale jest to dość niejasne, zwykle wystarczy podzielić wątki między węzłami NUMA i pozwolić im korzystać z pamięci lokalnej. Przepustowość na rdzeń jest wrażliwa na opóźnienia ze względu na maksymalne limity współbieżności (patrz poniżej), ale wszystkie rdzenie w jednym gnieździe mogą zwykle bardziej niż nasycać kontrolery pamięci w tym gnieździe.


(zwykle) Nie używaj wstępnego pobierania oprogramowania

Jedną z głównych rzeczy, które uległy zmianie, jest to, że wstępne pobieranie sprzętowe jest znacznie lepsze niż w Pentium 4 i może rozpoznawać wzorce dostępu krokowego do dość dużego kroku i wiele strumieni jednocześnie (np. Jeden do przodu / do tyłu na stronę 4k). Podręcznik optymalizacji firmy Intel opisuje niektóre szczegóły dotyczące modułów wstępnych HW na różnych poziomach pamięci podręcznej dla mikroarchitektury z rodziny Sandybridge. Ivybridge i później mają wstępne pobieranie sprzętowe następnej strony, zamiast czekać na brak pamięci podręcznej na nowej stronie, aby uruchomić szybki start. Zakładam, że AMD ma podobne rzeczy w swojej instrukcji optymalizacji. Pamiętaj, że podręcznik Intela jest również pełen starych porad, z których niektóre są dobre tylko dla P4. Sekcje specyficzne dla Sandybridge są oczywiście dokładne dla SnB, ale npw HSW zmieniło się nielaminowanie mikro-topionych uopsów i instrukcja o tym nie wspomina .

W dzisiejszych czasach zwykłą radą jest usunięcie całego wstępnego pobierania SW ze starego kodu i rozważenie przywrócenia go tylko wtedy, gdy profilowanie pokazuje chybienia w pamięci podręcznej (i nie nasycasz pasma pamięci). Wstępne pobranie obu stron następnego kroku wyszukiwania binarnego może nadal pomóc. np. gdy zdecydujesz, na który element patrzeć jako następny, pobierz wstępnie elementy 1/4 i 3/4, aby mogły ładować się równolegle z ładowaniem / sprawdzaniem środka.

Sugestia użycia osobnego wątku pobierania wstępnego (6.3.4) jest , jak sądzę, całkowicie przestarzała i była dobra tylko na Pentium 4. P4 miał hiperwątkowość (2 rdzenie logiczne współdzielące jeden rdzeń fizyczny), ale niewystarczająca pamięć podręczna śledzenia (i / lub zasoby wykonawcze poza kolejnością), aby uzyskać przepustowość podczas uruchamiania dwóch pełnych wątków obliczeniowych na tym samym rdzeniu. Ale nowoczesne procesory (rodzina Sandybridge i Ryzen) są znacznie mocniejsze i powinny albo uruchamiać prawdziwy wątek, albo nie używać hiperwątkowości (pozostaw drugi rdzeń logiczny bezczynny, aby wątek solo miał pełne zasoby zamiast partycjonować ROB).

Wstępne pobieranie oprogramowania zawsze było „kruche” : odpowiednie wartości magicznego strojenia, aby uzyskać przyspieszenie, zależą od szczegółów sprzętu i być może obciążenia systemu. Za wcześnie i jest eksmitowany przed ładowaniem na żądanie. Za późno i to nie pomaga. Ten artykuł na blogu przedstawia kod + wykresy dla interesującego eksperymentu z użyciem wstępnego pobierania SW w Haswell do wstępnego pobierania niesekwencyjnej części problemu. Zobacz także Jak prawidłowo korzystać z instrukcji pobierania wstępnego? . Pobieranie wstępne NT jest interesujące, ale jeszcze bardziej kruche, ponieważ wczesna eksmisja z L1 oznacza, że ​​musisz przejść całą drogę do L3 lub DRAM, a nie tylko L2. Jeśli potrzebujesz każdej kropli wydajności i możesz dostroić się do konkretnej maszyny, warto zwrócić uwagę na pobranie wstępne SW w celu uzyskania dostępu sekwencyjnego, alemoże nadal być spowolnieniem, jeśli masz wystarczająco dużo pracy ALU do wykonania, zbliżając się do wąskiego gardła w pamięci.


Rozmiar linii pamięci podręcznej nadal wynosi 64 bajty. (Przepustowość odczytu / zapisu L1D jest bardzo wysoka, a nowoczesne procesory mogą wykonać 2 obciążenia wektorowe na zegar + 1 magazyn wektorowy, jeśli wszystko trafi w L1D. Zobacz Jak pamięć podręczna może być tak szybka? ) W AVX512 rozmiar linii = szerokość wektora, więc możesz załadować / zapisać całą linię pamięci podręcznej w jednej instrukcji. W ten sposób każde niewyrównane ładowanie / przechowywanie przekracza granicę linii pamięci podręcznej, zamiast każdej innej dla 256b AVX1 / AVX2, co często nie spowalnia pętli w tablicy, której nie było w L1D.

Instrukcje ładowania bez wyrównania mają zerową karę, jeśli adres jest wyrównany w czasie wykonywania, ale kompilatory (zwłaszcza gcc) tworzą lepszy kod podczas autowektoryzacji, jeśli wiedzą o jakichkolwiek gwarancjach wyrównania. W rzeczywistości niewyrównane operacje są generalnie szybkie, ale podziały stron nadal bolą (jednak znacznie mniej w Skylake; tylko ~ 11 dodatkowych cykli opóźnienia w porównaniu z 100, ale nadal zmniejsza przepustowość).


Zgodnie z przewidywaniami Ulrich, każdy multi-gniazdo system jest Numa te dni: zintegrowane kontrolery pamięci są standardowe, czyli nie ma zewnętrznego mostka północnego. Ale SMP nie oznacza już wielu gniazd, ponieważ wielordzeniowe procesory są szeroko rozpowszechnione. Procesory Intel Nehalem do Skylake z wykorzystali dużą integracyjnego L3 cache jako sprzęgła jednokierunkowego dla spójności między rdzeniami. Procesory AMD są różne, ale nie znam szczegółów.

Skylake-X (AVX512) nie ma już dołączonego L3, ale myślę, że nadal istnieje katalog tagów, który pozwala mu sprawdzić, co jest w pamięci podręcznej w dowolnym miejscu na chipie (a jeśli tak, to gdzie) bez wysyłania szpiegów do wszystkich rdzeni. SKX używa raczej siatki niż szyny pierścieniowej , niestety z jeszcze gorszymi opóźnieniami niż poprzednie wielordzeniowe Xeony.

Zasadniczo wszystkie porady dotyczące optymalizacji rozmieszczenia pamięci są nadal aktualne, tylko szczegóły tego, co się dzieje, gdy nie można uniknąć błędów w pamięci podręcznej lub rywalizacji, są różne.


6.4.2 Atomic ops : test porównawczy pokazujący, że pętla CAS-retry jest 4x gorsza niż w przypadku arbitrażu sprzętowego lock add, prawdopodobnie nadal odzwierciedla maksymalny przypadek rywalizacji . Ale w prawdziwych programach wielowątkowych synchronizacja jest ograniczona do minimum (ponieważ jest droga), więc rywalizacja jest niewielka, a pętla ponawiania CAS zwykle kończy się sukcesem bez konieczności ponawiania.

C ++ 11 std::atomic fetch_addskompiluje się do a lock add(lub lock xaddjeśli zostanie użyta wartość zwracana), ale algorytm używający CAS do zrobienia czegoś, czego nie można zrobić za pomocą lockinstrukcji ed, zwykle nie jest katastrofą. Użyj C ++ 11std::atomic lub C11 stdatomiczamiast starszych __syncwbudowanych gcc lub nowszych __atomicwbudowanych, chyba że chcesz mieszać atomowy i nieatomowy dostęp do tej samej lokalizacji ...

8.1 DWCAS ( cmpxchg16b) : Możesz nakłonić gcc do emitowania go, ale jeśli chcesz wydajnie ładować tylko połowę obiektu, potrzebujesz brzydkich unionhacków: Jak mogę zaimplementować licznik ABA z c ++ 11 CAS? . (Nie należy mylić DWCAS z DCAS z 2 oddzielnymi lokalizacjami pamięci . Atomowa emulacja DCAS bez blokady nie jest możliwa w przypadku DWCAS, ale umożliwia to pamięć transakcyjna (taka jak x86 TSX).)

8.2.4 Pamięć transakcyjna : Po kilku fałszywych startach (zwolnionych, a następnie wyłączonych przez aktualizację mikrokodu z powodu rzadko wywoływanego błędu) Intel ma działającą pamięć transakcyjną w późnym modelu Broadwell i wszystkich procesorach Skylake. Projekt jest nadal taki, jaki opisał David Kanter dla Haswell . Istnieje sposób lock-ellision na użycie go do przyspieszenia kodu, który używa (i może wrócić) zwykłego zamka (szczególnie z pojedynczą blokadą dla wszystkich elementów kontenera, więc wiele wątków w tej samej krytycznej sekcji często nie koliduje) ) lub napisać kod, który bezpośrednio wie o transakcjach.


7.5 Hugepages : anonimowe przezroczyste strony hugepages działają dobrze na Linuksie bez konieczności ręcznego używania hugetlbfs. Dokonaj alokacji> = 2MiB z wyrównaniem 2MiB (np. posix_memalignLub takialigned_alloc , który nie wymusza głupiego wymagania ISO C ++ 17, aby zawieść, kiedy size % alignment != 0).

Alokacja anonimowa wyrównana do 2MiB będzie domyślnie używać hugepages. Niektóre obciążenia (np. Które używają dużych alokacji przez jakiś czas po ich utworzeniu) mogą skorzystać
echo always >/sys/kernel/mm/transparent_hugepage/defragna skłonieniu jądra do defragmentowania pamięci fizycznej, kiedy jest to potrzebne, zamiast cofania się do 4k stron. (Zobacz dokumentację jądra ). Alternatywnie, użyj madvise(MADV_HUGEPAGE)po dokonaniu dużych alokacji (najlepiej nadal z wyrównaniem 2MiB).


Dodatek B: Oprofile : Linux perfzostał w większości wyparty oprofile. Aby uzyskać szczegółowe informacje dotyczące określonych mikroarchitektur, użyj ocperf.pyopakowania . na przykład

ocperf.py stat -etask-clock,context-switches,cpu-migrations,page-faults,cycles,\
branches,branch-misses,instructions,uops_issued.any,\
uops_executed.thread,idq_uops_not_delivered.core -r2 ./a.out

Aby zapoznać się z przykładami jego użycia, zobacz Czy plik MOV x86 naprawdę może być „wolny”? Dlaczego w ogóle nie mogę tego odtworzyć? .

Peter Cordes
źródło
3
Bardzo pouczająca odpowiedź i wskazówki! To zdecydowanie zasługuje na więcej głosów!
claf
@Peter Cordes Czy są jakieś inne przewodniki / artykuły, które warto przeczytać? Nie jestem programistą wysokowydajnym, ale chciałbym dowiedzieć się o tym więcej i mam nadzieję, że podniosę praktyki, które będę mógł wprowadzić do mojego codziennego programowania.
user3927312
4
@ user3927312: agner.org/optimize to jeden z najlepszych i najbardziej spójnych przewodników po zagadnieniach niskiego poziomu, szczególnie dla x86, ale niektóre z ogólnych pomysłów odnoszą się do innych ISA. Oprócz przewodników po asm, Agner ma optymalizujący plik PDF w języku C ++. Aby uzyskać inne łącza dotyczące wydajności / architektury procesora, zobacz stackoverflow.com/tags/x86/info . Napisałem też trochę o optymalizacji C ++, pomagając kompilatorowi w tworzeniu lepszego asm dla krytycznych pętli, kiedy warto przyjrzeć się wynikom asm kompilatora: kod C ++ do testowania hipotezy Collatza szybciej niż ręcznie napisany asm?
Peter Cordes,
74

Z mojego szybkiego spojrzenia wygląda to dość dokładnie. Jedyną rzeczą, na którą należy zwrócić uwagę, jest część dotycząca różnicy między „zintegrowanymi” a „zewnętrznymi” kontrolerami pamięci. Od czasu wypuszczenia na rynek serii i7 procesory Intel są w całości zintegrowane, a AMD używa zintegrowanych kontrolerów pamięci od pierwszego wydania układów AMD64.

Od czasu napisania tego artykułu niewiele się zmieniło, prędkości wzrosły, kontrolery pamięci stały się znacznie bardziej inteligentne (i7 będzie opóźniał zapisy do pamięci RAM, aż poczuje się jak zatwierdzenie zmian), ale niewiele się zmieniło . Przynajmniej nie w żaden sposób, o który dbałby programista.

Timothy Baldridge
źródło
5
Chciałbym zaakceptować was oboje. Ale zagłosowałem za twoim postem.
Framester
5
Prawdopodobnie najważniejszą zmianą, która jest istotna dla programistów SW, jest to, że wątki pobierania wstępnego to zły pomysł. Procesory są wystarczająco wydajne, aby uruchomić 2 pełne wątki z hiperwątkowością i mają znacznie lepsze wstępne pobieranie sprzętu. Ogólnie pobieranie oprogramowania z wyprzedzeniem jest o wiele mniej ważne, szczególnie w przypadku dostępu sekwencyjnego. Zobacz moją odpowiedź.
Peter Cordes,