False sharing

False sharing to problem wydajnościowy, który może pojawić się w programach wielowątkowych nawet wtedy, gdy dwa wątki nie zapisują do tej samej zmiennej. Wystarczy, że ich dane leżą blisko siebie w pamięci i trafią do tej samej linii cache procesora. Jeden rdzeń zmienia swoją wartość, drugi modyfikuje inną, a mimo to pamięć podręczna musi być cały czas uzgadniana pomiędzy rdzeniami. Program działa poprawnie i nie zgłasza błędu, ale jego wydajność potrafi wyraźnie spaść. Właśnie dlatego false sharing jest tak niewdzięczny w diagnozowaniu - wszystko wygląda dobrze, tylko kod działa wolniej, niż powinien.

Dwa wątki, dwie zmienne - gdzie pojawia się problem?

Wyobraźmy sobie program działający na procesorze wielordzeniowym. Pierwszy wątek zwiększa licznik A, a drugi licznik B.

Wątek 1 → licznik_a
Wątek 2 → licznik_b

Na pierwszy rzut oka wszystko wygląda dobrze. Każdy wątek ma własną zmienną, więc nie powinien przeszkadzać drugiemu.

Problem może się jednak pojawić niżej - nie na poziomie kodu źródłowego, lecz pamięci podręcznej procesora.

Procesor nie pobiera z pamięci każdej zmiennej osobno. Dane są przenoszone i przechowywane w większych fragmentach nazywanych liniami cache.

Jeżeli dwa liczniki leżą w pamięci obok siebie, mogą trafić do jednej linii:

Linia cache:

[ licznik_a | licznik_b | inne dane ........ ]

I właśnie w takim miejscu może zacząć się false sharing.

Co to jest false sharing?

False sharing można opisać jako pozorne współdzielenie danych. Wątki tak naprawdę korzystają z różnych zmiennych, ale z punktu widzenia cache procesora znajdują się one w tym samym fragmencie pamięci.

Załóżmy, że licznik A jest często modyfikowany przez pierwszy rdzeń, a licznik B przez drugi:

Rdzeń 1:
licznik_a++

Rdzeń 2:
licznik_b++

Każdy zapis może wpływać na stan całej linii cache. Drugi rdzeń musi więc reagować na zmianę fragmentu pamięci, mimo że interesuje go zupełnie inna wartość.

Po chwili sytuacja odwraca się - drugi rdzeń wykonuje zapis do swojego licznika i linia znowu musi zostać odpowiednio uzgodniona pomiędzy pamięciami podręcznymi.

Jeżeli takie operacje zdarzają się miliony razy, koszt tej wymiany może stać się naprawdę widoczny.

Dlaczego procesor nie traktuje zmiennych osobno?

Ponieważ mechanizm cache nie zna pojęcia "zmienna A" czy "zmienna B". Dla procesora ważny jest fragment pamięci znajdujący się w konkretnej linii cache.

Na wielu współczesnych procesorach linia cache ma 64 bajty, choć nie jest to wartość, którą można bezwarunkowo przyjąć dla każdej architektury.

Jeżeli mamy dwie 8-bajtowe wartości:

counter_a - 8 bajtów
counter_b - 8 bajtów

bez problemu mogą znaleźć się obok siebie w jednym 64-bajtowym fragmencie.

Dla programisty są to dwa niezależne liczniki. Dla mechanizmu spójności cache mogą być częścią dokładnie tej samej linii.

Stąd właśnie słowo "false". Dane nie są faktycznie współdzielone, ale sprzęt zachowuje się tak, jakby zmiany dotyczyły wspólnego fragmentu pamięci.

Prosty przykład false sharing

Spójrzmy na bardzo prostą strukturę w C++:

struct Liczniki {
    std::atomic pierwszy;
    std::atomic drugi;
};

Następnie dwa wątki wykonują dużą liczbę operacji:

Wątek 1:
liczniki.pierwszy++

Wątek 2:
liczniki.drugi++

Każdy z nich korzysta z innego pola. Nie ma tutaj bezpośredniego zapisu do tej samej zmiennej.

Pola struktury leżą jednak blisko siebie w pamięci. Jeśli trafią do jednej linii cache, intensywne zapisy z różnych rdzeni mogą zacząć powodować ciągłe przekazywanie i aktualizowanie tej linii.

Przy kilku operacjach nie będzie to miało znaczenia. Przy milionach zmian różnica potrafi być już zauważalna.

False sharing a data race - to nie jest ten sam problem

Oba pojęcia pojawiają się przy programowaniu wielowątkowym, więc łatwo wrzucić je do jednego worka. W praktyce dotyczą czegoś zupełnie innego.

Data race, czyli wyścig danych, może prowadzić do błędnych wyników albo nieprzewidywalnego działania programu. Dwa wątki próbują wtedy korzystać z tych samych danych bez odpowiedniej synchronizacji.

Przy false sharing program może być napisany całkowicie poprawnie. Problem pojawia się w wydajności - procesor wykonuje dodatkową pracę związaną z utrzymywaniem spójności cache.

Jak false sharing wygląda w praktyce?

Najbardziej podejrzana jest sytuacja, w której dołożenie kolejnych wątków prawie nie przyspiesza programu.

Załóżmy, że pojedynczy wątek wykonuje zadanie w 10 sekund. Dodajemy kolejne i oczekujemy, że czas mocno spadnie, tymczasem wyniki wyglądają tak:

1 wątek  → 10 s
2 wątki  → 8 s
4 wątki  → 7 s
8 wątków → 7,5 s

To oczywiście nie jest dowód na false sharing. Wielowątkowość może słabo skalować się z wielu powodów: przez blokady, ograniczoną przepustowość pamięci, nierówny podział pracy czy sam charakter obliczeń.

Jeżeli jednak poszczególne wątki bardzo często zapisują dane leżące obok siebie w pamięci, false sharing jest jednym z pierwszych podejrzanych.

Jak ograniczyć false sharing?

Najprostszy pomysł jest dość intuicyjny: dane intensywnie modyfikowane przez różne wątki trzeba rozsunąć tak, żeby nie trafiały przypadkowo do tej samej linii cache.

Jednym ze sposobów jest padding, czyli dodanie pustej przestrzeni pomiędzy polami.

Zamiast takiego układu:

[ licznik A ][ licznik B ]

możemy dążyć do czegoś w rodzaju:

[ licznik A ][ ............ ]

[ licznik B ][ ............ ]

Jeśli oba liczniki znajdą się w różnych liniach cache, zapis wykonywany przez jeden rdzeń nie musi od razu wpływać na linię używaną przez drugi.

Nie warto jednak dodawać pustych bajtów wszędzie "na wszelki wypadek". Większe struktury zużywają więcej pamięci i mogą pogorszyć lokalność danych. Najpierw trzeba mieć powód, żeby sądzić, że false sharing naprawdę występuje.

False sharing w C++ - pomocne wyrównanie danych

Od C++17 dostępna jest stała:

std::hardware_destructive_interference_size

Można jej użyć przy rozmieszczaniu danych, które nie powinny znajdować się zbyt blisko siebie z punktu widzenia pamięci podręcznej.

Przykładowa struktura może wyglądać tak:

#include 
#include 

struct Liczniki {
    alignas(std::hardware_destructive_interference_size)
    std::atomic pierwszy;

    alignas(std::hardware_destructive_interference_size)
    std::atomic drugi;
};

Takie wyrównanie ma sens wtedy, gdy dane są często zmieniane przez różne wątki i pomiary wskazują, że ich bliskie położenie rzeczywiście szkodzi wydajności.

Stosowanie go przy każdej zmiennej atomowej nie ma większego sensu. False sharing to problem, który warto najpierw zmierzyć, a dopiero potem poprawiać.

False sharing w tablicach - każdy ma swój element, a problem nadal istnieje

Bardzo ciekawy przypadek pojawia się przy tablicach. Możemy przecież przydzielić każdemu wątkowi osobny licznik:

liczniki[0] → wątek 0
liczniki[1] → wątek 1
liczniki[2] → wątek 2
liczniki[3] → wątek 3

Na poziomie kodu wygląda to wręcz wzorowo. Każdy wątek zapisuje do własnego elementu.

Tyle że te cztery wartości mogą leżeć w pamięci jedna obok drugiej i wszystkie zmieścić się w jednej linii cache.

Jeśli każdy rdzeń bardzo często aktualizuje swój licznik, ta sama linia może zacząć krążyć pomiędzy pamięciami podręcznymi kolejnych rdzeni.

I właśnie dlatego false sharing bywa zaskakujący. Kod wygląda jak dobrze rozdzielony między wątki, a mimo tego sprzęt nadal widzi wspólny fragment pamięci.

Jak wykryć false sharing?

Samo spojrzenie na kod nie daje pewności. Możemy znaleźć podejrzane miejsca, ale ostatecznie liczą się pomiary.

Dobrym początkiem jest porównanie czasu wykonania programu dla różnej liczby wątków:

1 wątek
2 wątki
4 wątki
8 wątków

Jeżeli wydajność niemal nie rośnie, warto przyjrzeć się miejscom, w których:

• kilka wątków bardzo często wykonuje zapisy,
• każdy wątek posiada własny element struktury albo tablicy,
• te elementy leżą blisko siebie w pamięci,
• po ich rozdzieleniu program zaczyna działać szybciej.

Przy większych projektach można skorzystać z profilerów sprzętowych, na przykład Intel VTune. Takie narzędzia pomagają sprawdzić, gdzie procesor traci czas na dostęp do pamięci i komunikację pomiędzy rdzeniami.

Dobry test jest prosty: mierzysz wydajność, zmieniasz rozmieszczenie danych i mierzysz jeszcze raz. Jeśli wynik wyraźnie się poprawił, masz znacznie mocniejszy argument niż samo przypuszczenie na podstawie kodu.

Kiedy warto się tym przejmować?

Nie w każdym programie.

Jeżeli aplikacja większość czasu czeka na bazę danych, sieć albo dysk, rozmieszczenie dwóch liczników w pamięci raczej nie będzie największym problemem.

False sharing nabiera znaczenia wtedy, gdy mamy intensywne obliczenia wielowątkowe i bardzo częste zapisy do pamięci.

Można go spotkać między innymi w:

• kodzie HPC,
• systemach przetwarzających duże ilości danych,
• silnikach obliczeniowych,
• strukturach współbieżnych,
• licznikach statystyk aktualizowanych przez wiele wątków,
• serwerach mocno optymalizowanych pod wydajność.

W takich zastosowaniach pozornie niewinna zmiana w ułożeniu danych może czasem dać większą poprawę niż kilka godzin poprawiania samej pętli obliczeniowej.

False sharing w skrócie

False sharing dobrze pokazuje, że programista i procesor mogą patrzeć na te same dane w zupełnie inny sposób.

Dla nas dwa wątki korzystają z dwóch różnych zmiennych. Dla procesora te zmienne mogą znajdować się w jednej linii cache, więc zmiana jednej powoduje dodatkową pracę również po stronie drugiego rdzenia.

Program nadal daje poprawne wyniki. Po prostu traci część wydajności na ciągłe uzgadnianie stanu pamięci podręcznej.

W takiej sytuacji rozwiązaniem nie musi być dodatkowa blokada czy bardziej skomplikowana synchronizacja. Czasami wystarczy lepiej rozdzielić dane należące do poszczególnych wątków - oczywiście dopiero wtedy, gdy pomiary pokazują, że rzeczywiście jest to problem.