Andreas Rumpf (Araq), de auteur van de programmeertaal Nim, heeft een nieuw algoritme voor geheugenbeheer YRC (uitgesproken als 'Ürk') aangekondigd, dat een van de belangrijkste problemen van bestaande mechanismen in Nim oplost: het onvermogen om correct om te gaan met cyclische verwijzingen die de grenzen van threads overschrijden.
Voor de komst van YRC waren de volgende beperkingen aanwezig in de voorgestelde geheugenbeheeralgoritmes in Nim: ARC ondersteunde geen multithreading of de verwerking van cycli; Atomic ARC was thread-safe, maar verwerkte geen cyclische verwijzingen; ORC verwerkte cyclische verwijzingen, maar kon dit correct alleen binnen één thread doen (bij het gebruik van gedeelde verwijzingen tussen threads ontstonden geheugenlekken).
De voorgestelde YRC combineert thread-safety met de verwerking van cycli tussen threads door gebruik te maken van een gecombineerde aanpak: voor acyclische gegevens wordt een atomische referentietelling toegepast, en voor cyclische gegevens een write barrier, die alleen wordt geactiveerd bij het toewijzen van pointers. In de voorgestelde implementatie: de collector wordt alleen op daadwerkelijke behoefte gestart (geen stop-the-world pauzes); de root-objecten RC zijn expliciet gedefinieerd en worden eenmaal samengevoegd (geen scannen van de stacks van threads noodzakelijk); multithreaded verwijdering tijdens iteratie wordt vermeden (geen globale sweep-fase); mutators lezen vrijelijk gegevens; elke thread kan de garbage collector indien nodig starten (zonder een speciale GC-thread).
YRC maakt gebruik van volledige informatie over de gebeurtenissen incRef/decRef, die traditionele tracing garbage collectors (tracing GC) verwerpen en dan gedwongen zijn te herstellen via stack scanning en graf traversing. De implementatie beslaat slechts 550 regels code en heeft een formele verificatie van veiligheid en afwezigheid van deadlocks via specificatie in de TLA+ taal en bewijs in de Lean toolkit. YRC wordt gepositioneerd als 'bijna de laatste cyclische collector op basis van referentietelling' (de letter Y komt voor Z in het alfabet), en ook als de eenvoudigste thread-safe garbage collector — volgens de auteur vereist het niet de vele complexe mechanismen die kenmerkend zijn voor traditionele tracing garbage collectors.
YRC biedt dezelfde API als ORC, met destructors die worden uitgevoerd tijdens de garbage collection. De verzamelaar behandelt alleen die subgrafen van objecten waarmee threads werken, zonder niet-verbonden datastructuren (caches, langlevende objecten) aan te raken — een benadering die lijkt op een ‘ideale’ generational garbage collector zonder gebruik van generaties. Het belangrijkste nadeel is de prestaties: YRC vertoont een vertraging van 1,5 tot 2,0 keer vergeleken met ORC in de orcbench prestatietest. De auteur beschouwt dit als een acceptabele prijs voor volledige thread-veilige verwerking van cyclische referenties.
YRC is al beschikbaar in de developmentversie van Nim en kan worden ingeschakeld met de vlag “—mm:yrc”. Echter, in latere berichten erkende de auteur dat de oorspronkelijke implementatie ernstige fouten bevatte en cycli niet correct verzamelde. Op het moment van publicatie is een set correcties voorbereid die de belangrijkste fouten verhelpt. De auteur blijft de heuristieken van de verzameling afstemmen en de resterende fouten verhelpen, terwijl het basisalgoritme en de formele verificatie correct blijven.
Bron: opennet.ru
