Wydajność jednozadaniowego kodu zorientowanego na ADT na nowoczesnych procesorach

32

Można przypuszczać, że praca na niezmiennych danych z pojedynczymi przypisaniami wymaga więcej pamięci, ponieważ ciągle tworzysz nowe wartości (chociaż kompilatory pod pokrywami wykonują sztuczki wskaźnikowe, aby to nie było problemem).

Ale słyszałem już kilka razy, że straty w wydajności są równoważone przez zyski w sposobie, w jaki procesor (w szczególności kontroler pamięci) może skorzystać z faktu, że pamięć nie jest zmutowana (tyle).

Miałem nadzieję, że ktoś może rzucić nieco światła na to, jak to jest prawda (a jeśli tak nie jest?).

W komentarzu do innego postu wspomniano, że abstrakcyjne typy danych (ADT) mają do czynienia z tym, co mnie jeszcze bardziej zaciekawiło, w jaki sposób ADT wpływają konkretnie na sposób, w jaki CPU radzi sobie z pamięcią? Jest to jednak na marginesie, głównie interesuje mnie, jak czystość języka koniecznie wpływa na wydajność procesora i jego pamięci podręcznych itp.

Jimmy Hoffa
źródło
2
jest to szczególnie przydatne w wielowątkowości, gdzie czytelnik może atomowo złapać migawkę i mieć pewność, że nie będzie mutować podczas czytania
maniak zapadkowy
@ratchetfreak Rozumiem, że z punktu widzenia programowania, twój kod zyskuje więcej gwarancji bezpieczeństwa, ale moja ciekawość dotyczy kontrolera pamięci na CPU i tego, jak to zachowanie ma dla niego znaczenie (lub jeśli nie ma), ponieważ słyszałem, jak twierdzono, że bandied o ręce pełnej razy, która powiedziała, że ​​jest bardziej wydajna dla kontrolera pamięci, a nie znam szczegółów niskiego poziomu na tyle dobrze, aby powiedzieć, czy to może być prawda.
Jimmy Hoffa
Nawet gdyby to była prawda, nie sądzę, że mniejsza modyfikacja pamięci jest najlepszym punktem sprzedaży niezmienności. Pamięć ma zostać zmodyfikowana, a procesory i menedżerowie pamięci radzili sobie całkiem dobrze przez lata.
Rein Henrichs
1
Chciałbym również zauważyć, że wydajność pamięci niekoniecznie musi zależeć od optymalizacji kompilatora podczas korzystania z niezmiennych struktur. W tym przykładzie let a = [1,2,3] in let b = 0:a in (a, b, (-1):c)podziału zmniejsza zapotrzebowanie na pamięć, ale zależy od definicji (:)i []i nie kompilatora. Myślę? Nie jestem pewien co do tego.

Odpowiedzi:

28

Procesor (w szczególności kontroler pamięci) może skorzystać z faktu, że pamięć nie jest zmutowana

Zaletą tego jest fakt, że kompilator nie pozwala na korzystanie z instrukcji paska narzędzi podczas uzyskiwania dostępu do danych.

Bariera pamięci, znana również jako bariera pamięci, ogrodzenie pamięci lub instrukcja ogrodzenia, jest rodzajem instrukcji bariery, która powoduje, że centralna jednostka przetwarzająca (CPU) lub kompilator wymusza ograniczenie kolejności operacji wykonywanych przed i po instrukcji bariery. Zazwyczaj oznacza to, że pewne operacje są wykonywane przed barierą, a inne po niej.

Bariery pamięci są konieczne, ponieważ większość współczesnych procesorów wykorzystuje optymalizacje wydajności, które mogą powodować wykonywanie zadań poza kolejnością. Ta zmiana kolejności operacji pamięci (ładuje i zapisuje) zwykle pozostaje niezauważona w ramach jednego wątku wykonania, ale może powodować nieprzewidywalne zachowanie w równoległych programach i sterownikach urządzeń, chyba że będzie dokładnie kontrolowana ...


Widzisz, gdy dostęp do danych z różnych wątków, na wielordzeniowym procesorze, dzieje się to w następujący sposób: różne wątki działają w różnych rdzeniach, każdy używa własnej pamięci podręcznej (lokalnej do ich rdzenia) - kopii jakiejś globalnej pamięci podręcznej.

Jeśli dane są zmienne, a programista musi być spójny między różnymi wątkami, należy podjąć środki w celu zagwarantowania spójności. Dla programisty oznacza to stosowanie konstrukcji synchronizujących, gdy uzyskują one dostęp (np. Odczyt) danych w danym wątku.

W przypadku kompilatora konstrukcja synchronizacji w kodzie oznacza, że ​​należy wstawić instrukcję membar , aby upewnić się, że zmiany dokonane w kopii danych w jednym z rdzeni są odpowiednio propagowane („opublikowane”), aby zagwarantować, że pamięci podręczne w innych rdzeniach mieć tę samą (aktualną) kopię.

Nieco upraszczając, patrz uwaga poniżej , oto co dzieje się w procesorze wielordzeniowym dla paska membar:

  1. Wszystkie rdzenie przestają przetwarzać - aby uniknąć przypadkowego zapisu do pamięci podręcznej.
  2. Wszystkie aktualizacje lokalnych pamięci podręcznych są zapisywane z powrotem w pamięci globalnej - w celu zapewnienia, że ​​globalna pamięć podręczna zawiera najnowsze dane. To zajmuje trochę czasu.
  3. Zaktualizowane dane są zapisywane z globalnej pamięci podręcznej na lokalne - w celu zapewnienia, że ​​lokalne pamięci podręczne zawierają najnowsze dane. To zajmuje trochę czasu.
  4. Wszystkie rdzenie wznawiają wykonywanie.

Widzisz, wszystkie rdzenie nic nie robią, gdy dane są kopiowane tam iz powrotem między globalnymi i lokalnymi pamięciami podręcznymi . Jest to konieczne, aby upewnić się, że zmienne dane są odpowiednio zsynchronizowane (bezpieczne dla wątków). Jeśli są 4 rdzenie, wszystkie 4 zatrzymują się i czekają na synchronizację pamięci podręcznej. Jeśli jest ich 8, wszystkie 8 się zatrzymują. Jeśli jest 16 ... no cóż, masz 15 rdzeni, które nic nie robią, czekając na rzeczy potrzebne do zrobienia jednego z nich.

Zobaczmy teraz, co się stanie, gdy dane będą niezmienne? Bez względu na to, jaki wątek ma do niego dostęp, gwarantuje się, że będzie taki sam. Dla programisty oznacza to, że nie trzeba wstawiać konstrukcji synchronizujących, gdy uzyskują one dostęp (odczyt) danych w danym wątku.

Z kolei dla kompilatora oznacza to, że nie trzeba wstawiać instrukcji membar .

W rezultacie dostęp do danych nie musi zatrzymywać rdzeni i czekać, aż dane będą zapisywane w tę iz powrotem między globalnymi i lokalnymi pamięciami podręcznymi. Jest to zaletą tego, że pamięć nie jest zmutowana .


Zauważ, że uproszczenie powyższego wyjaśnienia porzuca bardziej skomplikowane negatywne skutki modyfikowania danych, na przykład na potokach . Aby zagwarantować wymagane zamawianie, procesor musi unieważnić pilele, na które wpływ mają zmiany danych - to kolejny spadek wydajności. Jeśli jest to realizowane przez proste (a tym samym niezawodne) unieważnienie wszystkich potoków, efekt negatywny jest dalej wzmacniany.

komar
źródło