Le langage Nim a introduit YRC — un collecteur de liens cycliques thread-safe

Andreas Rumpf (Araq), l'auteur du langage de programmation Nim, a annoncé un nouvel algorithme de gestion de la mémoire YRC (prononcé « Ürk »), qui résout l'un des problèmes clés des mécanismes existants dans Nim : l'impossibilité de gérer correctement les références circulaires traversant les frontières des threads.

Avant l'apparition de YRC, les algorithmes de gestion de la mémoire proposés dans Nim présentaient les limitations suivantes : l'ARC ne supportait ni la multiprogrammation, ni la gestion des cycles ; l'Atomic ARC était sûr pour les threads, mais ne gérait pas les références circulaires ; l'ORC gérait les références circulaires, mais pouvait le faire correctement uniquement à l'intérieur d'un seul thread (l'utilisation de références partagées entre les threads entraînait des fuites de mémoire).

Le YRC proposé combine la sécurité des threads et la gestion des cycles entre threads, grâce à une approche combinée : pour les données acycliques, il applique un comptage de références atomiques, et pour les données circulaires, un barrier d'écriture (write barrier) qui s'active uniquement lors de l'attribution de pointeurs. Dans la mise en œuvre proposée : le collecteur est déclenché en fonction des nécessités réelles (absence de pauses stop-the-world) ; les objets racines RC sont explicitement définis et unis une seule fois (aucun balayage des piles des threads n'est nécessaire) ; l'élimination multi-thread pendant l'itération est évitée (pas de phase de balayage globale) ; les mutateurs lisent librement les données ; tout thread peut lancer le ramasse-miettes si nécessaire (sans thread GC dédié).

Le YRC utilise des informations complètes sur les événements incRef/decRef, que les collecteurs de déchets traçants traditionnels (tracing GC) rejettent puis doivent restaurer via le balayage des piles et le parcours du graphique. L'implémentation ne nécessite que 550 lignes de code et possède une vérification formelle de sécurité et d'absence de blocage mutuel via une spécification en TLA+ et une démonstration dans l'outil Lean. Le YRC se positionne comme « presque le dernier collecteur de cycles basé sur le comptage des références » (la lettre Y précède Z dans l'alphabet), ainsi que comme le collecteur de déchets le plus simple et sûr pour les threads — selon l'auteur, il ne nécessite pas de nombreux mécanismes complexes présents dans les collecteurs de déchets traçants traditionnels.

YRC fournit la même API que ORC, avec l'exécution des destructeurs pendant le ramassage des ordures. Le ramasse-miettes ne traite que les sous-graphes d'objets auxquels les threads accèdent, sans toucher aux structures de données non liées (caches, objets à longue durée de vie) — une approche similaire à celle d'un ramasse-miettes générationnel « idéal » sans utilisation de générations. Le principal inconvénient réside dans les performances : YRC montre un ralentissement de 1,5 à 2,0 fois par rapport à ORC dans le test de performance orcbench. L'auteur considère que c'est un prix acceptable à payer pour un traitement complet des cycles de référence en toute sécurité des threads.

YRC est déjà disponible dans la version développement de Nim et s'active avec le drapeau « —mm:yrc ». Cependant, dans les messages suivants, l'auteur a reconnu que la première implémentation contenait de graves erreurs et ne collectait pas correctement les cycles. Au moment de la publication, un ensemble de correctifs a été préparé pour résoudre les principaux bugs. L'auteur continue d'ajuster les heuristiques de ramassage et de corriger les erreurs restantes, l'algorithme de base et sa vérification formelle restant corrects.

Source : opennet.ru