Andreas Rumpf (Araq), autor programovacího jazyka Nim, oznámil nový algoritmus správy paměti YRC (vyslovuje se „Ürk“), který řeší jeden z klíčových problémů stávajících mechanismů v Nimu: neschopnost správně zpracovávat cyklické reference, které překračují hranice vláken.
Před YRC měly Nimovy navrhované algoritmy správy paměti následující omezení: ARC nepodporoval multithreading ani zpracování cyklů; Atomic ARC byl thread-safe, ale nezpracovával cyklické reference; ORC zpracovával cyklické reference, ale mohl tak činit správně pouze v rámci jednoho vlákna (při použití sdílených referencí mezi vlákny docházelo k únikům paměti).
Navrhovaný YRC kombinuje bezpečnost vláken a zpracování mezivláknových cyklů pomocí hybridního přístupu: pro acyklická data se používá atomické počítání referencí a pro cyklická data se používá zápisová bariéra, aktivovaná pouze při přiřazování ukazatelů. V navrhované implementaci: kolektor se spouští, když je to skutečně potřeba (žádné pauzy typu stop-the-world); kořenové objekty RC jsou explicitně definovány a sloučeny jednou (není vyžadováno skenování zásobníku vláken); během iterace se zamezí vícevláknovému mazání (žádná fáze globálního sweepování); mutátory mohou volně číst data; libovolné vlákno může spustit garbage collector, když je to potřeba (žádné vyhrazené vlákno GC).
YRC využívá kompletní informace o událostech incRef/decRef, které tradiční trasovací garbage collectory (GC) zahodí a poté musí obnovit pomocí skenování zásobníku a procházení grafů. Implementace zabere pouze 550 řádků kódu a je formálně ověřena z hlediska bezpečnosti a absence deadlocků prostřednictvím specifikace v TLA+ a důkazu v sadě nástrojů Lean. YRC je prodáván jako „téměř poslední cyklický sběrač referencí“ (písmeno Y předchází Z v abecedě) a také jako nejjednodušší vláknově bezpečný garbage collector – podle autora nevyžaduje mnoho složitých mechanismů, které jsou vlastní tradičním trasovacím garbage collectorům.
YRC poskytuje stejné API jako ORC, přičemž destruktory se spouštějí během garbage collectoru. Collector zpracovává pouze podgrafy objektů, ke kterým přistupují vlákna, a ponechává nedotčené nesouvisející datové struktury (cache, dlouhodobé objekty) – přístup podobný „ideálnímu“ generačnímu garbage collectoru bez generačního garbage collectoru. Hlavní nevýhodou je výkon: YRC vykazuje v benchmarku orcbench 1.5–2.0násobné zpomalení ve srovnání s ORC. Autor to považuje za přijatelný kompromis pro plně thread-safe zpracování cyklických referencí.
YRC je již k dispozici ve vývojové verzi Nimu a lze jej povolit pomocí příznaku „--mm:yrc“. V následujících příspěvcích však autor uznal, že původní implementace obsahovala závažné chyby a nesestavovala cykly správně. V době publikace byla připravena sada oprav, které řeší hlavní problémy. Autor nadále ladí heuristiky sestavení a opravuje zbývající chyby, přičemž základní algoritmus a jeho formální ověření zůstávají správné.
Zdroj: opennet.ru
