Fils unglaublicher Garbage Collector

• Der FUGC der Sprache Fil-C ist ein fortschrittlicher Garbage Collector mit Unterstützung für parallele und konkurrierende Ausführung
• Er arbeitet on-the-fly und mit einem Grey-Stack-Dijkstra-Verfahren, ohne das gesamte Programm anzuhalten
• Er implementiert ein Design mit präzisem Memory-Tracking und Verarbeitung ohne Objektverschiebung
• Durch die Nutzung von Safepoints ist auch in Multithreading-Umgebungen eine sichere und effiziente Speicherverwaltung möglich
• Er bietet vielfältige Memory-Management-Funktionen im Stil von C/Java/JavaScript, darunter Exception-Behandlung bei Zugriff auf freigegebene Objekte oder doppeltem Freigeben

---

Überblick über FUGC (Fils unglaublicher Garbage Collector)

Fil-C verwendet FUGC (Fil's Unbelievable Garbage Collector), einen parallelen, konkurrierenden, on-the-fly arbeitenden, präzisen, nicht verschiebenden Grey-Stack-Dijkstra-Garbage-Collector
Der Quellcode von FUGC ist in fugc.c zu finden, funktioniert jedoch nicht ohne verschiedene unterstützende Logiken in Runtime und Compiler

Zentrale Merkmale von FUGC

• Parallele Verarbeitung: Marking- und Sweep-Arbeiten werden gleichzeitig auf mehreren Threads ausgeführt; je mehr CPU-Kerne vorhanden sind, desto schneller läuft die Sammlung
• Konkurrenzfähigkeit: Der Garbage-Collector-Thread arbeitet getrennt von den Mutator-Threads (also den Threads des Benutzerprogramms), sodass die Anwendungs-Threads ohne Stopp weiterlaufen können
• On-the-fly: Ohne globales Stop-the-World werden über einen „Soft Handshake“ (= ragged safepoint) bestimmte Arbeiten wie Stack-Scans von jedem Thread asynchron erledigt
• Grey-Stack-Verfahren: Thread-Stacks werden wiederholt bis zu einem Fixpunkt erneut untersucht und Marking wird wiederholt; tauchen dabei zusätzliche Objekte auf, wird erneut markiert
• Es nutzt eine einfache Store Barrier, eine Load Barrier ist nicht erforderlich
• Dijkstra-Barrier: Wird während des Markings ein Pointer in den Heap oder in globale Variablen gespeichert, wird das Zielobjekt gleichzeitig mit markiert
• Präzise Sammlung: Die Runtime verfolgt alle Pointer-Positionen exakt, sodass der GC nur tatsächliche Objekte traversiert
• Nicht verschiebende Objektverarbeitung: Die Speicherposition von Objekten ändert sich nicht, was konkurrierende Sammlung und Synchronisierung in Multithreading vereinfacht
• Advancing-Wavefront-Design: Der Mutator kann den Arbeitsaufwand des Collectors nicht erhöhen; markierte Objekte bleiben während dieses Sammelzyklus erhalten
• Inkrementelle Sammlung: Manche Objekte können während des Zyklus freigegeben werden, obwohl sie zu Beginn der Sammlung noch lebten

Safepoints und Thread-Verwaltung

• Pollcheck: Der Compiler fügt regelmäßig Pollchecks ein; auf dem Fast Path ist das nur ein einfacher Branch, auf dem Slow Path wird ein GC-bezogener Callback ausgeführt
• Soft Handshake: Alle Threads werden aufgefordert, den Pollcheck-Callback auszuführen, und es wird auf deren Abschluss gewartet
• enter/exit-Zustandsverwaltung: Wenn bei lang blockierenden Funktionen oder System Calls Pollchecks ausgelassen werden, führt der Collector den betreffenden Callback direkt aus
• In Umgebungen mit Multithreading werden Race Conditions verhindert und sicherer Pointer-Zugriff gewährleistet
• Über einen Stop-the-World-Modus werden Sonderfälle wie Debugging oder fork unterstützt; auch die Signalbehandlung ist stabil umgesetzt

FUGC-Collector-Loop

1. Auf einen GC-Trigger warten
2. Store Barrier aktivieren und Soft Handshake (No-op-Callback) ausführen
3. Black Allocation aktivieren (Vorab-Markierung neuer Objekte) und Cache-Reset-Callback ausführen
4. Globale Roots markieren
5. Soft Handshake ausführen (Stack-Scan- und Cache-Reset-Callbacks); wenn der Mark-Stack leer ist, zu 7 wechseln
6. Tracing (für jedes Objekt auf dem Mark-Stack Referenzen markieren; wiederholen, bis der Mark-Stack leer ist, dann zu 5 zurückkehren)
7. Store Barrier deaktivieren, Sweep vorbereiten, Soft Handshake zum erneuten Cache-Reset ausführen
8. Sweep ausführen (noch nicht gesweepte Seiten allokieren als black, bereits bearbeitete als white)
9. Erneut in die Schleife eintreten

Abgrenzung zu früherer Forschung und Optimierungen

• FUGC ähnelt dem DLG-Collector (Doligez-Leroy-Gonthier), bietet aber durch eine einfache Dijkstra-Barrier und die Nutzung eines Grey Stack eine intuitive und performante Implementierung der Store Barrier
• Der Fixpunkt-Ansatz konvergiert schnell und verursacht geringe Kosten
• Durch bitvector-SIMD-basiertes Sweeping erfolgt das Freigeben sehr schnell und beansprucht weniger als 5 % der gesamten GC-Zeit
• Performance-Optimierungen unter anderem durch Nutzung der Verse heap config

Bonusfunktionen (Erweiterbarkeit der Speicherverwaltung)

Objektfreigabe

• Beim Aufruf von free in C wird ein Objekt sofort als freigegeben markiert; spätere Zugriffe lösen einen Trap aus
• Fehlverhalten des GC durch dangling pointer wird verhindert
• Referenzen auf freigegebene Objekte werden auf ein Singleton-Free-Objekt umgeleitet, sodass auch nach einer Speicher-Reallokation eine sichere Erkennung möglich bleibt
• Durch ungenutzte Pointer ausgelöste, GC-verursachte Memory Leaks werden verhindert

Finalizer

• Eine Finalizer-Queue im Java-Stil lässt sich über benutzerdefinierte Queues und Thread-Verarbeitung flexibel implementieren

Schwache Referenzen

• Funktionieren wie weak reference in Java; eine separate Reference Queue gibt es nicht (phantom und soft references werden nicht unterstützt)

Schwache Maps

• Ähnlich wie JavaScript WeakMap, allerdings können alle Elemente iteriert und die Anzahl der Elemente geprüft werden

Fazit und Bedeutung

Mit FUGC bietet Fil-C starke Sicherheit und intuitive Exception-Behandlung bei falscher Verwendung von free

• Der Zugriff auf freigegebene Objekte oder doppeltes Freigeben löst zwingend einen Trap aus
• Werden Objekte nicht freigegeben, übernimmt der GC zuverlässig ihre Rückgewinnung
• Es werden verschiedene Memory-Management-Muster unterstützt, wodurch die Umgebung auch für Entwickler mit Erfahrung in C/Java/JavaScript vertraut wirkt

[GN⁺]

Hacker-News-Kommentare

• Hm, Fil-C könnte wirklich eine große Bedeutung bekommen. Es gibt viel Software, die ausschließlich in C existiert, daher braucht es aus meiner Sicht einen Ansatz, sie weiter zu pflegen. Bestehende C-Compiler nehmen große Sicherheitsrisiken in Kauf, um die Single-Core-Performance zu maximieren, und dieser Trade-off wirkt inzwischen schon etwas aus der Zeit gefallen. Die Support-Liste mit CPython, SQLite, OpenSSH, ICU, CMake, Perl5, Bash usw. ist wirklich beeindruckend. Ich glaube kaum, dass irgendeine dieser Softwares jemals in Rust neu geschrieben wird. Ich frage mich, ob sich Fil-C auch für Multitasking zwischen gegenseitig nicht vertrauenswürdigen Prozessen in Umgebungen ohne MMU nutzen lässt. Capability-basierte Sicherheit, Non-Blocking-Synchronisation usw. scheinen in die richtige Richtung zu gehen. Mich würde interessieren, ob das schon jemand tatsächlich benutzt hat. Berichten zufolge sinkt die Geschwindigkeit selbst im schlimmsten Fall nur um etwa das Vierfache, und der Name ist wirklich lustig. Phil’s way! Phil’s way!

  • Zu der Frage, ob mit Fil-C Multitasking zwischen nicht vertrauenswürdigen Prozessen auf Computern ohne MMU möglich ist: Grundsätzlich basiert FUGC zwar auf MMU-abhängigen OS-Funktionen, aber ich denke, man könnte auch eine Version bauen, die diese Abhängigkeiten entfernt. Zur Performance: Vierfach langsamer ist wirklich der Worst Case, und ich habe diese Zahl selbst genannt. Ich neige dazu, die Leistung immer realistisch zu messen und hartnäckig an Performance-Problemen zu arbeiten. Tatsächlich kann ich Software in der Fil-C-Version im Alltag nutzen und Programme, die ich sonst gern verwende, problemlos damit benutzen

  • Es wurde gesagt, die Liste unterstützter Software sei beeindruckend; dem stimme ich allgemein zu, aber bei den genannten Beispielen sehe ich es etwas anders. CPython, Perl5 usw. sind Laufzeitumgebungen von Sprachen, die ohnehin dafür bekannt sind, dass ihr GC langsam ist, daher wirkt es nicht besonders elegant, noch einen GC darüberzulegen, und der Geschwindigkeitsverlust könnte eher groß sein. Außerdem gibt es bereits teils Versuche, sie in Rust oder Go neu zu implementieren oder zu ersetzen; bei SQLite etwa Turso. Und solche Software sind sehr aktiv gepflegte grundlegende Projekte, sodass sie eines Tages vielleicht ohnehin intern refaktoriert oder nach Rust portiert werden. Eher geeignet erscheint mir Fil-C für weniger gepflegte, weniger performancekritische, aber weiterhin genutzte Software — so etwas wie C-Programme von vor 50 Jahren, die jemand gelegentlich noch hervorholt und benutzt

  • Eine Stärke von SQLite als in C geschriebener Software ist die gute Portierbarkeit auf nicht standardisierte Betriebssysteme. Ich habe es zum Beispiel direkt unter dem Embedded-RTOS μC/OS-II verwendet. Das Design eingebetteter Umgebungen unterscheidet sich ziemlich von PC/Servern; aus Performance-Gründen und um Speicherfragmentierung zu vermeiden, wird Speicher oft gar nicht freigegeben, sondern Objekte/Strukturen werden zur Wiederverwendung markiert. Das ist so etwas wie Custom-Heap-Allokation oder Pooling. SQLite-VFS-Dokumentation, Einführung in Micro-Controller OS

  • Es wurde gesagt, dass die als Beispiel genannte C-Software nicht in Rust neu geschrieben werde; ich frage mich, wie lange es wohl noch dauert, bis KI-basierte statische Analysetools so weit sind, Probleme in C-Code präzise zu finden und Feedback der Form „Hier tritt ein Fehler auf, so kann man ihn beheben“ zu geben. Wenn solche Tools wirklich erscheinen, könnte es am Ende vielleicht völlig in Ordnung sein, einfach weiter C zu verwenden

  • Nur als Hinweis: Fil-C unterstützt derzeit noch keine 32-Bit-Systeme (oder kleinere). Dokumentation zu Invisicaps in Fil-C

• Dieses Projekt wirkt wie ein seltener Fall, in dem Forschung und Praxis zugleich verfolgt werden. Solche Dinge werden sonst oft in großen IT-Unternehmen mit eigenen Teams und Werbeeinnahmen betrieben; mich würde interessieren, aus welchem Hintergrund Fil-C entstanden ist. Falls es nicht einfach nur ein persönliches Leidenschaftsprojekt ist: Wer hat es finanziert, wie viele Personenjahre sind hineingeflossen, und was ist das Endziel?

  • Für mich sieht das persönlich nach einem Leidenschaftsprojekt aus

  • Zur Frage nach dem Endziel: Im Projekt ist als Copyright 2024-2025 Epic Games, Inc. angegeben

• Allein dass Fil-C existiert, ist erfreulich. Selbst wenn sich solche Techniken in realen Programmen als wirksam erweisen, glauben viele Entwickler oft weiterhin, „dass so etwas nicht funktioniert“; schon die bloße Tatsache, dass es implementierbar ist, beendet auf einen Schlag unzählige Debatten

  • Mich interessieren Benchmark-Ergebnisse. Die größte Sorge bei so einem Ansatz ist doch wohl, dass die Performance in bestimmten Einsatzbereichen, in denen C/C++ weiterhin beliebt ist, massiv einbricht. Wenn Durchsatz, Latenz oder Speicherverbrauch am Ende zu sehr Sprachen wie Go ähneln, bleibt kaum noch ein guter Grund für die Wahl übrig

  • In Programmiersprachen gibt es seit der Assembler-Zeit immer den Gegensatz zwischen Performance und Diskurs. Die meisten Entwickler sind jedoch keine außergewöhnlichen Visionäre wie Ivan Suntherland, Alan Kay, Steve Jobs oder Bret Victor, sondern eher gewöhnliche Menschen, die etwas erst dann glauben, wenn sie es direkt vor sich funktionieren sehen. Deshalb gibt es bis heute so viele Kopien von UNIX und C, und viele leben eher davon, alte Visionen unverändert zu wiederholen, statt etwas Neues zu schaffen. Natürlich waren auch die beiden, die in den 1970ern UNIX und C geschaffen haben, großartige Visionäre

• Ich frage mich, warum man statt eines advancing-wavefront-Ansatzes keine retreating-wavefront-Strategie verwendet hat

• In bestehenden C-Programmen sind free(...)-Aufrufe oft bereits passend vorhanden, und wenn zusätzlich für alle Pointer noch eigene Bereichsinformationen verwaltet werden: Warum hat man sich dann für vollständiges GC entschieden? Stattdessen könnte eine temporal-checking-Technik nach dem Lock-and-Key-Prinzip (Referenz: Paper-Link) in Bezug auf Vorhersagbarkeit des Speicherverbrauchs, Performance und Scheduling besser sein. Ich vermute, dass vielleicht der Speicherbedarf für die Keys zu hoch ist, die Prüfungen zu lange dauern oder es in Multithreading-Umgebungen zu Race Conditions kommen könnte

  • Beim Lock-and-Key-Ansatz gibt es nichts von den cleveren Eigenschaften, die Fil-C besonders machen. Das Capability-Modell von Fil-C ist vollständig thread-safe, und in den meisten Fällen braucht es weder spezielle atomics noch Locking — das ist die Stärke daran

  • Interessant ist auch, dass Out-of-Bounds-Pointer-Arithmetik ohne Dereferenzierung erlaubt ist. Compiler nutzen solche UB-Bereiche ja gelegentlich für Optimierungen (relevante Stack-Overflow-Frage). Ich frage mich, ob im internen LLVM von Fil-C solche Optimierungen deaktiviert werden oder ob Pointer als Kombination aus „Basis + Offset“ verwaltet werden, sodass diese Möglichkeit grundsätzlich entfällt. Dann stellt sich natürlich auch die Frage, ob dadurch bestimmte Optimierungen verloren gehen, die sonst auf normale Pointer angewandt würden

• Sieht nach einem wirklich großartigen Projekt aus. Mir ist aufgefallen, dass der Fast Path von pollcheck einfach nur load-and-branch ist. Es gibt eine interessante Technik als Alternative zu solchen Branches, die im offiziellen Android-Blog im Beitrag "The secret to Android’s improved memory: the latest Android Runtime update" gut erklärt wird

  • Solche Optimierungen werden bei Poll Checks oft verwendet. Tatsächlich setzen die meisten Production-JVMs das bereits ein. Aber ich bin noch nicht an dem Punkt, an dem ich mich um solche Low-Level-Optimierungen kümmern sollte. Im Moment muss ich zuerst die noch offenen grundlegenden High-Level-Optimierungen angehen

• Ein C mit Nebenläufigkeitsunterstützung und GC, noch dazu mit non-moving GC — das ist wirklich faszinierend. Wenn ich bei einem mittelgroßen C-Projekt Laufzeitkosten um den Faktor 2 bis 3 gegen weniger Memory Bugs eintauschen könnte, wäre ich durchaus bereit dazu. Ich frage mich, wie einfach eine schrittweise Einführung ist. Geht das für jedes Ziel separat, oder muss man gleich die gesamte Toolchain austauschen?

• Mir sind C, Performance und Sicherheit alle wichtig. Dieses GC- und Capability-Modell ist attraktiv. Ich habe oft darüber nachgedacht, wie ein „sichereres C“ aussehen könnte, und mir das Capability-Konzept mehrmals angesehen, aber mit Compiler-Code kenne ich mich nicht gut aus. Ich frage mich, ob Windows-Support schwierig ist

  • Nur als Randbemerkung: Im ersten Satz fehlt das Oxford-Komma, deshalb habe ich ziemlich lange gebraucht, um den Sinn zu verstehen. So ein klares Beispiel dafür sieht man nicht oft

• Ich frage mich, wie der GC Root-Objekte verfolgt. Gibt es schon in der Kompilierphase einen Schritt, der die vom GC zu scannenden Roots markiert? Falls das jemand weiß, wäre eine Erklärung hilfreich

  • LLVM löst das, indem es Instruktionen einfügt, um die Stack Maps zu füllen

• Dieses Projekt ist wirklich erstaunlich. Fast schon seltsam, dass ich bisher noch nie davon gehört habe. Ich freue mich darauf, es einmal selbst auszuprobieren. Für produktive Dienste könnte es wegen der Performance-Grenzen schwierig sein, aber als Mittel, die Sicherheit bestimmter Programme direkt zu überprüfen, wirkt es ausgesprochen nützlich. Es fühlt sich umfassender an als die Sanitizer, die ich sonst verwende