Andreas Rumpf (Araq), the author of the Nim programming language, announced a new memory management algorithm called YRC (pronounced 'Ürk'), which addresses one of the key issues of existing mechanisms in Nim: the inability to correctly handle cyclic references that cross thread boundaries.
Before the introduction of YRC, the memory management algorithms available in Nim had the following limitations: ARC — did not support multi-threading or cycle handling; Atomic ARC — was thread-safe but did not process cyclic references; ORC — handled cyclic references but could do so correctly only within a single thread (using shared references between threads resulted in memory leaks).
The proposed YRC combines thread safety and cycle processing across threads through a hybrid approach: atomic reference counting is used for acyclic data, while a write barrier is activated only when assigning pointers for cyclic references. In the proposed implementation: the collector is triggered only when necessary (no stop-the-world pauses); root RC objects are explicitly defined and collected once (no need to scan thread stacks); multi-threaded deletion during iteration is avoided (there is no global sweep phase); mutators freely read data; any thread can initiate garbage collection when needed (without a dedicated GC thread).
YRC utilizes complete information about incRef/decRef events, which traditional tracing garbage collectors discard and subsequently must recover through stack scanning and graph traversal. The implementation consists of only 550 lines of code and has formal verification of safety and deadlock freedom through specifications in TLA+ and proof in the Lean toolchain. YRC is positioned as 'almost the last cycle collector based on reference counting' (the letter Y precedes Z in the alphabet), as well as the simplest thread-safe garbage collector — according to the author, it does not require the many complex mechanisms characteristic of traditional tracing garbage collectors.
YRC provides the same API as ORC, with destructors executed during garbage collection. The collector only processes those subgraphs of objects that the threads are working with, leaving unrelated data structures (caches, long-lived objects) untouched — a method similar to a "perfect" generational garbage collector without generations. The main drawback is performance: YRC shows a slowdown of 1.5-2.0 times compared to ORC in the orcbench performance test. The author considers this an acceptable price for fully thread-safe handling of cyclic references.
YRC is already available in the development version of Nim and is enabled with the flag "—mm:yrc". However, in later messages, the author acknowledged that the initial implementation had serious errors and did not collect cycles correctly. As of the publication date, a set of fixes has been prepared to eliminate the main errors. The author continues tuning the collection heuristics and fixing remaining bugs, while the basic algorithm and its formal verification remain correct.
Source: opennet.ru
