GoSuda

Chvilka klidu s citronovým... zeleným čajem, který Go runtime nestihne vzít: GreenTea GC

By snowmerak views ...

Proč vzniká další GC?

Proč existující GC

Současný GC v Go lze popsat následujícími pojmy.

  • concurrent tri-color mark and sweep
    • Pro sledování stavu objektů používá celkem tři barvy (bílou, šedou, černou).
      • Bílá: objekt, který ještě nebyl navštíven
      • Šedá: objekt, který byl navštíven, ale nebyly navštíveny všechny jeho potomky
      • Černá: objekt, jehož všichni potomci byli navštíveni
      • Po dokončení procházení jsou všechny bílé objekty uvolněny.
    • Pro ochranu paměti vytvořené během GC se používá Write Barrier.
      • Doba zapnutí a vypnutí Write Barrier tvoří podstatnou část takzvané fáze Stop-The-World (dále jen STW).
    • Tento proces probíhá souběžně.
  • No Compaction
    • GC v Go neprovádí compaction.
    • Může docházet k fragmentaci paměti.
      • Objekty do 32 KB však využívají per-P cache alokátoru paměti jazyka Go, čímž se fragmentace minimalizuje.
  • Non-Generational
    • GC v Go nespravuje objekty podle generací.
    • Všechny objekty patří do stejné generace.
  • Escape Analysis
    • Go pomocí Escape Analysis rozhoduje, zda je objekt alokován na heapu nebo na zásobníku.
    • Zhruba řečeno, pokud se používá dangling pointer nebo rozhraní (interface), lze předpokládat, že je objekt alokován na heapu.

Co je důležité

GC v Go provádí tri-color mark tak, že prochází všechny objekty počínaje kořeny. Tento proces lze v jedné větě popsat jako souběžné prohledávání grafu v topologickém pořadí. Objekty se však s velkou pravděpodobností nacházejí v různých oblastech paměti. Konkrétně řečeno:

  1. Předpokládejme, že existují dvě oblasti paměti vzdálené přibližně 32 MB.
  2. V každé z těchto oblastí je alokováno pět objektů.
    1. Objekty A, B, C jsou v oblasti 1
    2. Objekty D, E jsou v oblasti 2
  3. Pořadí referencí objektů je A -> D -> B -> E -> C.
  4. Když GC začne, navštíví A, poté D, poté B, poté E a nakonec C.
  5. Protože A a D se nacházejí v různých oblastech paměti, je při návštěvě A a následně D nutné přejít mezi oblastmi paměti.
  6. Tento proces přechodu mezi oblastmi paměti a plnění nových cache lines způsobuje takzvané náklady na skok v paměti (memory jump). Významná část času CPU aplikace může být přidělena právě této práci GC.
  7. Tyto náklady vznikají kontinuálně po celou dobu běhu GC.

Jaký je problém?

Takové chování GC je zásadně problematické v následujících případech.

  • Velký počet jader a velká paměť
    • GC v Go se standardně provádí souběžně.
    • Pokud je však paměťová oblast rozsáhlá a objekty jsou rozptýleny, několik jader souběžně prohledává objekty v různých částech paměti.
    • Pokud sběrnice mezi CPU a pamětí není dostatečně široká, může se šířka pásma paměti stát úzkým hrdlem.
    • Navíc, vzhledem ke skutečné fyzické vzdálenosti, je každé jednotlivé prohledání poměrně výrazným zpožděním.
  • Velké množství drobných objektů
    • Pokud v Go provozujete hluboké nebo rozvětvené stromy či grafy s mnoha potomky, GC musí prohledat všechny tyto objekty.
    • Pokud jsou tyto objekty rozptýleny v různých oblastech paměti, vzniká zpoždění z prvního důvodu.
    • Také, pokud je drobných objektů mnoho, GC je musí všechny prohledat, a proto během běhu GC věnuje jádra CPU značnou část své kapacity této práci.

Pro vyřešení těchto problémů tým Golang představil GreenTea GC.

Už nemáte čas na další zelený čaj

Co zelený čaj odnímá

Oblastí, na kterou lze aplikovat nejrychlejší řešení známé z existujícího GC, se zdá být lokalita paměti. To znamená uspořádat objekty tak, aby byly blízko sebe, a minimalizovat tak skoky v paměti. Programátorův způsob psaní kódu však nelze vynutit a alokace objektů je při různých pracovních postupech nepředvídatelná.

Tým Golang proto zvolil přístup založený na memory span (paměťovém rozsahu).

Co je memory span?

Memory span je místo, kde se po přidělení poměrně velké paměťové oblasti alokují malé objekty. Nový GC nazvaný GreenTea GC provádí sběr odpadu právě nad těmito memory spans. Podrobné chování je téměř shodné s existujícím Tri-Color Mark and Sweep.

Chování GreenTea GC

Nejprve GreenTea GC přiděluje memory span. Jeho velikost je, jak bylo uvedeno dříve, 8 KiB, což je poměrně značná velikost. Do něj lze alokovat objekty o velikosti nejvýše 512 bytes. Velikost uzlů stromů či grafů z uvedeného příkladu nebo běžných struktur, které unikají na heap, se jen obtížně dostane nad tuto hranici. Objekty do 512 bytes se při každém úniku na heap ukládají do tohoto memory span a jakmile je tento span plný, přiděluje se nový memory span.

Když nastane GC, GreenTea GC ukládá tyto memory spans do fronty a kontroluje je postupně. Při tom GreenTea GC používá plánování velmi podobné existujícímu modelu GMP. Je implementována také oblast jako work stealing. Worker, který vybere memory span z fronty, prohledá objekty uvnitř přiděleného memory span. Přitom se stejně jako dříve používá Tri-Color Mark and Sweep.

Jaké jsou z toho výhody?

Z pohledu celého procesu se rozdíl oproti existujícímu GC shrnuje do jediné věci: jednotkou, nad kterou GC v jednom kroku pracuje, se místo objektu stal memory span. Díky tomu GC přináší následující výhody.

  • Lokalita paměti: Protože objekty jsou seskupeny v memory span, při jejich procházení se minimalizují skoky v paměti. To znamená, že lze maximálně využít CPU cache.
  • Zlepšení výkonu GC: Provádění GC po jednotkách memory span umožňuje, aby GC efektivněji fungoval ve víceprocesorovém prostředí.
  • Optimalizace alokace paměti: Protože memory span má pevnou velikost, režie alokace malých objektů klesá a snižuje se pravděpodobnost fragmentace. To zvyšuje efektivitu uvolňování paměti.

Stručně řečeno, od nynějška můžeme objekty do 512 bytes alokovat častěji a bez obav.

Přesto existují určité oblasti, ve kterých je tento přístup výhodný.

  • Struktury stromů/grafů: případy s vysokým fan-outem, u nichž se změny vyskytují jen zřídka
    • B+ stromy, Trie, AST (Abstract Syntax Tree)
    • Datové struktury přátelské k cache
  • Dávkové zpracování: pracovní postupy hromadné alokace malých dat
    • Mnoho malých objektů vznikajících při parsování JSON
    • DAO objekty z výsledných množin databázových dotazů

V těchto případech může GreenTea GC dosáhnout lepšího výkonu než existující GC. Nelze jej však uplatnit ve všech situacích a zejména tam, kde jsou objekty rozptýleny v různých oblastech paměti, nelze stále očekávat dramatické zlepšení výkonu.

Závěr

Tým Golang pravděpodobně plánuje GC i nadále dlouhodobě vylepšovat. Tento GreenTea GC lze považovat za drobnou změnu v malém rozsahu a nenahrazuje existující GC. GreenTea GC je však zajímavým příkladem, z něhož je patrné, jaké problémy tým Golang řeší nebo předpokládá. Ačkoli jde o překvapivě složitý problém, pozoruhodný je pokus o jeho vyřešení přidáním relativně jednoduchého konceptu. Osobně to považuji za zajímavý případ.

GreenTea GC je experimentální funkce zavedená od Go 1.25. Lze ji aktivovat nastavením proměnné prostředí GOEXPERIMENT=greenteagc. Tato funkce je zatím experimentální, proto je před nasazením v produkčním prostředí nutné důkladné testování.

Reference