In der Nim-Sprache wird YRC — ein threadsicherer Sammler für zyklische Verweise, vorgestellt.

Andreas Rumpf (Araq), der Autor der Programmiersprache Nim, kündigte den neuen Algorithmus zur Speicherverwaltung YRC (ausgesprochen „Ürk“) an, der eines der Kernprobleme bestehender Mechanismen in Nim löst: die Unfähigkeit, zirkuläre Links, die die Grenzen von Threads überschreiten, korrekt zu verarbeiten.

Vor der Einführung von YRC hatten die in Nim vorgeschlagenen Algorithmen zur Speicherverwaltung folgende Einschränkungen: ARC — unterstützte weder Multithreading noch die Verarbeitung von Zyklen; Atomic ARC — war threadsicher, aber verarbeitete keine zirkulären Links; ORC — verarbeitete zirkuläre Links, konnte dies jedoch nur innerhalb eines einzelnen Threads korrekt tun (die Verwendung gemeinsamer Links zwischen Threads führte zu Speicherlecks).

Das vorgeschlagene YRC kombiniert Threadsicherheit und die Verarbeitung von Zyklen zwischen Threads, indem es einen kombinierten Ansatz nutzt: für akyzklische Daten wird atomares Zählen von Verweisen eingesetzt, für zirkuläre Daten ein Schreibschutz (write barrier), der nur bei der Zuordnung von Zeigern aktiviert wird. In der vorgeschlagenen Implementierung: Der Sammler wird nach tatsächlichem Bedarf gestartet (keine stop-the-world Pausen); Wurzelobjekte RC sind eindeutig definiert und werden einmal zusammengeführt (keine Notwendigkeit, die Stapel der Threads zu scannen); das Mehrfach-Thread-Löschen während der Iteration wird vermieden (keine globale Sweep-Phase); Mutatoren lesen Daten frei; jeder Thread kann den Garbage Collector bei Bedarf starten (kein dedizierter GC-Thread).

YRC nutzt vollständige Informationen über die Ereignisse incRef/decRef, die herkömmliche tracing Garbage Collector (tracing GC) verwerfen und dann durch Scannen der Stapel und Durchlaufen des Graphen wiederherstellen müssen. Die Implementierung umfasst nur 550 Codezeilen und besitzt eine formale Verifikation der Sicherheit und Abwesenheit von Deadlocks durch eine Spezifikation in TLA+ und einen Beweis im Lean-Tool. YRC wird als „fast der letzte Zyklen-Collector auf Basis der Zählung von Verweisen“ positioniert (der Buchstabe Y precedes Z im Alphabet) sowie als der einfachste threadsichere Garbage Collector — laut dem Autor erfordert er keine Vielzahl komplexer Mechanismen, die traditionellen tracing Garbage Collectors eigen sind.

YRC bietet die gleiche API wie ORC an, mit der Ausführung von Destruktoren während der Garbage Collection. Der Sammler verarbeitet nur die Teilgraphen von Objekten, mit denen die Threads arbeiten, ohne unverbundene Datenstrukturen (Caches, langlebige Objekte) zu berühren – ein Ansatz, der dem „idealen“ generationalen Garbage Collector ohne die Nutzung von Generationen ähnelt. Der Hauptnachteil ist die Leistung: YRC zeigt eine Verlangsamung von 1,5-2,0 Mal im Vergleich zu ORC im Leistungstest orcbench. Der Autor hält dies für einen akzeptablen Preis für die vollständige threadsichere Verarbeitung zyklischer Referenzen.

YRC ist bereits in der Entwicklungsversion von Nim verfügbar und wird mit dem Flag „—mm:yrc“ aktiviert. In späteren Nachrichten räumte der Autor jedoch ein, dass die ursprüngliche Implementierung schwerwiegende Fehler enthielt und Zyklen nicht korrekt sammelte. Zum Zeitpunkt der Veröffentlichung wurde ein Korrekturensatz vorbereitet, der die Hauptfehler behebt. Der Autor arbeitet weiterhin an der Feinabstimmung der Sammel-Heuristiken und der Behebung der verbleibenden Fehler, wobei der grundlegende Algorithmus und seine formale Verifizierung korrekt bleiben.

Quelle: opennet.ru