L’incroyable ramasse-miettes de Fil

• Le FUGC du langage Fil-C est un ramasse-miettes avancé prenant en charge le parallélisme et la concurrence
• Il utilise une exécution on-the-fly et une approche grey-stack de Dijkstra sans interruption globale du programme
• Il met en œuvre une conception avec traçage mémoire précis et sans déplacement des objets
• Grâce aux safepoints, il permet une gestion mémoire sûre et efficace même en environnement multithread
• Il offre diverses fonctions de gestion mémoire dans les styles C/Java/JavaScript, comme le traitement par exception lors d’un accès à un objet libéré / double libération

---

Présentation de FUGC, le ramasse-miettes incroyable de Fil

Fil-C utilise FUGC (Fil's Unbelievable Garbage Collector), un ramasse-miettes parallèle, concurrent, on-the-fly, grey-stack, de Dijkstra, précis et non déplaçant
Le code source de FUGC est disponible dans fugc.c, mais il ne peut pas fonctionner sans les diverses logiques de support du runtime et du compilateur

Principales caractéristiques de FUGC

• Traitement parallèle : les opérations de marquage et de balayage sont exécutées simultanément sur plusieurs threads ; plus il y a de cœurs CPU, plus la collecte est rapide
• Prise en charge de la concurrence : les threads du ramasse-miettes travaillent séparément des mutators (c’est-à-dire les threads du programme utilisateur), ce qui permet aux threads de l’application de continuer sans interruption
• on-the-fly : au lieu d’un stop-the-world global, chaque thread effectue de manière asynchrone certaines opérations comme le scan de pile via un « soft handshake » (= ragged safepoint)
• Approche grey-stack : les piles de threads sont rescannées plusieurs fois jusqu’au point fixe, avec répétition du marquage ; si de nouveaux objets apparaissent durant ce processus, le marquage reprend
• Utilise un store barrier simple, sans nécessité de load barrier
• Barrière de Dijkstra : lorsqu’un pointeur est stocké dans le tas ou dans une variable globale pendant le marquage, l’objet cible est lui aussi marqué simultanément
• Collecte précise : le runtime suit exactement toutes les positions de pointeurs, de sorte que le GC ne parcourt que les objets réels
• Objets non déplacés : l’adresse mémoire des objets ne change pas, ce qui facilite la collecte concurrente multithread et la synchronisation
• Conception à wavefront avançant : le mutator ne peut pas augmenter la charge de travail du collecteur, et les objets marqués le restent pendant tout le cycle de collecte
• Collecte incrémentale : certains objets, bien que vivants au début de la collecte, peuvent être libérés en cours de cycle

Safepoints et gestion des threads

• Pollcheck : le compilateur insère périodiquement des pollchecks ; sur le chemin rapide, il ne s’agit que d’un simple branchement, tandis que le chemin lent exécute des callbacks liés au GC
• Soft handshake : demande à tous les threads d’exécuter le callback pollcheck puis attend leur achèvement
• Gestion d’état enter/exit : pour les fonctions bloquantes de longue durée, appels système, etc., lorsque le pollcheck est omis, le collecteur exécute lui-même le callback correspondant
• Garantit la prévention des conditions de course et un accès sûr aux pointeurs dans les environnements prenant en charge le multithreading
• Prend aussi en charge des opérations spéciales comme le débogage ou fork via un mode stop-the-world, avec une gestion stable des signaux

Boucle du collecteur FUGC

1. Attente d’un déclenchement du GC
2. Activation du store barrier puis soft handshake avec callback no-op
3. Activation de l’allocation en noir (pré-marquage des nouveaux objets), puis exécution du callback de réinitialisation du cache
4. Marquage des racines globales
5. Soft handshake (scan de pile et callback de réinitialisation du cache) ; si la pile de marquage est vide, passer à l’étape 7
6. Traçage (marquage des références pour chaque objet de la pile de marquage, répétition jusqu’à ce qu’elle soit vide, puis retour à l’étape 5)
7. Désactivation du store barrier, préparation du balayage, puis soft handshake de nouvelle réinitialisation du cache
8. Balayage (les pages pas encore balayées allouent en noir, celles déjà balayées en blanc)
9. Retour dans la boucle

Différences avec les travaux antérieurs et optimisations

• FUGC ressemble au collecteur DLG (Doligez-Leroy-Gonthier), mais l’implémentation du store barrier y est plus intuitive et plus performante grâce à une barrière de Dijkstra simple et à l’utilisation d’une grey stack
• L’approche par point fixe converge rapidement et coûte peu
• Le balayage basé sur des bitvectors SIMD permet une libération extrêmement rapide, représentant moins de 5 % du temps total du GC
• Optimisations de performance, notamment via la configuration de tas Verse

Fonctions bonus (extensibilité de la gestion mémoire)

Libération d’objets

• Lorsqu’on appelle free en C, l’objet est immédiatement marqué comme libéré, et tout accès ultérieur déclenche un trap
• Empêche les dysfonctionnements du GC dus à des dangling pointers
• Les références vers des objets libérés sont redirigées vers un objet free singleton, ce qui permet une détection fiable même après réallocation mémoire
• Évite les fuites mémoire provoquées par des pointeurs inutilisés qui déclencheraient le GC

Finalizers

• Les files de finalizers de style Java peuvent être implémentées de façon souple via des files personnalisées et un traitement par thread

Références faibles

• Fonctionnent comme les weak reference de Java, sans file de références séparée (pas de prise en charge de phantom ni de soft reference)

Maps faibles

• Semblables à WeakMap en JavaScript, avec toutefois la possibilité d’itérer sur tous les éléments et d’en connaître le nombre

Conclusion et portée

Grâce à FUGC, Fil-C offre une forte sûreté et une gestion des exceptions intuitive face aux mauvais usages de free

• Le système est conçu pour qu’un trap se produise systématiquement lors d’un accès à un objet libéré ou d’une double libération
• Si un objet n’est pas libéré, le GC se charge de le récupérer correctement
• Il prend en charge divers modèles de gestion mémoire et fournit un environnement familier même pour les développeurs venant de C, Java ou JavaScript

[GN⁺]

Commentaires sur Hacker News

• Hmm, Fil-C pourrait vraiment avoir une importance majeure. Il existe énormément de logiciels écrits uniquement en C, donc il faut une approche pour les maintenir. Les compilateurs C existants prennent de gros risques de sécurité pour maximiser les performances sur un seul cœur, et ce genre de compromis semble déjà daté. La liste des logiciels pris en charge est vraiment impressionnante : CPython, SQLite, OpenSSH, ICU, CMake, Perl5, Bash, etc. Je vois mal n’importe lequel de ces logiciels être réécrit en Rust. Je me demande si Fil-C pourrait aussi servir au multitâche entre processus non fiables sur des environnements sans MMU. On dirait qu’ils vont dans la bonne direction avec la sécurité fondée sur les capacités, la synchronisation non bloquante, etc. J’aimerais savoir si quelqu’un l’a déjà utilisé en pratique. En réalité, il est rapporté qu’au pire les performances chutent d’environ 4x, et le nom est vraiment drôle. Fil this way! Fil this way!

  • À propos de la question de savoir si Fil-C permettrait le multitâche entre processus non fiables sur des machines sans MMU : fondamentalement, FUGC repose sur des fonctionnalités de l’OS dépendantes de la MMU, mais je pense qu’on pourrait en faire une version sans cette dépendance. Côté performances, le facteur 4x plus lent correspond au pire cas, et c’est moi qui ai rapporté ce chiffre. J’essaie toujours de mesurer les performances de façon réaliste et de corriger obstinément les problèmes de performance. En pratique, je peux aussi utiliser sans difficulté, au quotidien, des versions de logiciels compilées avec Fil-C

  • Vous dites que la liste des logiciels pris en charge est impressionnante ; je suis d’accord en général, mais je vois les exemples cités un peu différemment. CPython, Perl5, etc. sont déjà les runtimes de langages réputés pour leur GC lente, donc leur ajouter encore une GC ne me paraît pas être une conception élégante, et la baisse de performances pourrait être importante. Et il existe déjà, au moins en partie, des tentatives de réimplémentation ou de remplacement en Rust ou en Go ; par exemple, pour SQLite, il y a Turso. En plus, ce sont des projets fondamentaux très activement maintenus, donc ils pourraient un jour être refactorisés en interne ou portés vers Rust. À mon avis, Fil-C conviendrait plutôt à du code moins maintenu, moins sensible aux performances, mais toujours utilisé — des programmes C vieux de 50 ans que quelqu’un ressort de temps en temps

  • L’un des grands avantages de SQLite, écrit en C, est sa portabilité vers des OS non standards. Par exemple, je l’ai déjà utilisé directement sur μC/OS-II, un RTOS pour systèmes embarqués. La conception des environnements embarqués diffère assez fortement de celle des PC/serveurs : pour des raisons de performance et pour éviter la fragmentation mémoire, on ne libère parfois jamais la mémoire et on marque plutôt les objets/structures comme réutilisables. C’est une idée proche des allocations sur tas personnalisées ou du pooling. Documentation VFS de SQLite, Présentation de Micro-Controller OS

  • Vous dites qu’aucun des logiciels C de cette liste ne sera réécrit en Rust, mais je me demande dans combien de temps les outils d’analyse statique fondés sur l’IA progresseront au point de repérer précisément les problèmes dans du code C et de dire : « cette partie provoquera une erreur, voici comment la corriger ». Si de tels outils voient vraiment le jour, continuer à utiliser le C pourrait redevenir tout à fait acceptable

  • À noter que Fil-C ne prend pas encore en charge les systèmes 32 bits (ou inférieurs). Documentation Fil-C sur Invisicaps

• Ce projet donne l’impression d’être un cas rare où recherche et pratique avancent ensemble. D’ordinaire, ce genre de travail est plutôt mené par une grande entreprise tech avec une équipe dédiée et financé par les revenus publicitaires ; je me demande de quel contexte Fil-C est issu. Si ce n’est pas simplement un projet passion, qui l’a financé, combien d’années-homme y ont été consacrées, et quel est l’objectif final ?

  • Personnellement, ça me semble être un projet passion

  • À la question sur l’objectif final, le copyright du projet indique 2024-2025 Epic Games, Inc.

• Le simple fait que Fil-C existe est réjouissant. Même lorsque ce type de technologie est réellement efficace sur de vrais programmes, beaucoup de développeurs continuent de croire que « ce n’est pas possible ». Le simple fait de démontrer que c’est implémentable suffit à clore d’innombrables débats d’un seul coup

  • Je serais curieux de voir des benchmarks. La principale inquiétude avec ce genre d’approche, c’est que les performances chutent énormément dans certains cas d’usage où le C/C++ reste populaire. Si le débit, la latence ou l’utilisation mémoire finissent par trop ressembler à ceux de langages comme Go, il ne restera peut-être plus beaucoup de raisons de le choisir

  • En programmation, le débat sur les performances existe depuis l’époque de l’assembleur. Mais la plupart des développeurs ne sont pas des visionnaires hors norme comme Ivan Suntherland, Alan Kay, Steve Jobs ou Bret Victor ; ce sont des gens ordinaires qui font confiance à ce qu’ils peuvent voir fonctionner sous leurs yeux. C’est peut-être pour cela qu’on trouve encore autant de clones d’UNIX et de C, et que tant de gens vivent en recopiant des visions du passé plutôt qu’en créant quelque chose de nouveau. Cela dit, les deux personnes qui ont créé UNIX et C dans les années 1970 étaient elles aussi de remarquables visionnaires

• Je me demande pourquoi ils n’ont pas choisi une stratégie de retreating wavefront plutôt qu’une advancing wavefront

• Si les appels à free(...) sont déjà correctement présents dans les programmes C existants, et qu’on gère en plus séparément des informations de borne pour chaque pointeur, pourquoi avoir choisi une GC complète ? À la place, une technique de vérification temporelle de type lock-and-key (référence : lien vers l’article) pourrait peut-être être meilleure en termes de prévisibilité mémoire, de performances ou d’ordonnancement. J’imagine que l’espace nécessaire pour stocker les clés est peut-être trop important, que les vérifications coûtent trop cher, ou qu’il peut y avoir des conditions de course en environnement multithread

  • L’approche lock and key n’a rien de particulièrement malin propre à Fil-C. La force du modèle par capacités de Fil-C, c’est qu’il est complètement thread-safe et que, dans la plupart des cas, il n’a besoin ni d’atomiques spéciaux ni de verrouillage

  • Je trouve aussi intéressant qu’ils autorisent l’arithmétique hors bornes sur les pointeurs tant qu’il n’y a pas de déréférencement. Les compilateurs exploitent parfois l’UB dans ce genre de cas pour optimiser (question Stack Overflow associée) ; je me demande donc si LLVM, dans Fil-C, désactive ces optimisations, ou si les pointeurs sont gérés comme une combinaison « base + offset », ce qui éliminerait totalement ce risque. Et si c’est le cas, je me demande aussi si cela ne fait pas perdre certaines optimisations applicables aux pointeurs ordinaires

• Le projet a l’air vraiment excellent. Je note que le fast path de pollcheck n’est qu’un load-and-branch. Il existe une technique intéressante qui peut remplacer ce type de branchement ; elle est bien résumée dans l’article du blog officiel Android « implicit suspend checks »

  • Ce genre d’optimisation est souvent utilisé pour les poll checks. En fait, la plupart des JVM de production l’appliquent déjà. Mais je n’en suis pas encore au stade où je dois me préoccuper de ce type d’optimisations bas niveau. Il me reste encore à faire d’abord des optimisations de haut niveau plus fondamentales

• Du C avec prise en charge de la concurrence et GC, qui plus est une GC non mouvante : c’est vraiment étonnant. Si je peux réduire les bugs mémoire sur un projet C de taille moyenne en échange d’une perte de performances d’un facteur 2 à 3 à l’exécution, je serais tout à fait prêt à l’accepter. Je me demande à quel point l’adoption progressive est simple. Est-ce possible cible par cible, ou faut-il remplacer toute la toolchain ?

• J’accorde beaucoup d’importance au C, aux performances et à la sécurité. Cette structure GC + capacités est séduisante. Je me suis souvent demandé à quoi pourrait ressembler un « C plus sûr » ; j’ai envisagé plusieurs fois le concept de capacités, mais je ne maîtrise pas vraiment le code des compilateurs. Je me demande si le support de Windows est difficile

  • Petite digression : l’absence de virgule d’Oxford dans la première phrase m’a demandé un bon moment avant d’en comprendre le sens. C’est un exemple de manque de clarté assez rare

• Je me demande comment la GC suit les objets racines. Y a-t-il une phase de compilation qui marque à l’avance les racines à scanner ? Si quelqu’un le sait, je serais preneur d’une explication

  • LLVM résout cela en insérant des instructions pour remplir la stack map

• Ce projet est vraiment stupéfiant. Il est presque étrange que je n’en aie jamais entendu parler jusqu’ici. J’ai hâte de l’essayer moi-même. Les limites de performance le rendront peut-être difficile à utiliser en production, mais comme moyen de vérifier concrètement la sûreté de certains programmes, cela semble extrêmement utile. Cela paraît plus global que les sanitizers que j’utilise habituellement