THC (Turbo Haskell-compiler) is een project dat Haskell-programma's uitvoerbaar maakt op de JVM. Terwijl GHC verantwoordelijk blijft voor het parsen, typechecken en optimaliseren van de code, neemt THC het over vanaf de GHC Core-fase door deze te compileren via Truffle en GraalVM.
De belangrijkste technische kenmerken zijn:
- Flexibiliteit: Ondersteuning voor zowel JIT (Just-In-Time) als AOT (Ahead-Of-Time) compilatie via Native Image.
- Polyglotte FFI: Een interface waarmee Haskell direct bibliotheken uit Python, Ruby, R en JavaScript kan gebruiken met minimale overhead.
- Concurrency & SIMD: Ondersteuning voor Project Loom (green threading) en het gebruik van de Java Vector API voor runtime SIMD-optimalisaties.
- Tail Call Optimalisatie: Een innovatieve aanpak met Bloom-filters en code-transformaties om de beperkingen van de JVM wat betreft recursie en stackframes te omzeilen.
Hoewel de prestaties momenteel nog in ontwikkeling zijn en variëren ten opzichte van GHC, is THC al in staat om complexe software zoals pandoc en zelfs de GHC-compiler zelf te draaien.
Turbo Haskell
Precies een week geleden begon ik (als grap) met het schrijven van THC, mijn "Turbo Haskell-compiler", terwijl ik op vakantie was bij Bartosz Milewski.
Inmiddels is het project iets gegroeid. THC implementeert nu alle prim-ops van GHC 9.14.1 en biedt een JIT (Just-In-Time) compiler voor GHC Core die Haskell op de JVM draait. Het maakt gebruik van de aanpak voor het draaien van typed functionele talen die ik enkele jaren geleden ontwikkelde in Cadenza, gebruikmakend van Truffle en GraalVM.
GHC blijft verantwoordelijk voor het parsen, typechecken, desugaring en de Core-optimalisatie. THC neemt het vanaf dat punt over door die Core te compileren en uit te voeren via een eigen runtime op Truffle/GraalVM. Geavanceerde taalfuncties zoals Template Haskell en Linear Haskell worden volledig ondersteund.
Hoewel het gebruikt kan worden als een JIT voor Haskell op GHC-niveau, ondersteunt het ook ahead-of-time (AOT) compilatie met Native Image, waardoor het in staat is om executables te produceren. THC is in staat om een aantal Haskell-programma's via JIT of AOT te compileren, waaronder pandoc, happy, alex en, sinds vandaag, zelfs GHC zelf!
THC resolveert pakketten via Cabal en ondersteunt volledig pakketten met meerdere bibliotheken, inclusief Backpack.
Bibliotheken lenen
THC biedt een polyglotte FFI (Foreign Function Interface) naar Python, Ruby, R en JavaScript. Hiermee kan Haskell bibliotheken uit andere talen gebruiken en hun output direct in een JIT-gecompileerd Haskell-programma brengen. De conversie tussen Data.Text en Truffle-strings via de FFI is zero-copy voor UTF-8-gecodeerde strings binnen andere polyglotte talen.
Het idee is dat als je een data frame nodig hebt, een LLM wilt draaien of een D3.js-visualisatie wilt maken, je de Text simpelweg via foreign imports naar buiten moet sturen. Bindingen in de stijl van inline-<taalnaam> op basis van quasi-quotation zouden waarschijnlijk ook eenvoudig te implementeren zijn.
C/C++ onderdelen in Haskell-bibliotheken worden uitgevoerd via FFI naar native-mode Sulong (LLVM op de JVM). Managed-mode Sulong, waarbij LLVM wordt geïnterpreteerd binnen de JVM en pointers worden beheerd en garbage-collected, is ook beschikbaar, maar wordt niet gebruikt door het normale foreign import-pad.
Evaluatie en concurrency
Intern ondersteunt THC twee verschillende backends voor Truffle-evaluatie: een bytecode-gebaseerde JIT-target en een traditionele AST-gebaseerde JIT-target. Beiden kunnen in een single-threaded of multi-threaded stijl draaien, waarbij voor die laatste optie extra locking wordt toegevoegd. Het ondersteunt ook de GHC-bytecode zelf, waardoor het BCO-code kan draaien zoals geproduceerd door GHCi.
THC ondersteunt volledig throwTo, asynchrone exceptions die hernieuwbare code achterlaten, en masking.
Daarnaast ondersteunt THC zowel "normale" Java-threading als Project Loom. Op basis daarvan biedt het lichtgewicht GHC-stijl "green threading" met een HEC-stijl runtime-executor, wat goedkope MVars en vergelijkbare constructies mogelijk maakt.
SIMD
THC ondersteunt SIMD via het relatief beperkte aanbod van beschikbare GHC prim-ops, maar kan verder gaan door runtime-selectie van de SIMD "species" breedte mogelijk te maken. Loops kunnen vervolgens via de incubating Vector API (jdk.incubator.vector) worden JIT-gecompileerd met gebruik van deze informatie. Hierdoor begint de JIT zijn waarde echt te bewijzen.
In feite is er niets dat de runtime verhindert om volledige RuntimeRep-polymorfe code op runtime aan te bieden, behalve het feit dat we geen Core hebben die gebruikmaakt van die vrijheid.
Tail calls
Hete tail calls worden omgezet in loops. Wanneer de uitvoering moet terugvallen op gewone aanroepen, ontwindt THC periodiek de opgehoopte stackframes.
Eerdere pogingen om functionele code op de JVM te draaien, zoals de programmeertaal Eta en het ontwerp dat ik met Runar Bjarnason gebruikte voor het trampolineren van Scalaz-monaden, maakten gebruik van een trampoline-mechanisme. THC gebruikt in plaats daarvan een code-transformatie-truc om hete tail calls binnen strakke basic-block-stijl loops met zij-exits te houden.
Tijdens recursie in de tracing-modus vult THC een 64-bit Bloom-filter om waarschijnlijke recursieve tail calls te detecteren. Wanneer er een waarschijnlijke hit wordt gevonden, gooit het een slow-path exception om de continuatie met de lanceersite te verbinden. Vervolgens zorgen aangepaste Truffle-nodes ervoor dat Graal de huidige tail-call loop over functielichamen heen transformeert in een strakke loop. False positives betekenen extra werk op het slow-path; ze veranderen het resultaat van het programma niet.
Wanneer latere codepaden divergeren, probeert THC extra zij-loops te maken, zoals een tracing JIT, totdat de limieten van de JVM voor de grootte van het functielichaam worden bereikt. Op dat punt zal het uiteindelijk een tail call "spillen", waardoor er een stackframe "lekt".
Dat lek is tijdelijk. We kunnen de opgehoopte stackframes compact maken met een truc die enigszins lijkt op de garbage collection-strategie van CHICKEN Scheme, waarbij we de mechanieken hergebruiken die nodig waren om hernieuwbare code te ondersteunen in het bijzijn van asynchrone exceptions. Het resultaat is dat hete loops inderdaad zeer heet kunnen draaien.
Bij het benchmarken van Data.Map in het bijzonder, ontdekte ik dat er ongeveer 66 fallback-trampoline-aanroepen nodig waren tegenover enkele miljoenen fast-path aanroepen.
Prestaties
De runtime kan ook gebruikmaken van compressed ordinary object pointers (compressed oops). Deze representeren heap-referenties als 32-bit offsets in plaats van volledige 64-bit pointers, wat het geheugenbeslag van referenties vermindert en helpt om meer data in de cache te passen. Met de gebruikelijke 8-byte object-uitlijning van de JVM beperkt dit de heap tot ongeveer 32 GB wanneer in deze modus wordt gedraaid.
Prestaties waren een belangrijk aandachtspunt tijdens de eerste paar dagen van de ontwikkeling. Voor tests op Data.Map en vergelijkbare zaken was ik in staat om, na de warm-up fase, prestaties te behalen in een bereik van 3× sneller tot 3× langzamer dan GHC, waarbij het meestal rond de 10–20% langzamer dan GHC schommelde. Dat gezegd hebbende, we hebben de afgelopen dagen niet gebenchmarkt omdat we raceden voor bredere coverage, wat in de tussentijd heeft geleid tot een prestatieverlies van ongeveer 10× op enkele eenvoudige benchmarks. De ontwikkelingsinspanningen zijn erop gericht deze zaken onder controle te houden.
We hebben nog niet getest of stack-groei op non-tail-call paden begrensd blijft ten opzichte van het stack-gebruik van GHC. Het waarborgen van die grens is mogelijk toekomstig werk.
Ontwikkeling
De code is beschikbaar op github.com/ekmett/thc, met documentatie over hoe je THC bouwt, draait en gebruikt.
De ontwikkeling vindt plaats op irc.libera.chat in het ##thc kanaal.
Doe mee.
— Edward Kmett
Turbo Haskell
Precies een week geleden begon ik (als grap) met het schrijven van THC, mijn "Turbo Haskell-compiler", terwijl ik op vakantie was bij Bartosz Milewski.
Inmiddels is het project iets gegroeid. THC implementeert nu alle prim-ops van GHC 9.14.1 en biedt een JIT (Just-In-Time) compiler voor GHC Core die Haskell op de JVM draait. Het maakt gebruik van de aanpak voor het draaien van typed functionele talen die ik enkele jaren geleden ontwikkelde in Cadenza, gebruikmakend van Truffle en GraalVM.
GHC blijft verantwoordelijk voor het parsen, typechecken, desugaring en de Core-optimalisatie. THC neemt het vanaf dat punt over door die Core te compileren en uit te voeren via een eigen runtime op Truffle/GraalVM. Geavanceerde taalfuncties zoals Template Haskell en Linear Haskell worden volledig ondersteund.
Hoewel het gebruikt kan worden als een JIT voor Haskell op GHC-niveau, ondersteunt het ook ahead-of-time (AOT) compilatie met Native Image, waardoor het in staat is om executables te produceren. THC is in staat om een aantal Haskell-programma's via JIT of AOT te compileren, waaronder pandoc, happy, alex en, sinds vandaag, zelfs GHC zelf!
THC resolveert pakketten via Cabal en ondersteunt volledig pakketten met meerdere bibliotheken, inclusief Backpack.
Bibliotheken lenen
THC biedt een polyglotte FFI (Foreign Function Interface) naar Python, Ruby, R en JavaScript. Hiermee kan Haskell bibliotheken uit andere talen gebruiken en hun output direct in een JIT-gecompileerd Haskell-programma brengen. De conversie tussen Data.Text en Truffle-strings via de FFI is zero-copy voor UTF-8-gecodeerde strings binnen andere polyglotte talen.
Het idee is dat als je een data frame nodig hebt, een LLM wilt draaien of een D3.js-visualisatie wilt maken, je de Text simpelweg via foreign imports naar buiten moet sturen. Bindingen in de stijl van inline-<taalnaam> op basis van quasi-quotation zouden waarschijnlijk ook eenvoudig te implementeren zijn.
C/C++ onderdelen in Haskell-bibliotheken worden uitgevoerd via FFI naar native-mode Sulong (LLVM op de JVM). Managed-mode Sulong, waarbij LLVM wordt geïnterpreteerd binnen de JVM en pointers worden beheerd en garbage-collected, is ook beschikbaar, maar wordt niet gebruikt door het normale foreign import-pad.
Evaluatie en concurrency
Intern ondersteunt THC twee verschillende backends voor Truffle-evaluatie: een bytecode-gebaseerde JIT-target en een traditionele AST-gebaseerde JIT-target. Beiden kunnen in een single-threaded of multi-threaded stijl draaien, waarbij voor die laatste optie extra locking wordt toegevoegd. Het ondersteunt ook de GHC-bytecode zelf, waardoor het BCO-code kan draaien zoals geproduceerd door GHCi.
THC ondersteunt volledig throwTo, asynchrone exceptions die hernieuwbare code achterlaten, en masking.
Daarnaast ondersteunt THC zowel "normale" Java-threading als Project Loom. Op basis daarvan biedt het lichtgewicht GHC-stijl "green threading" met een HEC-stijl runtime-executor, wat goedkope MVars en vergelijkbare constructies mogelijk maakt.
SIMD
THC ondersteunt SIMD via het relatief beperkte aanbod van beschikbare GHC prim-ops, maar kan verder gaan door runtime-selectie van de SIMD "species" breedte mogelijk te maken. Loops kunnen vervolgens via de incubating Vector API (jdk.incubator.vector) worden JIT-gecompileerd met gebruik van deze informatie. Hierdoor begint de JIT zijn waarde echt te bewijzen.
In feite is er niets dat de runtime verhindert om volledige RuntimeRep-polymorfe code op runtime aan te bieden, behalve het feit dat we geen Core hebben die gebruikmaakt van die vrijheid.
Tail calls
Hete tail calls worden omgezet in loops. Wanneer de uitvoering moet terugvallen op gewone aanroepen, ontwindt THC periodiek de opgehoopte stackframes.
Eerdere pogingen om functionele code op de JVM te draaien, zoals de programmeertaal Eta en het ontwerp dat ik met Runar Bjarnason gebruikte voor het trampolineren van Scalaz-monaden, maakten gebruik van een trampoline-mechanisme. THC gebruikt in plaats daarvan een code-transformatie-truc om hete tail calls binnen strakke basic-block-stijl loops met zij-exits te houden.
Tijdens recursie in de tracing-modus vult THC een 64-bit Bloom-filter om waarschijnlijke recursieve tail calls te detecteren. Wanneer er een waarschijnlijke hit wordt gevonden, gooit het een slow-path exception om de continuatie met de lanceersite te verbinden. Vervolgens zorgen aangepaste Truffle-nodes ervoor dat Graal de huidige tail-call loop over functielichamen heen transformeert in een strakke loop. False positives betekenen extra werk op het slow-path; ze veranderen het resultaat van het programma niet.
Wanneer latere codepaden divergeren, probeert THC extra zij-loops te maken, zoals een tracing JIT, totdat de limieten van de JVM voor de grootte van het functielichaam worden bereikt. Op dat punt zal het uiteindelijk een tail call "spillen", waardoor er een stackframe "lekt".
Dat lek is tijdelijk. We kunnen de opgehoopte stackframes compact maken met een truc die enigszins lijkt op de garbage collection-strategie van CHICKEN Scheme, waarbij we de mechanieken hergebruiken die nodig waren om hernieuwbare code te ondersteunen in het bijzijn van asynchrone exceptions. Het resultaat is dat hete loops inderdaad zeer heet kunnen draaien.
Bij het benchmarken van Data.Map in het bijzonder, ontdekte ik dat er ongeveer 66 fallback-trampoline-aanroepen nodig waren tegenover enkele miljoenen fast-path aanroepen.
Prestaties
De runtime kan ook gebruikmaken van compressed ordinary object pointers (compressed oops). Deze representeren heap-referenties als 32-bit offsets in plaats van volledige 64-bit pointers, wat het geheugenbeslag van referenties vermindert en helpt om meer data in de cache te passen. Met de gebruikelijke 8-byte object-uitlijning van de JVM beperkt dit de heap tot ongeveer 32 GB wanneer in deze modus wordt gedraaid.
Prestaties waren een belangrijk aandachtspunt tijdens de eerste paar dagen van de ontwikkeling. Voor tests op Data.Map en vergelijkbare zaken was ik in staat om, na de warm-up fase, prestaties te behalen in een bereik van 3× sneller tot 3× langzamer dan GHC, waarbij het meestal rond de 10–20% langzamer dan GHC schommelde. Dat gezegd hebbende, we hebben de afgelopen dagen niet gebenchmarkt omdat we raceden voor bredere coverage, wat in de tussentijd heeft geleid tot een prestatieverlies van ongeveer 10× op enkele eenvoudige benchmarks. De ontwikkelingsinspanningen zijn erop gericht deze zaken onder controle te houden.
We hebben nog niet getest of stack-groei op non-tail-call paden begrensd blijft ten opzichte van het stack-gebruik van GHC. Het waarborgen van die grens is mogelijk toekomstig werk.
Ontwikkeling
De code is beschikbaar op github.com/ekmett/thc, met documentatie over hoe je THC bouwt, draait en gebruikt.
De ontwikkeling vindt plaats op irc.libera.chat in het ##thc kanaal.
Doe mee.
— Edward Kmett
Groetjes,