Garbage collector
-=-=-=-=-=-=-=-=-=-
One day a student came to Moon and said: "I understand how
to make a better garbage collector. We must keep a reference count
of the pointers to each cons."
Moon patiently told the student the following story:
"One day a student came to Moon and said: 'I understand how to
make a better garbage collector...
-- vtip z MIT
(David Moon spolu s Tomem Knightem z větší části vytvořili lispové stroje.
Reference couting má potíže zejména s objekty ukazujícími samy na sebe)
Gabage collecting v překladu znamená "sběr smetí". Pokud je snad
někdo touto činností frustrován, může používat mnohem elegantněji
znějicí název "resource regeneration", což znamená úplně totéž.
Princip garbage collectingu je jednoduchý. Program data pouze
alokuje a o jejich uvolňování se vůbec nestará. V případě, že je
nedostatek paměti su aktivuje tajemný proces a automaticky určí,
které bloky je možné uvolnit. Tento tajemný proces pracuje plně
automaticky a od programátora nepotřebuje žádnou pomoc. Je jasné,
že takový přístup ušetří programátorovi mnoho starostí. Nestane se,
že by v programu zůstavaly zbytečné neuvolněné bloky či že
by program používal uvolněná data. Zejména u paraelních programů,
které využívají komplikované datové struktury a na kterých pracuje
více lidí často není jasné, kdo vlastně kdy a kde má co uvolňovat.
Zastánci garbage collectingu uvádějí, že vývoj programů se urychlí
v průměru o 30%, což rozhodně není malá hodnota.
Jediným problémem této skvělé myšlenky je, jak má tajemný proces
fungovat. Odpověď je ale poměrně snadná. Pokud se na paměť budete
dívat jako na graf, kde vrholy jsou bloky paměti a orientované hrany
určují ukazatele mezi bloky, snadno zjistíte, že bloky na které
neexistuje cesta po hranách se program už nemůže dostat (nemá odkud
by na ně získal ukazatel). Takové bloky mohou být tedy bez starostí
uvolněny.
Algoritmy GC
Pro samotné hledání takových bloků existuje hned několik
algoritmů. Každého začátečníka asi napadne použít tzv. "reference
couting", kde si každý blok pamatuje, kolik na něj ukazuje
ukazatelů. Pokud toto čítadlo klesne na 0, blok je uvolněn.
Tento algoritmus se na první pohled zdá být naprosto ideální:
uvolňuje bloky hned, jak je to možné, nepotřebuje příliš paměti ani
času procesoru. Přesto je zkušenějšími sběrači smetí zatracován.
Situace totiž není vůbec tak růžová, jak se na první pohled zdá.
Tento algoritmus vůbec neuvolní bloky, které jsou pospojovány
do kruhu. Přesto, že z venčí na ně nikdo neukazuje, jsou jejich
čítače nastaveny na 1. Dalším nezanedbatelným problémem je, že čítač
zabírá poměrně hodně paměti. Garbage collector se nejčastěji používá
na velmi malé bloky paměti, kde každý byte navíc škodí. Posledním
problémem je, že program sám se musí starat o udržování těchto
čítačů. V jazyce C na to neexistuje žádná automatická konstukce
a tak mohou vzniknout přesně stejné chyby jako u volání free. V C++
je v tomto ohledu situace lepší, přesto ale toto udržování čítačů
může védst k poměrně velkému zpomalení.
Z toho vyplývá, že problém garbage collectingu není až tak
jednoduchý, jak se na první pohled zdá. Většina lidí má tendenci
problém podcenit a udělat si na koleni nějaký collector, který sice
většinou funguje, ale rozhodně není optimální. Je lepší takovou
práci přenechat profesionálům.
Dvě základní metody garbage collectingu jsou: "mark and sweep"
a "copy propagation". Myšlenky obou těchto metod jsou jednoduché:
U metody mark and sweep se jednou za čas rekurzivně projdou všechny
bloky, na které má proces ukazatele a označkují se (mark). Potom se
neoznačkované bloky vymažou (sweep). Jedná se vlastně o procházení
grafem-bludištěm pomocí backtracingu. Kam se nedostanete, tam se
nedostane ani program. Metoda copy propagation pracuje na odlišném
principu. Ta postupně rekurzivně kopíruje všechny bloky do nové
paměti a obnovuje ukazatele na nová působiště. Takto se opět
překopírují pouze dostupné bloky.
Jakkoliv tyto metody vypadají hloupě a neefektivně, chovají
se velmi dobře. Výhoda mark and sweep oproti reference couting
spočívá zejména v tom, že uvolňuje i cykly a nepotřebuje místo
na čítač (značky mohou být udržovány v dočasném bitovém poli). Copy
porpagation ještě navíc zabraňuje fragmentaci paměti. Při samotném
kopírování je sice potřeba dočasně dvojnásobek paměti, ale kupodivu
statistiky ukazují, že u mark and sweep alokace je často promrhané
místo způsobené fragmentací paměti mnohem větší. I když v průměru
mark and sweep vede a proto je používanější.
Samozřejmě, že tyto metody mají i své nevýhody. Mezi největší
patří fakt, že pracují "návalově". Tedy že jednou za čas se program
zastaví a provádí garbage collection. Uživateli pak nezbývá, než
čekat. Je také těžké určit okamžik, kdy tuto návalovou akci udělat.
Zbytečně časté volání zdržuje, jinak se ale zbytečně mrhá pamětí.
Metoda "zavolej když je plná paměť" také neobstojí, protože v UNIXu
(a ani většině jiných modernějších OS)není možné určit, kdy vlastně
plná je. Proto je nutné dělat různé statistiky. Navíc existují
úpravy těchto algoritmů, které pracují inkrementálně. Tady při každé
alokaci udělají kus práce a program pak běží plynule. Navíc je
možné, aby garbage collector běžel paralelně s vlastním programem.
Více o algoritmech se můžete dočíst ve velmi pěkném článku
"Uniprocessor Garbage Collection Techniques" [Wilson].
Conservative GC
Jedním z hlavních důvodů, proč garbage collectory stále
patří zejména do světa interpretovaných jazyků je nutnost rozumět
datům programu. Popsané metody garbage collectingu musí být
schopny v bloku najít ukazatele a ty zpracovat. Navíc musí vědět,
na které bloky má program přístup přímo. V C je situace mnohem
komplikovanější. Garbage collector datům nerozumí a navíc počítat
s daty na zásobníku a v registrech. S tímto se vypořádává postup
zvaný konzervativní garbage collecting. Myšlenka je jednoduchá.
Garbage collector se nesnaží o přesné nalezení zapomenutých
bloků a všechny data na zásobníku, v registrech a v blocích jsou
potencionální ukazatele. Při značkovací části se bere v úvahu
každý z nich a pokud ukazuje do nejakého existujícího bloku,
blok se označí. Pokud se v tuto chvíli chytáte za hlavu, nezoufejte.
Situace není tak strašná, jak se zdá. Díky opravdu vysoké efektivitě
dnešních garbage collectorů zpomalení není až tak velké. Navíc
garbage collector u bloků umožňuje většinou nastavit, které jsou
atomické (další ukazatele už neobsahují) a na které se ukazuje jenom
na začátek (aby se snížila pravděpodobnost, že nějaký integer bude
chybně interpretován jako ukazatel doprostřed velkého bloku).
Samozřejmě, že je nutné program pro takový garbage collector
navrhnout. Ale i samotné nahrazení malocu a zrušení všech volání
free nepřináší zase tak strašné výsledky. Autoři [Costs] toto
zkusili u několika paměťově intensivních programů (gawk, perl apod.)
a výsledky oproti GNU malloc implementaci jsou asi následující:
Čas strávený ve funkcích alokátoru je u GNU malloc 17% a u garbage
collectoru 36%. Celkové zpomalení programu asi o 20%. Maximální
velikost použité paměti se zvýšila asi 2.5 krát.
Běžně ale při použití garbage collectingu nemusíte na free
úplně zapomenout a použivat jej v jednoduchých případech a garbage
collectoru přenechat pouze ty komplikovanější. Potom jsou poměry
mnohem příznivější.
Bezpečnost GC
Jakási "špinavost" konzervativních Garbage Collectorů přináší
další problém: najde GC operavdu všechny ukazatele? Ve většině
případů program opravdu uchovává nějaký ukazatel na blok. ANSI
C má velmi striktní pravidla pro práci s ukazatelem (jak jsem už
popisoval, zakazuje například i udržovat ukazatele mimo alokovanou
paměť) a proto většina programů odpovídajících ANSI C je korekní.
Je ale nutné se vyvarovat zejména nasledujícím situacím:
- ukládat a nahrávat ukazatele se souboru (nebo posílat po síti)
- použití memcpy pro zkopírování ukazatelů na pozici, jejíž adresa
není dělitelná velikostí ukazatele.
- přetypovávání ukazatelů na integery
- udržování ukazatelů před daný blok (to je poměrně častý problém,
ale takové ukazatele stejně neodpovídají ANSI C)
Jiným problémem jsou ale překladače. Dobře optimalizující
překladač může udělat nějaký trik a ukazatel schovat. Překladače
jsou tedy 100% spolehlivé jenom bez optimalizací. Pouze ty nejlépe
optimalizující překladače porušují tyto pravidla a to jenom ve velmi
vzácných případech. Přesto, pokud chcete mít jistotu, je dobré si
přečíst [Boehm96]. Obsahuje podrobný návod, jak zabránit těmto
problémům pod GCC, včetně preprocesoru pro kód, který udělá změny
automaticky. (a zpomalí kód přibližně o 10%). V boudocnosti vzhledem
k rostoucí popularitě těchto collectorů bude možná přidán přepínač
do GCC, který to zařídí sám.
Boehmův garbage collector pro C a C++
Asi nejrozšířenějším garbage collectorem pro C je gc od pana
Hanse J. Boehma. Je distribuován pod licencí kompatibilní s GPL
a dostupný na http://reality.sgi.com/employees/boehm_mti/gc.html.
Patří mezi velmi kvalitní konzervatavní garbage collecotry.
Implementuje algoritmus Mark and Sweep a na některých platformách
i inkrementální garbage collecting (práce se rovnoměrně rozdělí
mezi jednotlivé volání malloc). Má velice kvalitní podporu pro
multithreading (může probíhat několik alokací zároveň) a volání
finalizačních funkcí (funkce, které se zavolají pokud se objekt
uvolňuje). Samotný garbage collector sice nelze implementovat
přenositelně, ale má podporu pro velké množství platforem
(GNU/Linux, UNIXové systémy, DJGPP, Mac, Win32 apod.) a threadových
knihoven (protože standard pthreads nemá některé funkce, které GC
potřebuje, je nutné psát podporu pro každou implementaci zvlášť).
Je možné jej přeložit v mnoha režimech. Pokud jej chcete použít
pro existující kód, je možné jej přeložit tak, aby nahradil funkce
malloc, realloc a free. Pokud má Váš kód chyby, je také možné
nastavit flag, aby se free ignorovalo. Tak je možné použít GC
pouze pro kontrolu a hledání zapomenutých bloků a ve výsledném kódu
jej vůbec nepoužít. To ale není cílem tohoto programu a proto má
i vlastní interface. To se skládá z následujících volání:
void * GC_malloc(size_t nbytes)
podobně jako malloc alokuje n bajtů
void * GC_malloc_atomic(size_t nbytes)
Toto je dobré použít pro oblasti, které neobsahují další
ukazatele. Mark průchod blok potom ignoruje a ušetří si práci
void * GC_malloc_uncollectable(size_t nbytes)
Funguje stejně jako GC_malloc, ale výsledný blok nemůže
být uvolněn. Narozdíl od systémového malloc ale GC o paměti ví
a zkontroluje ji na případně ukazatele.
void * GC_realloc(void *old, size_t new_size)
Změna velikosti bloku
void GC_free(void *dead)
Uvolnění bloku
void * GC_malloc_ignore_off_page(size_t nbytes)
void * GC_malloc_atomic_ignore_off_page(size_t nbytes)
Tyto funkce mají stejnou funkci jako GC_malloc
a GC_malloc_atomic. Při mark průchodu se ale berou v úvahu pouze
ukazatele do prvních 512 bajtů bloku (takové ukazatele by měly
být typu volatile, aby je optimizer neposunul). Toto je doporučená
metoda pro alokaci bloků nad 100KB, aby se zabránilo tomu, že mark
průchod najde nějaký integer, co interpretovaný jako pointer ukazuje
do bloku.
void GC_gcollect(void)
Explicitně zavola garbage collector.
void GC_enable_incremental(void)
Zapne inkrementální mód
void GC_register_finalizer(...)
Nastavení finalizační funkce pro objekt
GC_warn_proc GC_set_warn_proc(GC_warn_proc p)
Nastavení funkce pro vypisování warningů.
Garbage collector navíc obsahuje interface pro C++ (new, delete
apod.) a speciální knihovnu pro práci s velkými stringy (cord),
která nejenom pěkně demonstruje výhody garbage collectingu ale je
i poměrně praktická. Jako příklad použití knihovny je ještě přibalen
ukázkový editor pro curses a Win32.
výheň