В езика 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