Andreas Rumpf (Araq), autor programovacieho jazyka Nim, oznámil nový algoritmus správy pamäte YRC (vyslovuje sa ako „Ürk“), ktorý rieši jeden z kľúčových problémov existujúcich mechanizmov v Nime: nemožnosť správneho spracovania cyklických referencií prekračujúcich hranice vlákien.
Pred príchodom YRC mali navrhnuté algoritmy správy pamäte v Nime tieto obmedzenia: ARC — nepodporoval viacvláknovosť ani spracovanie cyklov; Atomic ARC — bol bezpečný pre vlákna, ale nespracovával cyklické referencie; ORC — spracovával cyklické referencie, ale mohol to robiť správne iba v rámci jedného vlákna (pri použití zdieľaných referencií medzi vláknami vznikali úniky pamäte).
Navrhnutý YRC kombinuje bezpečnosť pri práci s vláknami a spracovanie cyklov medzi vláknami, vďaka použitiu kombinovaného prístupu: pre acyklické dáta sa používa atomárny počítanie referencií, a pre cyklické — zápisová bariéra (write barrier), ktorá sa aktivuje iba pri priraďovaní ukazovateľov. V navrhnutej implementácii: zberateľ sa spúšťa podľa skutočnej potreby (bez stop-the-world pauz); koreňové objekty RC sú jasne definované a kombinované raz (nie je potrebné skenovanie zásobníkov vlákien); vyhýba sa viacvláknovému odstráneniu počas iterácie (žiadna globálna fáza sweep); mutátory voľne čítajú dáta; akékoľvek vlákno môže spustiť zberateľ odpadu podľa potreby (bez vyhradeného GC vlákna).
YRC využíva úplné informácie o udalostiach incRef/decRef, ktoré tradiční trasovacie zberatelia odpadu (tracing GC) odmietajú a následne ich musia obnoviť skenovaním zásobníkov a prechádzaním grafu. Implementácia zaberá len 550 riadkov kódu a má formálnu verifikáciu bezpečnosti a absencie vzájomných blokovaní prostredníctvom špecifikácie v jazyku TLA+ a dôkazu v nástroji Lean. YRC je prezentovaná ako „takmer posledný zberateľ cyklov na báze počítania referencií“ (písmeno Y predchádza Z v abecede), ale aj ako najjednoduchší zberateľ odpadu bezpečný pre vlákna — podľa autora nevyžaduje množstvo zložitých mechanizmov, ktoré sú vlastné tradičným trasovacím zberateľom odpadu.
YRC poskytuje rovnaké API ako ORC, so spúšťaním destruktorov počas zberu odpadu. Zberač spracováva iba tie podgrafy objektov, s ktorými pracujú vlákna, pričom sa nedotýka nesúvisiacich štruktúr dát (cache, dlhodobé objekty) — prístup, ktorý je podobný „ideálnemu“ generatívnemu zberaču odpadu bez využívania generácií. Hlavnou nevýhodou je výkon: YRC ukazuje spomalenie o 1,5-2,0 násobok v porovnaní s ORC v teste výkonu orcbench. Autor považuje toto za prijateľnú cenu za úplne vlákno-bezpečné spracovanie cyklických odkazov.
YRC je už dostupný v vývojovej verzii Nim a zapína sa príkazom „--mm:yrc“. Avšak v nasledujúcich príspevkoch autor uznal, že pôvodná implementácia obsahovala vážne chyby a správne nezbierala cykly. K dátumu publikácie bol pripravený súbor opráv, ktorý odstraňuje hlavné chyby. Autor pokračuje v ladění heuristík zberu a opravovaní zostávajúcich chýb, pričom základný algoritmus a jeho formálna verifikácia zostávajú správne.
Zdroj: opennet.ru
