Die Sprache Nim führt YRC ein – einen threadsicheren Garbage Collector für zirkuläre Referenzen.

Andreas Rumpf (Araq), der Schöpfer der Programmiersprache Nim, hat einen neuen Algorithmus zur Speicherverwaltung namens YRC (ausgesprochen „Ürk“) vorgestellt, der ein zentrales Problem der bestehenden Mechanismen in Nim löst: die korrekte Verarbeitung von zirkulären Referenzen, die die Thread-Grenzen überschreiten.

Vor der Einführung von YRC hatten die in Nim angebotenen Algorithmen zur Speicherverwaltung folgende Einschränkungen: ARC – unterstützte weder Multithreading noch die Behandlung von Kreisläufen; Atomic ARC – war threadsicher, behandelte jedoch keine zirkulären Referenzen; ORC – konnte zirkuläre Referenzen behandeln, jedoch nur korrekt innerhalb eines einzelnen Threads (bei der Verwendung von gemeinsamen Referenzen zwischen Threads traten Gedächtnislecks auf).

Die vorgeschlagene YRC kombiniert Thread-Sicherheit und das Verarbeiten von Zyklen zwischen Threads durch einen hybriden Ansatz: Für azyklische Daten wird eine atomare Referenzzählung verwendet, während für zyklische Daten eine Schreibbarriere (write barrier) zum Einsatz kommt, die nur beim Zuweisen von Zeigern aktiviert wird. In der vorgeschlagenen Implementierung wird der Collector nur bei tatsächlichem Bedarf gestartet (keine stop-the-world Pausen); die Wurzelobjekte von RC sind eindeutig definiert und werden einmalig zusammengeführt (kein Scannen der Thread-Stacks erforderlich); das mehrfädige Löschen während der Iteration wird vermieden (keine globale Sweep-Phase); Mutatoren können Daten frei lesen; jeder Thread kann bei Bedarf den Garbage Collector starten (kein dedizierter GC-Thread).

YRC nutzt vollständige Informationen zu den Ereignissen incRef/decRef, die herkömmliche tracing Garbage Collector (GC) ignorieren und dann durch das Scannen von Stacks und Traversieren des Graphen wiederherstellen müssen. Die Implementierung besteht aus nur 550 Codezeilen und hat eine formale Sicherheits- und Deadlock-Verifizierung durch eine Spezifikation in der Sprache TLA+ und einen Beweis im Lean-Toolset. YRC wird als "nahezu letzter Zähler-basierten Cycles Collector" positioniert (der Buchstabe Y kommt vor Z im Alphabet) und auch als der einfachste thread-sichere Garbage Collector — laut dem Autor erfordert er nicht die vielen komplexen Mechanismen, die herkömmlichen tracing Garbage Collectors eigen sind.

YRC bietet die gleiche API wie ORC und führt Destruktoren während der Garbage Collection aus. Der Sammler verarbeitet nur die Teilgraphen von Objekten, mit denen die Threads arbeiten, und berührt keine unverbundenen Datenstrukturen (Caches, langlebige Objekte). Dieser Ansatz ähnelt einem „idealen“ generationsbasierten Garbage Collector ohne die Verwendung von Generationen. Der Hauptnachteil ist die Leistung: YRC zeigt im orcbench-Leistungstest eine Verlangsamung von 1,5 bis 2,0 im Vergleich zu ORC. Der Autor hält dies für einen akzeptablen Preis für die vollständige thread-sichere Behandlung von zyklischen Verweisen.

YRC ist bereits in der Entwicklungsversion von Nim verfügbar und wird über das Flag „—mm:yrc“ aktiviert. In späteren Mitteilungen erkannte der Autor jedoch, dass die ursprüngliche Implementierung schwerwiegende Fehler enthielt und Zyklen nicht korrekt sammelte. Zum Zeitpunkt der Veröffentlichung steht ein Satz von Korrekturen zur Verfügung, die die Hauptfehler beheben. Der Autor arbeitet weiterhin an der Feinabstimmung der Sammelheuristiken und der Behebung der verbleibenden Fehler, während der grundlegende Algorithmus und dessen formale Verifikation korrekt bleiben.

Quelle: opennet.ru