GoSuda

Chwila spokoju za filiżanką zielonej herbaty, którą odbierze środowisko uruchomieniowe Go: GreenTea GC

By snowmerak views ...

Dlaczego pojawia się kolejny GC?

Dlaczego istniejący GC

Obecny GC w Go można opisać następująco.

  • concurrent tri-color mark and sweep
    • Wykorzystuje łącznie 3 kolory (biały, szary, czarny) do śledzenia stanu obiektów.
      • Biały: obiekt, który jeszcze nie został odwiedzony
      • Szary: obiekt, który został odwiedzony, ale nie wszystkie jego obiekty potomne zostały odwiedzone
      • Czarny: obiekt, którego wszystkie obiekty potomne zostały odwiedzone
      • Po zakończeniu przechodzenia wszystkie białe obiekty są zbierane.
    • Używa Write Barrier do ochrony pamięci tworzonej podczas działania GC.
      • Czas włączania i wyłączania Write Barrier stanowi znaczną część tzw. Stop-The-World (dalej STW).
    • Ten proces wykonywany jest współbieżnie.
  • No Compaction
    • GC w Go nie wykonuje kompaktowania.
    • Może dochodzić do fragmentacji pamięci.
      • Jednak obiekty o rozmiarze do 32 KB wykorzystują per-P cache alokatora pamięci języka Go, co minimalizuje fragmentację.
  • Non-Generational
    • GC w Go nie zarządza obiektami według generacji.
    • Wszystkie obiekty należą do tej samej generacji.
  • Escape Analysis
    • Go za pomocą Escape Analysis decyduje, czy obiekt zostanie przydzielony na stercie (heap), czy na stosie.
    • W przybliżeniu można przyjąć, że jeśli występuje wiszący wskaźnik (dangling pointer) lub używany jest interfejs, obiekt jest przydzielany na stercie.

Najważniejsza kwestia

GC w Go przeszukuje wszystkie obiekty, zaczynając od korzeni (roots), i wykonuje trójkolorowe znakowanie. Ten proces można w jednym zdaniu określić jako współbieżny algorytm przeszukiwania grafu z sortowaniem topologicznym. Jednak każdy obiekt bardzo prawdopodobnie znajduje się w innym obszarze pamięci. Mówiąc wprost:

  1. Załóżmy, że istnieją dwa obszary pamięci oddalone od siebie o około 32 MB.
  2. W każdym z tych obszarów pamięci przydzielono po 5 obiektów.
    1. Obiekty A, B, C znajdują się w obszarze 1.
    2. Obiekty D, E znajdują się w obszarze 2.
  3. Kolejność referencji obiektów wynosi A -> D -> B -> E -> C.
  4. Gdy rozpocznie się GC, odwiedzane są kolejno A, D, B, E i C.
  5. Ponieważ A i D znajdują się w różnych obszarach pamięci, przy odwiedzaniu A, a następnie D, konieczne jest przejście między obszarami pamięci.
  6. W tym procesie, przez przechodzenie między obszarami pamięci i ponowne wypełnianie linii pamięci podręcznej (cache line), powstaje tzw. koszt skoku pamięci (memory jump cost). Znaczna część czasu CPU wykorzystywanego przez aplikację może zostać przeznaczona na te operacje GC.
  7. Ten koszt powstaje nieprzerwanie przez cały czas trwania GC.

Dlaczego to problem?

Takie zachowanie GC jest zabójcze w następujących przypadkach.

  • Wiele rdzeni i duży rozmiar pamięci
    • GC w Go domyślnie działa współbieżnie.
    • Jednak jeśli obszar pamięci jest rozległy, a obiekty są rozproszone, wiele rdzeni równocześnie przeszukuje obiekty w różnych obszarach pamięci.
    • W takim przypadku, 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, ponieważ odległości fizyczne są rzeczywiste, każde przeszukanie może powodować stosunkowo duże opóźnienie.
  • Wiele drobnych obiektów
    • Jeśli w Go obsługujecie głębokie lub mocno rozgałęzione drzewa bądź grafy, GC musi przeszukać wszystkie te obiekty.
    • Jeśli obiekty te są rozmieszczone w różnych obszarach pamięci, opóźnienie wynikające z pierwszej przyczyny również się pojawia.
    • Ponadto, gdy obiektów jest wiele, GC musi przeszukać wszystkie z nich, przez co w trakcie działania GC rdzenie CPU poświęcają znaczne zasoby na pracę GC.

Aby rozwiązać te problemy, zespół Golang zaprezentował GreenTea GC.

Nie masz już czasu na kolejną herbatę zieloną

Co odbiera zieloną herbatę

Głównym obszarem, w którym najszybsze rozwiązanie znane z istniejącego GC może zostać zastosowane, wydaje się być lokalność pamięci (memory locality). Oznacza to umieszczanie obiektów blisko siebie w celu zminimalizowania skoków pamięci. Nie można jednak wymusić na programistach określonego wzorca pisania kodu, a alokacja obiektów zależy od przepływu pracy i nie jest przewidywalna.

Być może dlatego zespół Golang wybrał podejście oparte na spanie pamięci (Memory Span).

Czym jest span pamięci?

Span pamięci to obszar, w którym przydzielana jest stosunkowo duża porcja pamięci, a następnie w jego obrębie alokowane są małe obiekty. Nowy GC o nazwie GreenTea GC wykonuje zbieranie śmieci właśnie na tych spanach pamięci. Szczegóły działania są niemal identyczne z istniejącym Tri-Color Mark and Sweep.

Działanie GreenTea GC

Najpierw GreenTea GC alokuje span pamięci. Jego rozmiar, jak wspomniano wcześniej, wynosi 8 KiB, co stanowi pewien rozsądny rozmiar. W jego obrębie można przydzielić obiekty o rozmiarze do 512 bajtów. Rozmiar węzłów wspomnianych drzew lub grafów, a także zwykłych struktur uciekających na stertę, raczej nie przekracza tej wartości. Obiekty o rozmiarze do 512 bajtów są umieszczane w tym spanie za każdym razem, gdy uciekają na stertę, a gdy span się zapełni, alokowany jest nowy span pamięci.

Gdy zachodzi GC, GreenTea GC ustawia te spany pamięci w kolejce i sprawdza je sekwencyjnie. W tym procesie GreenTea GC wykorzystuje harmonogramowanie niemal analogiczne do dotychczasowego modelu GMP. Zaimplementowano również mechanizmy takie jak kradzież pracy (work stealing). W każdym razie worker, który pobrał span z kolejki, sprawdza obiekty wewnątrz przydzielonego mu spanu. W tym procesie używany jest ten sam Tri-Color Mark and Sweep.

Jakie są z tego korzyści?

Różnica względem dotychczasowego GC sprowadza się, ogólnie rzecz biorąc, do jednej rzeczy: jednostką wykonywania GC przy jednym przebiegu stał się span pamięci zamiast obiektu. Dzięki temu GC zyskuje następujące korzyści.

  • Lokalność pamięci: ponieważ obiekty są zgromadzone w spanie pamięci, podczas przeszukiwania obiektów skoki pamięci są zminimalizowane. Oznacza to, że można maksymalnie wykorzystać pamięć podręczną CPU.
  • Poprawa wydajności GC: dzięki wykonywaniu GC w jednostkach spanów pamięci GC działa bardziej efektywnie w środowisku wielordzeniowym.
  • Optymalizacja alokacji pamięci: ponieważ spany pamięci są przydzielane o stałym rozmiarze, narzut alokacji małych obiektów maleje, a możliwość fragmentacji ulega zmniejszeniu. Zwiększa to również efektywność zwalniania pamięci.

Krótko mówiąc, od teraz możemy częściej i z lżejszym sercem alokować obiekty o rozmiarze do 512 bajtów.

Warto jednak zauważyć, że również tutaj istnieją pewne korzystne przypadki.

  • Struktury drzewiaste/grafowe: sytuacje, w których fan-out jest wysoki, a zmiany zachodzą rzadko
    • B+ drzewa, Trie, AST (Abstract Syntax Tree)
    • Struktury danych przyjazne pamięci podręcznej
  • Przetwarzanie wsadowe: przepływy pracy wymagające masowej alokacji małych danych
    • Liczne małe obiekty tworzone podczas parsowania JSON
    • Obiekty DAO z wyników zapytań do bazy danych

W takich przypadkach GreenTea GC może osiągać lepszą wydajność niż dotychczasowy GC. Nie dotyczy to jednak wszystkich sytuacji, a zwłaszcza w przypadku, gdy obiekty są rozproszone w różnych obszarach pamięci, nadal trudno oczekiwać dramatycznej poprawy wydajności.

Zatem

Zespół Golang prawdopodobnie zamierza w dłuższej perspektywie stale ulepszać GC. Obecny GreenTea GC można uznać za drobną zmianę w wąskim zakresie i nie zastępuje on dotychczasowego GC. Jednak GreenTea GC wydaje się interesującym przykładem, pozwalającym zajrzeć w problemy, z którymi zmaga się zespół Golang lub które przewiduje. Choć problem jest zaskakująco złożony, podejście polegające na rozwiązaniu go przez dodanie stosunkowo prostej koncepcji również zrobiło na mnie wrażenie. Osobiście uważam to za ciekawy przypadek.

GreenTea GC to funkcja eksperymentalna wprowadzana od Go 1.25. Można ją aktywować, używając zmiennej środowiskowej GOEXPERIMENT=greenteagc. Ponieważ funkcja ta ma wciąż charakter eksperymentalny, przed użyciem w środowisku produkcyjnym wymagane są dokładne testy.

Referencje