De auteur optimaliseert de Garbage Collector (GC) van Plush, een door hemzelf ontwikkelde actor-gebaseerde programmeertaal. De initiële implementatie was traag (117ms voor één miljoen objecten) omdat er een HashMap werd gebruikt voor forwarding pointers om mutaties tijdens het verzenden van berichten te voorkomen. Hoewel een overstap naar FxHashMap de snelheid verbeterde, bleven cache-misses en overhead problematisch.
De uiteindelijke doorbraak kwam door de implementatie van het klassieke Cheney-kopieeralgoritme. Om het probleem met de berichtuitwisseling op te lossen, voegde de auteur een 'undo-list' toe die forwarding-pointers ongedaan maakt na het kopiëren. Dit bracht de collectietijd terug naar slechts 7ms.
Daarnaast is een mmap-techniek geïmplementeerd voor de message-allocator. Door vooraf een groot blok virtuele adresruimte te reserveren zonder direct fysiek RAM te verbruiken, kan de allocator dynamisch worden vergroot zonder dat bestaande pointers ongeldig worden. De auteur concludeert dat cache-efficiëntie en voorspelbare geheugentoegang cruciaal zijn en dat klassieke algoritmen vaak superieur blijven aan modernere, abstracte datastructuren zoals hashmaps voor dit soort taken.
De Plush Garbage Collector versnellen
Wie deze blog leest of mij volgt op X, weet dat ik de neiging heb om tussen verschillende zijprojecten te springen. Een tijd geleden heb ik bewust besloten mezelf toe te staan mijn motivatie te volgen en nieuwe ideeën te verkennen, omdat ik vind dat zijprojecten leuk moeten blijven en nooit een klusje mogen worden. Dat gezegd hebbende, merk ik dat ik af en toe denk aan een project dat ik een tijd geleden heb laten rusten, en hoe ik dat verder zou kunnen uitwerken.
Vorig jaar schreef ik een reeks blogposts over Plush, een speelgoedtaal in de stijl van Lox die ik heb gemaakt. Ik heb het ontwikkeld om te experimenteren met verschillende ontwerpidieën voor interpreters en virtual machines (VM's). Opvallend is dat het actor-gebaseerd parallellisme heeft en zo is ontworpen dat er geen globale VM-lock op enig kritiek pad zit, en er geen situatie is waarin de volledige VM voor iets moet pauzeren. Later implementeerde ik enkele basisoptimalisaties in de Plush-interpreter en schreef ik vervolgens een kopiërende Garbage Collector (GC) voor de VM. De GC zelf is niets bijzonders, maar wat het interessant maakt, is dat elke actor zijn eigen volledig onafhankelijke GC heeft. Elke actor kan een collectiecyclus uitvoeren zonder dat daar enige synchronisatie bij komt kijken. Wat echter ongelukkig is, is dat de prestaties van deze GC behoorlijk teleurstellend bleken.
Ik had een persoonlijk doel voor de Plush GC: ik wilde dat deze één miljoen live objecten in minder dan 20 milliseconden kon collecteren. Het idee was dat dit snel genoeg zou zijn om een 3D-game engine in Plush te bouwen zonder dat GC-pauzes merkbaar zouden zijn. Ik schreef een kleine microbenchmark, gcmanyobjs.psh, die een gelinkte lijst met een miljoen nodes alloceert en vervolgens in een loop de GC triggert, maar de prestaties kwamen niet in de buurt van mijn doel. Op mijn MacBook Air M5 kwam de collectietijd van deze implementatie uit op ongeveer 117 ms, wat meerdere keren te traag is.
De reden is dat ik een handige shortcut heb genomen bij het implementeren van mijn kopiërende GC. Een traditionele Cheney-kopiërende collector kopieert objecten van het ene geheugenblok (de from-space) naar het andere (de to-space). Hierbij wordt een forwarding pointer gebruikt die in de header van elk object staat, terwijl de to-space tegelijkertijd als werklijst dient om transitief de graaf van live objecten te doorlopen tijdens het kopieerproces.
In Plush heeft elke actor zijn eigen private allocator voor het alloceren van objecten, evenals een message-allocator die als buffer dient voor het ontvangen van berichten van andere actors. Wanneer een object als bericht wordt verzonden, kopieert de verzender dit naar de message-allocator van de ontvanger. Dit is gedaan om de verzender los te koppelen van de ontvanger, zodat zij niet hoeven te locken of synchroniseren om berichten uit te wisselen.
Ik wilde één kopieeralgoritme kunnen hergebruiken voor zowel de GC als voor het kopiëren van berichten naar de message-allocator van de ontvanger. Hiervoor wilde ik geen forwarding-pointers uit de heap van de verzender gebruiken, omdat dit objecten in de verzender zou muteren. In plaats daarvan gebruikte ik een hashmap die de correspondentie tussen objecten en hun kopieën bijhoudt. Ik dacht dat dit niet veel impact op de prestaties zou hebben, omdat het hashen van pointers snel is, maar ik had ongelijk.
Mijn vriend en collega Laurent Huberdeau wees me op iets basisstijgs dat ik tot dan toe niet wist: de standaard Rust HashMap gebruikt een beveiligde hashing-functie, specifiek ontworpen om bescherming te bieden tegen HashDoS. Dit heeft geen invloed op de functionaliteit, maar wel op de prestaties. Gelukkig is er een equivalent, FxHashMap, in de rustc_hash crate, die wordt onderhouden door het rust-lang project en een directe vervanger is. Laurent vond daarnaast een redundante hash-tabel lookup die vermeden kon worden. Deze eenvoudige wijzigingen zorgden ervoor dat de kopiërende GC meer dan twee keer zo snel werd, tot 43 ms op mijn M5-laptop. Veel sneller, maar nog steeds ver verwijderd van mijn oorspronkelijke doel van 20 ms.
Profiling laat zien dat het grootste deel van de overhead nog steeds uit de hashtabel komt. Er is echter slechter nieuws: de forwarding-pointer hashtabel zelf neemt meer ruimte in beslag dan de live data die tijdens de collectie wordt gekopieerd. Dat is logisch als je erover nadenkt. We kopiëren een gelinkte lijst; de lijst-nodes zijn erg klein, met slechts een next pointer en een waarde-veld. De entries in de hashtabel zijn zelf een paar pointers, maar bovendien heeft een hashmap een bepaalde hoeveelheid extra capaciteit (lege slots) nodig om goed te presteren, anders kun je te maken krijgen met hash-collisions en prestatieverlies. Daarbovenop zijn hash-functies bedoeld om onvoorspelbaar te zijn; de output moet een quasi-willekeurige distributie hebben. Vanuit het perspectief van cache-prestaties is dat eigenlijk verschrikkelijk. Het betekent dat we tijdens de GC overal in het geheugen terechtkomen, vaker dan bij de data die we kopiëren, en dat in een onvoorspelbaar patroon. Niet ideaal.
Er zijn andere inefficiënties in deze GC. In een traditionele Cheney GC wordt de to-space lineair doorlopen en dient deze als werklijst. We gebruiken de to-space zelf om bij te houden welke objecten we hebben gekopieerd en doorlopen vervolgens de pointers in deze objecten om andere live objecten te kopiëren. Als je dat niet hebt, heb je een aparte werklijst nodig. Dit kan een eenvoudige dynamische array zijn die als stack dient. Dat is niet het einde van de wereld, maar het kan extra allocaties, extra geheugengebruik en extra geheugentoegang toevoegen.
Het ergste deel van mijn implementatie was echter dat ik, nadat de objecten waren doorgestuurd, de hashmap een tweede keer doorliep om de doorgestuurde objecten te verwerken en pointers naar from-space objecten te vervangen door pointers naar hun kopieën in de to-space. Zoals eerder vermeld, slaat de hashmap pointers op in een quasi-willekeurige volgorde, waardoor we nu ook de from-space en de to-space in een onvoorspelbare volgorde benaderen.
Ik denk dat ik er ergens in mijn hoofd aan gewend was geraakt aan de aanname dat hashmaps een efficiënte datastructuur zijn. In inleidende informatica-lessen leer je dat je gemiddeld een tijdcomplexiteit van O(1) kunt behalen. Ze werken goed voor veel toepassingen. Maar als je het geheugengebruik en de cache-vriendelijkheid wilt optimaliseren voor maximale doorvoer, blijken ze dat misschien niet te zijn.
Ik zei oorspronkelijk dat de reden dat ik geen forwarding-pointers wilde gebruiken, was dat ik hetzelfde kopieeralgoritme gebruikte voor het verzenden van berichten, en ik wilde de objecten (of object-headers) in de heap van de verzender tijdens dat proces niet overschrijven. Er is echter een eenvoudige oplossing voor dat probleem: voor dit speciale geval kunnen we een lijst met doorgestuurde objecten bijhouden en na het kopiëren terugkomen om de forwarding-pointer writes ongedaan te maken. Dat klinkt inefficiënt, maar in de praktijk zijn berichten die naar andere actors worden verzonden meestal geen enorme grafen van objecten, en normaal GC-gebruik kan deze stap gewoon overslaan.
Op dat moment besloot ik de Plush GC te herschrijven om simpelweg het traditionele Cheney-kopieeralgoritme te volgen, met een toggle die ons in staat stelt een undo-list bij te houden om forwarding-pointers te verwijderen en object-headers te herstellen voor het speciale geval van berichten verzenden. Dit bracht onze GC-tijd voor een miljoen live objecten helemaal terug naar 7 ms, wat ongeveer 16,7x zo snel is als de naïeve implementatie waar we mee begonnen. Dat is een geweldige prestatieverbetering en het ligt ruim onder mijn doel van 20 ms. Ik heb zelfs een voorbeeldprogramma dat een roterende stadsgezicht rendert met ongeveer 2200 polygonen. Dit triggert regelmatig de GC omdat het 3D-vector- en matrixoperaties uitvoert en tonnen tijdelijke objecten alloceert. Voor dit specifieke programma is de GC-tijd minder dan 1 ms.
Voor de historische context: Cheney publiceerde in 1970 een paper over wat nu bekend staat als het Cheney-algoritme. Destijds werkte hij op een Ferranti Atlas 2 computer. Dit was een getransistoriseerde supercomputer uit het begin van de jaren zestig. Hij nam een hele grote kamer in beslag, gebruikte kerngeheugen (core memory) en had verrassend genoeg al een vroege vorm van cache. Ongeacht de cache-efficiëntie was geheugen destijds een kostbaar middel, en het gebruik van een forwarding-pointer is veel geheugenefficiënter dan het gebruik van een hulpdatastructuur.
Ik hoop dat deze conclusie niet te teleurstellend is, want we zijn in feite een cirkel rondgegaan naar de conclusie dat het oorspronkelijke Cheney GC-algoritme met forwarding-pointers veel efficiënter is. Een andere indicatie dat we respect moeten hebben voor de wijsheid van onze voorgangers en hun heilige publicaties. Toch is het goed om precies te begrijpen wat iets efficiënt maakt of niet, en hoeveel verschil zaken als cache-efficiëntie en voorspelbare geheugentoegangspatronen kunnen maken. Ook is het goed om te weten dat Rust's HashMap een beveiligingsrisico (security footgun) heeft ingeruild voor een prestatierisico (performance footgun).
Naast het versnellen van de GC heb ik nog een andere verbetering doorgevoerd, die zowel een beperking in Plush opheft als het geheugengebruik vermindert. Voorheen had ik geen logica om de message-allocator van een actor te vergroten. Dit betekende dat de berichtgrootte beperkt was tot 16 MB, een hardcoded constante. De message-allocator gebruikt bump pointer allocation net als een normale GC-heap, en het is lastig om deze te herdimensioneren omdat het heralloceren van de onderliggende opslag pointers naar berichten in de wachtrij ongeldig maakt. Dit betekent dat je de onderliggende opslag alleen kunt heralloceren wanneer de wachtrij leeg is en alle berichten door de ontvanger zijn geconsumeerd. Dat vereist op zijn beurt coördinatie tussen verzenders en de ontvanger. Als één actor een groot bericht probeert te verzenden, zou hij aan de ontvanger moeten communiceren dat de message-allocator vergroot moet worden, terwijl alle andere verzenders ondertussen zouden moeten wachten.
Er is echter een eenvoudigere oplossing. Er is een slimme mmap-truc die ik geloof dat ik van Alan Wu heb geleerd. Dit is gebruikt in YJIT, mijn eigen UVM-project, en ook in veel andere runtimes. Je kunt mmap gebruiken om vooraf een groot aaneengesloten blok virtuele adresruimte te reserveren met de MAPPRIVATE | MAPANONYMOUS flags en PROTNONE protectie. Hiermee vertel je het OS in feite dat er geen ander geheugen of andere resources in dit blok virtuele adresruimte geplaatst mogen worden, maar het geheugen wordt niet fysiek ondersteund door RAM, waardoor er geen RSS wordt verbruikt. Later kun je terugkomen en pagina's uit deze ruimte als PROTREAD | PROT_WRITE markeren met mprotect om ze toegankelijk te maken voor je programma. Dit geeft je genulde geheugen dat je kunt lezen en schrijven, maar het OS koppelt deze pagina's pas aan fysiek RAM zodra je er data in schrijft.
Wat belangrijk is om te weten, is dat de virtuele adresruimte zeer groot is — momenteel 128 TB op macOS en Linux (gebaseerd op 48-bit adressering) — en dus kan je initiële reservering zeer genereus zijn. Zelfs 512 GB is slechts een fractie van de beschikbare 128 TB. De implicatie hiervan is dat je in feite het equivalent hebt van een C++ std::vector of een Rust Vec die dynamisch naar believen kan worden vergroot, maar dat je altijd pointers binnen deze dynamisch-omvangrijke vector kunt behouden. Het vergroten van de vector en het verhogen van de capaciteit maakt oude pointers niet ongeldig. Je kunt de vector zelfs inkrimpen en pagina's teruggeven aan het OS zonder adressen te wijzigen. In de context van Plush betekent dit dat een verzender triviaal de message-allocator van de ontvanger kan vergroten, zonder dat er coördinatie met de ontvanger of andere verzenders nodig is. De ontvanger kan zijn message-allocator later inkrimpen als deze te groot is geworden, om zo geheugen terug te geven aan het OS.
Met de herschreven GC en de mmap-truc heeft Plush een GC die niet alleen veel sneller is (vermoedelijk goed genoeg voor een real-time game met veel allocaties), maar ook minder geheugen gebruikt. De collectie zelf gebruikt geen omvangrijke hashmap, en de baseline RSS is ook veel kleiner. Een triviaal programma zonder actors gebruikt 9,6 MB piek-RSS en start op in minder dan 10 ms. Een triviaal programma met 2000 actors gebruikt 224 MB piek-RSS en start op in 0,23 s. Niet slecht.
Wat betreft de volgende stappen heb ik verschillende ideeën om de prestaties van Plush te verbeteren of het dichter bij een "echte" programmeertaal te brengen. Eén ding dat opvalt is dat Plush een Rust tagged union gebruikt om zijn Value type te representeren (ook wel een "fat value" representatie genoemd). Dit zorgt voor mooie, leesbare code, maar het betekent ook dat we 16 bytes per waarde gebruiken wanneer rekening wordt gehouden met alignment. De meeste dynamische talen gebruiken een tagging scheme. Dat brengt enkele compromissen met zich mee, maar het zou het geheugengebruik aanzienlijk kunnen verkleinen. Plush gebruikt ook een stack-gebaseerde interpreter, terwijl een register-gebaseerde interpreter veel sneller zou kunnen zijn. Ook heb ik me afgevraagd hoe haalbaar het zou zijn om een LLM een naïeve JIT-compiler voor Plush te laten schrijven.
Als zijnoot vraag je je misschien af waarom ik een kopiërende GC voor Plush heb gekozen. Misschien zou een mark-and-sweep GC eigenlijk sneller zijn. Mijn motivatie was dat kopiërende GC's zeer snelle bump allocation kunnen doen (geweldig voor een dynamische taal die veel alloceert), en ze hebben de mooie eigenschap dat de collectietijd proportioneel is aan de live data die wordt gekopieerd, in plaats van aan de totale heap-grootte. Er is ook een theoretisch cache-voordeel doordat gerelateerde data dicht bij elkaar in het geheugen staan. Het zou kunnen dat die aannames onjuist zijn en mark-and-sweep wint. Als je nieuwsgierig bent en wilt experimenteren, heb ik benchmarks/gcmanyobjs.psh en benchmarks/gcallocspeed.psh aan de Plush-repo toegevoegd. Je favoriete coding agent kan Plush wellicht in minder dan 30 minuten refactoren om een mark-and-sweep GC te gebruiken. Als iemand dit experiment wil proberen, ben ik benieuwd naar het resultaat. Zorg er alleen voor dat je de benchmarks uitvoert met cargo run --release en ook cargo test draait om te controleren of de tests nog steeds slagen.
De Plush Garbage Collector versnellen
Wie deze blog leest of mij volgt op X, weet dat ik de neiging heb om tussen verschillende zijprojecten te springen. Een tijd geleden heb ik bewust besloten mezelf toe te staan mijn motivatie te volgen en nieuwe ideeën te verkennen, omdat ik vind dat zijprojecten leuk moeten blijven en nooit een klusje mogen worden. Dat gezegd hebbende, merk ik dat ik af en toe denk aan een project dat ik een tijd geleden heb laten rusten, en hoe ik dat verder zou kunnen uitwerken.
Vorig jaar schreef ik een reeks blogposts over Plush, een speelgoedtaal in de stijl van Lox die ik heb gemaakt. Ik heb het ontwikkeld om te experimenteren met verschillende ontwerpidieën voor interpreters en virtual machines (VM's). Opvallend is dat het actor-gebaseerd parallellisme heeft en zo is ontworpen dat er geen globale VM-lock op enig kritiek pad zit, en er geen situatie is waarin de volledige VM voor iets moet pauzeren. Later implementeerde ik enkele basisoptimalisaties in de Plush-interpreter en schreef ik vervolgens een kopiërende Garbage Collector (GC) voor de VM. De GC zelf is niets bijzonders, maar wat het interessant maakt, is dat elke actor zijn eigen volledig onafhankelijke GC heeft. Elke actor kan een collectiecyclus uitvoeren zonder dat daar enige synchronisatie bij komt kijken. Wat echter ongelukkig is, is dat de prestaties van deze GC behoorlijk teleurstellend bleken.
Ik had een persoonlijk doel voor de Plush GC: ik wilde dat deze één miljoen live objecten in minder dan 20 milliseconden kon collecteren. Het idee was dat dit snel genoeg zou zijn om een 3D-game engine in Plush te bouwen zonder dat GC-pauzes merkbaar zouden zijn. Ik schreef een kleine microbenchmark, gcmanyobjs.psh, die een gelinkte lijst met een miljoen nodes alloceert en vervolgens in een loop de GC triggert, maar de prestaties kwamen niet in de buurt van mijn doel. Op mijn MacBook Air M5 kwam de collectietijd van deze implementatie uit op ongeveer 117 ms, wat meerdere keren te traag is.
De reden is dat ik een handige shortcut heb genomen bij het implementeren van mijn kopiërende GC. Een traditionele Cheney-kopiërende collector kopieert objecten van het ene geheugenblok (de from-space) naar het andere (de to-space). Hierbij wordt een forwarding pointer gebruikt die in de header van elk object staat, terwijl de to-space tegelijkertijd als werklijst dient om transitief de graaf van live objecten te doorlopen tijdens het kopieerproces.
In Plush heeft elke actor zijn eigen private allocator voor het alloceren van objecten, evenals een message-allocator die als buffer dient voor het ontvangen van berichten van andere actors. Wanneer een object als bericht wordt verzonden, kopieert de verzender dit naar de message-allocator van de ontvanger. Dit is gedaan om de verzender los te koppelen van de ontvanger, zodat zij niet hoeven te locken of synchroniseren om berichten uit te wisselen.
Ik wilde één kopieeralgoritme kunnen hergebruiken voor zowel de GC als voor het kopiëren van berichten naar de message-allocator van de ontvanger. Hiervoor wilde ik geen forwarding-pointers uit de heap van de verzender gebruiken, omdat dit objecten in de verzender zou muteren. In plaats daarvan gebruikte ik een hashmap die de correspondentie tussen objecten en hun kopieën bijhoudt. Ik dacht dat dit niet veel impact op de prestaties zou hebben, omdat het hashen van pointers snel is, maar ik had ongelijk.
Mijn vriend en collega Laurent Huberdeau wees me op iets basisstijgs dat ik tot dan toe niet wist: de standaard Rust HashMap gebruikt een beveiligde hashing-functie, specifiek ontworpen om bescherming te bieden tegen HashDoS. Dit heeft geen invloed op de functionaliteit, maar wel op de prestaties. Gelukkig is er een equivalent, FxHashMap, in de rustc_hash crate, die wordt onderhouden door het rust-lang project en een directe vervanger is. Laurent vond daarnaast een redundante hash-tabel lookup die vermeden kon worden. Deze eenvoudige wijzigingen zorgden ervoor dat de kopiërende GC meer dan twee keer zo snel werd, tot 43 ms op mijn M5-laptop. Veel sneller, maar nog steeds ver verwijderd van mijn oorspronkelijke doel van 20 ms.
Profiling laat zien dat het grootste deel van de overhead nog steeds uit de hashtabel komt. Er is echter slechter nieuws: de forwarding-pointer hashtabel zelf neemt meer ruimte in beslag dan de live data die tijdens de collectie wordt gekopieerd. Dat is logisch als je erover nadenkt. We kopiëren een gelinkte lijst; de lijst-nodes zijn erg klein, met slechts een next pointer en een waarde-veld. De entries in de hashtabel zijn zelf een paar pointers, maar bovendien heeft een hashmap een bepaalde hoeveelheid extra capaciteit (lege slots) nodig om goed te presteren, anders kun je te maken krijgen met hash-collisions en prestatieverlies. Daarbovenop zijn hash-functies bedoeld om onvoorspelbaar te zijn; de output moet een quasi-willekeurige distributie hebben. Vanuit het perspectief van cache-prestaties is dat eigenlijk verschrikkelijk. Het betekent dat we tijdens de GC overal in het geheugen terechtkomen, vaker dan bij de data die we kopiëren, en dat in een onvoorspelbaar patroon. Niet ideaal.
Er zijn andere inefficiënties in deze GC. In een traditionele Cheney GC wordt de to-space lineair doorlopen en dient deze als werklijst. We gebruiken de to-space zelf om bij te houden welke objecten we hebben gekopieerd en doorlopen vervolgens de pointers in deze objecten om andere live objecten te kopiëren. Als je dat niet hebt, heb je een aparte werklijst nodig. Dit kan een eenvoudige dynamische array zijn die als stack dient. Dat is niet het einde van de wereld, maar het kan extra allocaties, extra geheugengebruik en extra geheugentoegang toevoegen.
Het ergste deel van mijn implementatie was echter dat ik, nadat de objecten waren doorgestuurd, de hashmap een tweede keer doorliep om de doorgestuurde objecten te verwerken en pointers naar from-space objecten te vervangen door pointers naar hun kopieën in de to-space. Zoals eerder vermeld, slaat de hashmap pointers op in een quasi-willekeurige volgorde, waardoor we nu ook de from-space en de to-space in een onvoorspelbare volgorde benaderen.
Ik denk dat ik er ergens in mijn hoofd aan gewend was geraakt aan de aanname dat hashmaps een efficiënte datastructuur zijn. In inleidende informatica-lessen leer je dat je gemiddeld een tijdcomplexiteit van O(1) kunt behalen. Ze werken goed voor veel toepassingen. Maar als je het geheugengebruik en de cache-vriendelijkheid wilt optimaliseren voor maximale doorvoer, blijken ze dat misschien niet te zijn.
Ik zei oorspronkelijk dat de reden dat ik geen forwarding-pointers wilde gebruiken, was dat ik hetzelfde kopieeralgoritme gebruikte voor het verzenden van berichten, en ik wilde de objecten (of object-headers) in de heap van de verzender tijdens dat proces niet overschrijven. Er is echter een eenvoudige oplossing voor dat probleem: voor dit speciale geval kunnen we een lijst met doorgestuurde objecten bijhouden en na het kopiëren terugkomen om de forwarding-pointer writes ongedaan te maken. Dat klinkt inefficiënt, maar in de praktijk zijn berichten die naar andere actors worden verzonden meestal geen enorme grafen van objecten, en normaal GC-gebruik kan deze stap gewoon overslaan.
Op dat moment besloot ik de Plush GC te herschrijven om simpelweg het traditionele Cheney-kopieeralgoritme te volgen, met een toggle die ons in staat stelt een undo-list bij te houden om forwarding-pointers te verwijderen en object-headers te herstellen voor het speciale geval van berichten verzenden. Dit bracht onze GC-tijd voor een miljoen live objecten helemaal terug naar 7 ms, wat ongeveer 16,7x zo snel is als de naïeve implementatie waar we mee begonnen. Dat is een geweldige prestatieverbetering en het ligt ruim onder mijn doel van 20 ms. Ik heb zelfs een voorbeeldprogramma dat een roterende stadsgezicht rendert met ongeveer 2200 polygonen. Dit triggert regelmatig de GC omdat het 3D-vector- en matrixoperaties uitvoert en tonnen tijdelijke objecten alloceert. Voor dit specifieke programma is de GC-tijd minder dan 1 ms.
Voor de historische context: Cheney publiceerde in 1970 een paper over wat nu bekend staat als het Cheney-algoritme. Destijds werkte hij op een Ferranti Atlas 2 computer. Dit was een getransistoriseerde supercomputer uit het begin van de jaren zestig. Hij nam een hele grote kamer in beslag, gebruikte kerngeheugen (core memory) en had verrassend genoeg al een vroege vorm van cache. Ongeacht de cache-efficiëntie was geheugen destijds een kostbaar middel, en het gebruik van een forwarding-pointer is veel geheugenefficiënter dan het gebruik van een hulpdatastructuur.
Ik hoop dat deze conclusie niet te teleurstellend is, want we zijn in feite een cirkel rondgegaan naar de conclusie dat het oorspronkelijke Cheney GC-algoritme met forwarding-pointers veel efficiënter is. Een andere indicatie dat we respect moeten hebben voor de wijsheid van onze voorgangers en hun heilige publicaties. Toch is het goed om precies te begrijpen wat iets efficiënt maakt of niet, en hoeveel verschil zaken als cache-efficiëntie en voorspelbare geheugentoegangspatronen kunnen maken. Ook is het goed om te weten dat Rust's HashMap een beveiligingsrisico (security footgun) heeft ingeruild voor een prestatierisico (performance footgun).
Naast het versnellen van de GC heb ik nog een andere verbetering doorgevoerd, die zowel een beperking in Plush opheft als het geheugengebruik vermindert. Voorheen had ik geen logica om de message-allocator van een actor te vergroten. Dit betekende dat de berichtgrootte beperkt was tot 16 MB, een hardcoded constante. De message-allocator gebruikt bump pointer allocation net als een normale GC-heap, en het is lastig om deze te herdimensioneren omdat het heralloceren van de onderliggende opslag pointers naar berichten in de wachtrij ongeldig maakt. Dit betekent dat je de onderliggende opslag alleen kunt heralloceren wanneer de wachtrij leeg is en alle berichten door de ontvanger zijn geconsumeerd. Dat vereist op zijn beurt coördinatie tussen verzenders en de ontvanger. Als één actor een groot bericht probeert te verzenden, zou hij aan de ontvanger moeten communiceren dat de message-allocator vergroot moet worden, terwijl alle andere verzenders ondertussen zouden moeten wachten.
Er is echter een eenvoudigere oplossing. Er is een slimme mmap-truc die ik geloof dat ik van Alan Wu heb geleerd. Dit is gebruikt in YJIT, mijn eigen UVM-project, en ook in veel andere runtimes. Je kunt mmap gebruiken om vooraf een groot aaneengesloten blok virtuele adresruimte te reserveren met de MAPPRIVATE | MAPANONYMOUS flags en PROTNONE protectie. Hiermee vertel je het OS in feite dat er geen ander geheugen of andere resources in dit blok virtuele adresruimte geplaatst mogen worden, maar het geheugen wordt niet fysiek ondersteund door RAM, waardoor er geen RSS wordt verbruikt. Later kun je terugkomen en pagina's uit deze ruimte als PROTREAD | PROT_WRITE markeren met mprotect om ze toegankelijk te maken voor je programma. Dit geeft je genulde geheugen dat je kunt lezen en schrijven, maar het OS koppelt deze pagina's pas aan fysiek RAM zodra je er data in schrijft.
Wat belangrijk is om te weten, is dat de virtuele adresruimte zeer groot is — momenteel 128 TB op macOS en Linux (gebaseerd op 48-bit adressering) — en dus kan je initiële reservering zeer genereus zijn. Zelfs 512 GB is slechts een fractie van de beschikbare 128 TB. De implicatie hiervan is dat je in feite het equivalent hebt van een C++ std::vector of een Rust Vec die dynamisch naar believen kan worden vergroot, maar dat je altijd pointers binnen deze dynamisch-omvangrijke vector kunt behouden. Het vergroten van de vector en het verhogen van de capaciteit maakt oude pointers niet ongeldig. Je kunt de vector zelfs inkrimpen en pagina's teruggeven aan het OS zonder adressen te wijzigen. In de context van Plush betekent dit dat een verzender triviaal de message-allocator van de ontvanger kan vergroten, zonder dat er coördinatie met de ontvanger of andere verzenders nodig is. De ontvanger kan zijn message-allocator later inkrimpen als deze te groot is geworden, om zo geheugen terug te geven aan het OS.
Met de herschreven GC en de mmap-truc heeft Plush een GC die niet alleen veel sneller is (vermoedelijk goed genoeg voor een real-time game met veel allocaties), maar ook minder geheugen gebruikt. De collectie zelf gebruikt geen omvangrijke hashmap, en de baseline RSS is ook veel kleiner. Een triviaal programma zonder actors gebruikt 9,6 MB piek-RSS en start op in minder dan 10 ms. Een triviaal programma met 2000 actors gebruikt 224 MB piek-RSS en start op in 0,23 s. Niet slecht.
Wat betreft de volgende stappen heb ik verschillende ideeën om de prestaties van Plush te verbeteren of het dichter bij een "echte" programmeertaal te brengen. Eén ding dat opvalt is dat Plush een Rust tagged union gebruikt om zijn Value type te representeren (ook wel een "fat value" representatie genoemd). Dit zorgt voor mooie, leesbare code, maar het betekent ook dat we 16 bytes per waarde gebruiken wanneer rekening wordt gehouden met alignment. De meeste dynamische talen gebruiken een tagging scheme. Dat brengt enkele compromissen met zich mee, maar het zou het geheugengebruik aanzienlijk kunnen verkleinen. Plush gebruikt ook een stack-gebaseerde interpreter, terwijl een register-gebaseerde interpreter veel sneller zou kunnen zijn. Ook heb ik me afgevraagd hoe haalbaar het zou zijn om een LLM een naïeve JIT-compiler voor Plush te laten schrijven.
Als zijnoot vraag je je misschien af waarom ik een kopiërende GC voor Plush heb gekozen. Misschien zou een mark-and-sweep GC eigenlijk sneller zijn. Mijn motivatie was dat kopiërende GC's zeer snelle bump allocation kunnen doen (geweldig voor een dynamische taal die veel alloceert), en ze hebben de mooie eigenschap dat de collectietijd proportioneel is aan de live data die wordt gekopieerd, in plaats van aan de totale heap-grootte. Er is ook een theoretisch cache-voordeel doordat gerelateerde data dicht bij elkaar in het geheugen staan. Het zou kunnen dat die aannames onjuist zijn en mark-and-sweep wint. Als je nieuwsgierig bent en wilt experimenteren, heb ik benchmarks/gcmanyobjs.psh en benchmarks/gcallocspeed.psh aan de Plush-repo toegevoegd. Je favoriete coding agent kan Plush wellicht in minder dan 30 minuten refactoren om een mark-and-sweep GC te gebruiken. Als iemand dit experiment wil proberen, ben ik benieuwd naar het resultaat. Zorg er alleen voor dat je de benchmarks uitvoert met cargo run --release en ook cargo test draait om te controleren of de tests nog steeds slagen.
Groetjes,