Mechanismus garbage collection platformy Java výrazně zvyšuje produktivitu vývojářů, ale špatně implementovaný garbage collector může nadměrně spotřebovávat prostředky aplikace. V tomto třetím článku seriálu o optimalizaci výkonu JVM nabízí Eva Andreassonová začátečníkům v Javě přehled paměťového modelu platformy Java a mechanismu GC. Poté vysvětluje, proč je fragmentace (a nikoli GC) hlavním “gotcha!” výkonu aplikací v Javě a proč jsou generační garbage collection a kompakce v současnosti předními (i když ne nejinovativnějšími) přístupy ke správě fragmentace haldy v aplikacích v Javě.

Garbage collection (GC) je proces, jehož cílem je uvolnit obsazenou paměť, na kterou se již neodkazuje žádný dosažitelný objekt Javy, a je základní součástí systému dynamické správy paměti virtuálního stroje Java (JVM). V typickém cyklu garbage collection jsou zachovány všechny objekty, na které je stále odkazováno, a které jsou tedy dosažitelné. Místo obsazené dříve odkazovanými objekty je uvolněno a rekultivováno, aby bylo možné alokovat nové objekty.

Chcete-li porozumět garbage collection a různým přístupům a algoritmům GC, musíte nejprve vědět několik věcí o paměťovém modelu platformy Java.

Garbage collection a paměťový model platformy Java

Pokud na příkazovém řádku aplikace Java zadáte možnost spuštění -Xmx (například: java -Xmx:2g MyApp), paměť se přiřadí procesu Java. Tato paměť se označuje jako halda Javy (nebo jen halda). Jedná se o vyhrazený adresový prostor paměti, ve kterém budou alokovány všechny objekty vytvořené vaším programem Java (nebo někdy JVM). Jak váš program Java neustále běží a alokuje nové objekty, zaplní se halda Java (tedy tento adresní prostor).

Koneckonců se halda Java zaplní, což znamená, že alokující vlákno nemůže najít dostatečně velký po sobě jdoucí úsek volné paměti pro objekt, který chce alokovat. V tomto okamžiku JVM určí, že je třeba provést garbage collection, a oznámí to garbage collectoru. Sběr odpadu může být také spuštěn, když program Java zavolá System.gc(). Použití System.gc() nezaručuje, že dojde ke sběru odpadu. Před spuštěním jakéhokoli garbage collection mechanismus GC nejprve určí, zda je bezpečné jej spustit. Bezpečné je zahájit garbage collection, když jsou všechna aktivní vlákna aplikace v bezpečném bodě, který to umožňuje, např. jednoduše vysvětleno, že by bylo špatné zahájit garbage collection uprostřed probíhající alokace objektu nebo uprostřed provádění sekvence optimalizovaných instrukcí procesoru (viz můj předchozí článek o překladačích), protože byste mohli ztratit kontext a tím pokazit konečné výsledky.

A garbage collector by nikdy neměl reclaimovat aktivně odkazovaný objekt; kdyby tak učinil, porušil by specifikaci virtuálního stroje Java. Od garbage collectoru se také nevyžaduje, aby okamžitě sbíral mrtvé objekty. Mrtvé objekty jsou nakonec sebrány během následujících cyklů garbage collection. I když existuje mnoho způsobů implementace garbage collection, tyto dva předpoklady platí pro všechny varianty. Skutečným úkolem garbage collection je identifikovat vše, co je živé (stále odkazované), a získat zpět veškerou nereferencovanou paměť, ale přitom tak učinit bez dopadu na běžící aplikace více, než je nutné. Sběrač odpadků má tedy dva mandáty:

1. Rychle uvolnit nereferencovanou paměť, aby byla uspokojena alokační rychlost aplikace a nedošla jí paměť.
2. Znovu získat paměť a zároveň co nejméně ovlivnit výkon (např, latenci a propustnost) běžící aplikace.

Dva druhy garbage collection

V prvním článku této série jsem se dotkl dvou hlavních přístupů k garbage collection, kterými jsou reference counting a tracing collectors. Tentokrát se každému z těchto přístupů budu věnovat hlouběji a poté představím některé algoritmy používané k implementaci trasovacích kolektorů v produkčních prostředích.

Kolektory počítání referencí

Kolektory počítání referencí sledují, kolik referencí ukazuje na jednotlivé objekty Javy. Jakmile počet pro objekt dosáhne nuly, lze paměť okamžitě získat zpět. Tento okamžitý přístup k regenerované paměti je hlavní výhodou přístupu ke sběru odpadu pomocí počítání referencí. Pokud jde o držení nereferenční paměti, je zde velmi malá režie. Udržování všech aktuálních počtů referencí však může být poměrně nákladné.

Hlavním problémem sběračů počítajících reference je udržování přesných počtů referencí. Dalším známým problémem je složitost spojená se zpracováním kruhových struktur. Pokud se dva objekty navzájem odkazují a žádný živý objekt na ně neodkazuje, jejich paměť nebude nikdy uvolněna. Oba objekty zůstanou navždy s nenulovým počtem. Zpětné získání paměti spojené s kruhovými strukturami vyžaduje rozsáhlou analýzu, což přináší nákladnou režii algoritmu, a tedy i aplikace.

Sledovací kolektory

Sledovací kolektory jsou založeny na předpokladu, že všechny živé objekty lze najít iterativním sledováním všech referencí a následných referencí z počáteční množiny známých živých objektů. Počáteční množina živých objektů (nazývaných kořenové objekty nebo zkráceně jen kořeny) je lokalizována analýzou registrů, globálních polí a zásobníkových rámců v okamžiku, kdy je spuštěn garbage collection. Po identifikaci počáteční sady živých objektů sleduje kolektor trasování reference z těchto objektů a řadí je do fronty, aby byly označeny jako živé a následně byly trasovány jejich reference. Označení všech nalezených odkazovaných objektů jako živých znamená, že se známá množina živých objektů v průběhu času zvětšuje. Tento proces pokračuje, dokud nejsou nalezeny a označeny všechny odkazované (a tedy i všechny živé) objekty. Jakmile trasovací kolektor najde všechny živé objekty, rekultivuje zbývající paměť.

Trasovací kolektory se od kolektorů počítajících reference liší tím, že mohou pracovat s kruhovými strukturami. Háček u většiny trasovacích kolektorů spočívá ve fázi označování, která s sebou nese čekání, než je možné získat zpět nereferenční paměť.

Trasovací kolektory se nejčastěji používají pro správu paměti v dynamických jazycích; pro jazyk Java jsou zdaleka nejrozšířenější a již mnoho let se komerčně osvědčují v produkčních prostředích. Ve zbytku tohoto článku se zaměřím na trasovací kolektory a začnu některými algoritmy, které tento přístup ke sběru odpadu implementují.

Algoritmy trasovacích kolektorů

Kopírování a mark-and-sweep garbage collection nejsou nové, ale stále jsou to dva nejběžnější algoritmy, které dnes implementují trasovací sběr odpadu.

Kopírovací kolektory

Tradiční kopírovací kolektory používají od-prostor a do-prostor — to znamená dva samostatně definované adresové prostory haldy. V okamžiku sběru odpadu jsou živé objekty v oblasti definované jako from-space zkopírovány do dalšího volného prostoru v oblasti definované jako to-space. Jakmile jsou všechny živé objekty v prostoru from přesunuty ven, může být celý prostor from regenerován. Při opětovném zahájení alokace se začíná od prvního volného místa v oblasti to-space.

Ve starších implementacích tohoto algoritmu si oblasti from-space a to-space vyměňují místa, což znamená, že po zaplnění oblasti to-space se opět spustí garbage collection a z oblasti to-space se stane oblast from-space, jak ukazuje obrázek 1.

Modernější implementace kopírovacího algoritmu umožňují přiřadit jako to-space a from-space libovolné adresní prostory v rámci haldy. V těchto případech si nemusí nutně vyměňovat umístění mezi sebou; spíše se každý z nich stává dalším adresním prostorem v rámci haldy.

Jednou z výhod kopírovacích sběračů je, že objekty jsou v to-prostoru alokovány těsně vedle sebe, což zcela eliminuje fragmentaci. Fragmentace je častým problémem, se kterým se potýkají ostatní algoritmy pro vybírání odpadu; o tom se zmíním později v tomto článku.

Nevýhody kopírovacích kolektorů

Kopírovací kolektory jsou obvykle stop-the-world kolektory, což znamená, že po dobu, kdy je vybírání odpadu v cyklu, nelze provádět žádnou práci aplikace. Při implementaci stop-the-world platí, že čím větší oblast je třeba kopírovat, tím větší bude dopad na výkon aplikace. To je nevýhoda pro aplikace, které jsou citlivé na dobu odezvy. U kopírovacího kolektoru je také třeba vzít v úvahu nejhorší možný scénář, kdy je vše živé v prostoru from-space. Vždy musíte ponechat dostatek prostoru pro přesun živých objektů, což znamená, že prostor to-space musí být dostatečně velký, aby se do něj vešlo vše z prostoru from-space. Kopírovací algoritmus je kvůli tomuto omezení mírně paměťově neefektivní.

Kolektory mark-and-sweep

Většina komerčních JVM nasazených v podnikových produkčních prostředích používá kolektory mark-and-sweep (nebo marking), které nemají takový dopad na výkon jako kopírovací kolektory. Mezi nejznámější značkovací kolektory patří CMS, G1, GenPar a DeterministicGC (viz zdroje).

Kolektor mark-and-sweep sleduje reference a každý nalezený objekt označí “živým” bitem. Obvykle nastavený bit odpovídá adrese nebo v některých případech sadě adres na haldě. Živý bit může být například uložen jako bit v záhlaví objektu, bitový vektor nebo bitová mapa.

Poté, co je vše označeno jako živé, nastoupí fáze sweep. Pokud má kolektor fázi sweep, obsahuje v podstatě nějaký mechanismus pro opětovné procházení haldy (nejen živé množiny, ale celé délky haldy), aby našel všechny neoznačené kusy po sobě jdoucích adresních prostorů paměti. Neoznačená paměť je volná a rekultivovatelná. Kolektor pak tyto neoznačené kousky spojí do uspořádaných volných seznamů. V garbage collectoru mohou být různé seznamy volné paměti – obvykle organizované podle velikosti kusů. Některé JVM (například JRockit Real Time) implementují kolektory s heuristikou, která dynamicky řadí seznamy podle velikosti na základě profilovacích dat aplikace a statistik o velikosti objektů.

Po dokončení fáze procházení začne alokace znovu. Nové alokační oblasti jsou alokovány ze seznamů volných míst a kousky paměti by mohly odpovídat velikostem objektů, průměrným velikostem objektů na ID vlákna nebo aplikačně vyladěným velikostem TLAB. Přizpůsobení volného prostoru více velikosti toho, co se aplikace snaží alokovat, optimalizuje paměť a může pomoci snížit fragmentaci.

Nevýhody mark-and-sweep kolektorů

Fáze mark je závislá na množství živých dat na haldě, zatímco fáze sweep je závislá na velikosti haldy. Vzhledem k tomu, že je třeba počkat na dokončení fáze mark i sweep, aby bylo možné získat zpět paměť, způsobuje tento algoritmus problémy s časem pauzy u větších hromad a větších sad živých dat.

Jedním ze způsobů, jak můžete pomoci aplikacím s velkou spotřebou paměti, je použití možností ladění GC, které se přizpůsobí různým scénářům a potřebám aplikací. Ladění může v mnoha případech pomoci alespoň oddálit některou z těchto fází, aby se nestala rizikem pro vaši aplikaci nebo dohody o úrovni služeb (SLA). (Smlouva SLA stanoví, že aplikace splní určitou dobu odezvy aplikace – tj. latenci.) Ladění pro každou změnu zátěže a modifikaci aplikace je však opakovaným úkolem, protože ladění platí pouze pro určitou pracovní zátěž a míru přidělování.

Implementace mark-and-sweep

Existují nejméně dva komerčně dostupné a osvědčené přístupy k implementaci mark-and-sweep collection. Jedním z nich je paralelní přístup a druhým je souběžný (nebo převážně souběžný) přístup.

Paralelní sběrače

Paralelní sběr znamená, že prostředky přidělené procesu jsou pro účely sběru odpadu využívány paralelně. Většina komerčně implementovaných paralelních kolektorů jsou monolitické stop-the-world kolektory — všechna aplikační vlákna jsou zastavena, dokud není dokončen celý cyklus sběru odpadků. Zastavení všech vláken umožňuje efektivní paralelní využití všech prostředků k dokončení sběru odpadků prostřednictvím fází mark a sweep. To vede k velmi vysoké efektivitě, která obvykle vede k vysokým výsledkům v benchmarcích propustnosti, jako je SPECjbb. Pokud je pro vaši aplikaci zásadní propustnost, je paralelní přístup vynikající volbou.