GreenTea GC, czyli chwila wytchnienia przy filiżance zielonej herbaty, którą skradnie środowisko uruchomieniowe Go
Dlaczego pojawia się kolejny nowy GC
Dlaczego istniejący GC
Obecny GC w Go można opisać następującymi słowami:
- concurrent tri-color mark and sweep (współbieżne oznaczanie i zamiatanie trójkolorowe)
- Używa 3 kolorów (biały, szary, czarny) do śledzenia stanu obiektów.
- Biały: obiekt jeszcze nieodwiedzony
- Szary: obiekt odwiedzony, ale nie wszystkie jego obiekty potomne zostały odwiedzone
- Czarny: wszystkie obiekty potomne zostały odwiedzone
- Po zakończeniu cyklu wszystkie białe obiekty są zbierane.
- Używa Write Barrier (bariery zapisu) do ochrony nowo tworzonej pamięci podczas GC.
- Czas włączania/wyłączania Write Barrier stanowi znaczną część tzw. Stop-The-World (dalej STW).
- Wykonuje ten proces współbieżnie.
- Używa 3 kolorów (biały, szary, czarny) do śledzenia stanu obiektów.
- No Compaction (Brak kompresji)
- GC w Go nie wykonuje kompresji.
- Może wystąpić fragmentacja pamięci.
- Jednakże obiekty o rozmiarze mniejszym niż 32kb minimalizują fragmentację, wykorzystując per-P cache alokatora pamięci języka Go (Allocator).
- Non-Generational (Niegeneracyjny)
- GC w Go nie zarządza obiektami według generacji.
- Wszystkie obiekty należą do tej samej generacji.
- Escape Analysis (Analiza ucieczki)
- Go decyduje, czy obiekt ma być alokowany na stercie, czy na stosie, poprzez Escape Analysis.
- Z grubsza można przyjąć, że jeśli używane są wiszące wskaźniki (dangling pointers) lub interfejsy, obiekt jest alokowany na stercie.
Co jest istotne
GC w Go polega na przeszukiwaniu wszystkich obiektów, począwszy od korzenia, i wykonywaniu trójkolorowego oznaczania. Proces ten można w jednym zdaniu określić jako współbieżny algorytm przeszukiwania grafu z sortowaniem topologicznym. Jednakże, jest duże prawdopodobieństwo, że poszczególne obiekty znajdują się w różnych obszarach pamięci. Mówiąc wprost:
- Załóżmy, że istnieją dwa obszary pamięci oddalone od siebie o około 32MB.
- W tych dwóch obszarach pamięci alokowane jest po 5 obiektów.
- Obiekty A, B, C są w obszarze 1.
- Obiekty D, E są w obszarze 2.
- Kolejność odwołań obiektów to
A -> D -> B -> E -> C. - Kiedy rozpoczyna się GC, odwiedzane są kolejno A, D, B, E i C.
- W tym procesie, ponieważ A i D znajdują się w różnych obszarach pamięci, podczas przechodzenia od A do D konieczne jest przemieszczenie się między obszarami pamięci.
- Ten proces generuje tzw. koszt skoku pamięci (memory jump cost), obejmujący przemieszczanie się między obszarami pamięci i wypełnianie nowej linii cache. Znaczna część czasu CPU wykorzystywanego przez aplikację może być przeznaczona na takie operacje GC.
- Koszt ten jest generowany przez cały czas trwania GC.
Zatem, co jest problemem?
Takie działanie GC jest szczególnie niekorzystne w następujących przypadkach:
- Duża liczba rdzeni i duża pamięć
- GC w Go jest zasadniczo wykonywany współbieżnie.
- Jednakże, jeśli obszar pamięci jest duży, a obiekty są rozproszone, wiele rdzeni jednocześnie przeszukuje obiekty w różnych przestrzeniach pamięci.
- W tym procesie, jeśli magistrala między CPU a pamięcią nie jest wystarczająco szeroka, przepustowość pamięci może stać się wąskim gardłem.
- Ponadto, ze względu na fizyczną odległość, każde przeszukanie będzie wiązało się ze stosunkowo dużym opóźnieniem.
- Duża liczba drobnych obiektów
- Jeśli używacie w Go drzew lub grafów o dużej głębokości lub wielu dzieciach, GC musi przeszukać wszystkie te obiekty.
- Jeśli obiekty są rozproszone w różnych obszarach pamięci, z powodu pierwszego punktu wystąpi opóźnienie.
- Ponadto, jeśli jest dużo drobnych obiektów, GC musi je wszystkie przeszukać, co oznacza, że rdzenie CPU będą przeznaczać znaczną część swoich zasobów na pracę GC podczas jego wykonywania.
Aby rozwiązać te problemy, zespół Golang ogłosił GreenTea GC.
Nie masz już czasu na picie kolejnej zielonej herbaty
Co odbiera zieloną herbatę
Wydaje się, że za obszar, w którym można zastosować najszybsze rozwiązanie dla istniejącego GC, uznano lokalność pamięci. Oznacza to minimalizację skoków pamięci poprzez umieszczenie obiektów blisko siebie. Jednakże nie można narzucić wzorców programistom piszącym kod, a alokacja obiektów jest nieprzewidywalna w zależności od przepływu pracy.
Dlatego też metoda wybrana przez zespół Golang to Memory Span (zakres pamięci).
Czym jest Memory Span?
Memory Span to stosunkowo duży obszar pamięci alokowany w celu alokacji małych obiektów. Nowy GC nazwany GreenTea GC przeprowadza zbieranie śmieci właśnie na tym Memory Span. Szczegółowe działanie jest niemal identyczne z istniejącym Tri-Color Mark and Sweep.
Działanie GreenTea GC
Najpierw GreenTea GC alokuje Memory Span. Jak wcześniej wspomniano, jego rozmiar to 8 KiB, czyli jest on stosunkowo duży. Wewnątrz niego można alokować obiekty o maksymalnym rozmiarze 512 bajtów. Jest to wielkość, która, jak się wydaje, jest wystarczająca dla węzłów drzewa lub grafu, o których mówiliśmy, lub dla rozmiaru struktury, która normalnie "ucieka" na stertę. Obiekty o rozmiarze poniżej 512 bajtów są gromadzone w tym Memory Span za każdym razem, gdy "uciekają" na stertę, a gdy Memory Span się zapełni, alokowany jest nowy Memory Span.
Gdy następuje GC, GreenTea GC umieszcza te Memory Span w kolejce i sprawdza je sekwencyjnie. W tym procesie GreenTea GC wykorzystuje harmonogramowanie niemal identyczne z istniejącym modelem GMP. Zaimplementowano również mechanizmy takie jak kradzież pracy (work stealing). W każdym razie, worker, który pobiera Memory Span z kolejki, sprawdza wewnętrzne obiekty przydzielonego mu Memory Span. W tym procesie używany jest ten sam Tri-Color Mark and Sweep.
Jakie są korzyści?
Różnica w stosunku do istniejącego GC sprowadza się w zasadzie do jednego: jednostka, na której wykonywane jest GC, zmieniła się z obiektu na Memory Span. Dzięki temu GC zyskuje następujące korzyści:
- Lokalność pamięci: Ponieważ obiekty są zgromadzone w Memory Span, skoki pamięci są minimalizowane podczas przeszukiwania obiektów. Oznacza to maksymalne wykorzystanie cache CPU.
- Poprawa wydajności GC: Wykonywanie GC na poziomie Memory Span sprawia, że GC działa wydajniej w środowiskach wielordzeniowych.
- Optymalizacja alokacji pamięci: Ponieważ Memory Span jest alokowany o stałym rozmiarze, zmniejsza się narzut alokacji pamięci dla małych obiektów, a prawdopodobieństwo fragmentacji maleje. To zwiększa efektywność zwalniania pamięci.
Krótko mówiąc, od teraz możemy alokować obiekty o rozmiarze poniżej 512 bajtów częściej i z mniejszym obciążeniem umysłowym.
Należy jednak zauważyć, że istnieją obszary, w których jest to szczególnie korzystne:
- Struktury drzewiaste/grafowe: przypadek, gdy współczynnik rozgałęzienia (fan-out) jest wysoki i rzadko dochodzi do zmian.
- Drzewo B+, Trie, AST (Abstract Syntax Tree)
- Struktury danych przyjazne dla cache
- Przetwarzanie wsadowe: przepływ pracy z masową alokacją małych danych.
- Liczne małe obiekty tworzone podczas parsowania JSON
- Obiekty DAO z zestawów wyników baz danych
W takich przypadkach GreenTea GC może osiągnąć lepszą wydajność niż istniejący GC. Nie dotyczy to jednak wszystkich przypadków, a zwłaszcza, gdy obiekty są rozproszone w różnych obszarach pamięci, nadal trudno jest oczekiwać dramatycznego wzrostu wydajności.
Podsumowanie
Wygląda na to, że zespół Golang ma zamiar kontynuować ulepszanie GC w dłuższej perspektywie. Ten GreenTea GC można postrzegać jako drobną zmianę w małym obszarze i nie zastępuje on istniejącego GC. Jednak GreenTea GC jest interesującym przykładem, który pozwala nam zobaczyć problemy, z którymi zespół Golang się mierzy, lub które przewiduje. Imponująca jest również próba rozwiązania złożonego problemu poprzez dodanie stosunkowo prostego konceptu. Osobiście uważam, że jest to ciekawy przypadek.
GreenTea GC to funkcja eksperymentalna wprowadzana od Go 1.25. Można ją aktywować, używając zmiennej środowiskowej GOEXPERIMENT=greenteagc. Ponieważ ta funkcja jest wciąż eksperymentalna, wymaga odpowiednich testów przed użyciem w środowisku produkcyjnym.