В езика Nim е представен YRC — потокобезопасен сборщик на циклични референции

Андреас Румпф (Araq), автор на езика за програмиране Nim, обяви нов алгоритъм за управление на паметта YRC (изговаря се «Ürk»), който решава един от ключовите проблеми на съществуващите механизми в Nim: невъзможността за коректна обработка на циклични връзки, пресичащи границите на потоките.

Преди появата на YRC в предлаганите в Nim алгоритми за управление на паметта имаше следните ограничения: ARC — не поддържаше нито многопоточност, нито обработка на цикли; Atomic ARC — беше безопасен за потока, но не обработваше циклични връзки; ORC — обработваше циклични връзки, но можеше да го прави коректно само в рамките на един поток (при използване на споделени връзки между потоките възникваха изтичания на памет).

Предложеният YRC съчетава безопасност за потока и обработка на цикли между потоките, благодарение на комбиниран подход: за ациклични данни се прилага атомарно броене на връзките, а за циклични — бариера за запис (write barrier), която се активира само при присвояване на указатели. В предложената реализация: колекторът се стартира при действителна необходимост (липса на паузи stop-the-world); кореновите обекти RC са ясно определени и обединени веднъж (не е необходимо сканиране на стековете на потоките); избягва се многопоточна обработка по време на итерация (няма глобална фаза sweep); мутатори свободно четат данни; всеки поток може да стартира сборщика на мусор при необходимост (без определен GC поток).

YRC използва пълна информация за събитията incRef/decRef, която традиционните трасиращи сборщики мусор (tracing GC) отхвърлят и след това са принудени да възстановят чрез сканиране на стекове и обход на графа. Реализацията заема само 550 реда код и има формална верификация на безопасността и отсъствието на взаимни блокировки чрез спецификация на езика TLA+ и доказателство в инструмента Lean. YRC се позиционира като «почти последния сборщик на цикли на базата на броене на връзки» (буквата Y предхожда Z в азбуката), а също така като най-простия безопасен за потока сборщик мусор — според автора, не изисква множество сложни механизми, присъщи на традиционните трасиращи сборщики мусор.

YRC предоставя същото API, както ORC, с изпълнение на деструктори по време на събиране на垃圾. Събирачът обработва само онези подграфи на обекти, с които работят нишките, без да засяга несвързани структури от данни (кешове, дългоживеещи обекти) — подход, подобен на "идеалния" генерационен събирач на垃圾 без използването на поколения. Основният недостатък е производителността: YRC показва забавяне от 1.5-2.0 пъти в сравнение с ORC в теста за производителност orcbench. Авторът смята, че това е приемлива цена за пълна потокобезопасна обработка на циклични връзки.

YRC вече е наличен в development версията на Nim и се активира с флага "—mm:yrc". Въпреки това, в последващи съобщения авторът призна, че първоначалната реализация е съдържала сериозни грешки и не е събирала цикли коректно. Към момента на публикуване е подготвен набор от корекции, който отстранява основните грешки. Авторът продължава настройването на хевристиките за събиране и исправянето на останалите грешки, като основният алгоритъм и неговата формална верификация остават коректни.

Източник: opennet.ru