Tech-Talk: Truffle and Graal Implementing a JIT-Optimized AST-interpreter

Die GraalVM ist eine von Oracle entwickelte alternative zu Java Hotspot zum Ausführen von Java Programmen. Die Java Virtuelle Maschine (JVM) war schon immer ein Vorreiter wenn es um performante Virtuelle Maschinen geht. Graal begann als ein Forschungsprojekt im Bereich von Just in Time Compiler (JIT). Das Projekt hatte grossen Erfolg und die GraalVM wird unterdessen als offizielle alternative von Oracle unterstütz. Es gibt eine kostenlose Community Edition sowie eine kostenpflichtige Enterprise Edition.

Die GraalVM ist mehr als nur eine alternative JVM, sie bietet eine Vielfalt an interessanten Features. Zum einten ist sie bekannt dafür das sie Java Byte Code zu nativem Maschinencode kompilieren kann was die Startseiten von Programmen enorm erhöht, jedoch auf kosten der Spitzenausführungszeit. Dies ist vor allem für kleine Programme mit kurzer Ausführungszeit gut geeignet. Eine weitere Eigenschaft der GraalVM ist das sie Polygot ist, sprich sie kann neben Java viele anderen sprachen wie Python, Ruby, JavaScript und sogar C ausführen. Diese sprachen verwenden das Truffle Framework, welches es erlaubt einen Sprachinterpreter zu bauen, welcher dann automatisch vom hocheffizienten JIT profitieren kann. Dies wurde möglich durch eine Kompilierstrategie namens Partial Evaluation in Verbindung mit einem Konzept Namen Futamura Projection.

In diesem Techtalk wurde darauf eingegangen wie Truffle funktioniert und wie man damit eine eigene Programmiersprache entwickeln kann.

Die Theoretische Grundlage von Truffle basiert auf der sogenannten ersten Futamura Projektion, welche aussagt, das wenn man ein Interpreter auf source code spezialisiert erhält man ein ausführbares Programm für diesen source code. Dies ist die gleiche Funktion welche normalerweise ein Compiler übernimmt. Die erste Futamura Projektion verspricht somit, das man aus einem Interpreter automatisch einen Compiler ableiten kann. Obwohl diese Projektion schon lange bekannt ist waren die ausführbaren Programme welche aus diesem Prozess entstanden sehr ineffizient. Das lagt daran das die Algorithmen welche für die Spezialisierung verwendet werden suboptimal sind. Diese Algorithmen werden Specializer genannt und viel Forschung wurde bereits darin investiert.

Einer dieser Algorithmen wird Partial Evaluation genannt und wird sowohl im Graal JIT wie auch im Graal AOT Compiler verwendet. Es hat sich herausgestellt das unter bestimmten Bedingungen dieser effizienten Code erzeugen kann welcher mit herkömmlichen Techniken mithalten kann. Einer dieser anwendungsfälle ist die Verwendung als JIT Compiler zur Spezialisierung eines sogenannten selbst optimierenden Abstract Syntax Tree (AST) Interpreter auf einen konkreten AST.

Ein AST ist hierbei eine Programm Repräsentation als baum wobei die knoten Operationen oder konstante werte darstellen. Zum Beispiel kann die Berechnung 3+4*2 als ein AST dargestellt werden der als root knoten die + Operation hat welche als linkes Kind die konstante 3 hat und als rechtes Kind ein knoten mit der * Operation und den den konstanten Kinder 4 und 2. Die AST Repräsentation eines Programms ist sehr einfach zu interpretieren, da jeder Knoten einfach eine execute Methode braucht welche das Resultat berechnet. Der + knoten würde zum Beispiel execute auf seinen Kindern aufrufen und dann die Resultate zusammenzählt und das Resultat zurückgibt.

Ein selbst optimierender AST Interpreter ist eine Technik bei der während des Ausführens darauf geachtet wird was für werte von einem AST knoten produziert werden und für denn fall das nur werte mit einer spezifischen Eigenschaft angetroffen werden, so wird der AST knoten durch einen ersetzt welcher darauf spezialisiert ist diese Eigenschaft auszunutzen (er kann effizienter ausgeführt werden).

Das Truffle Framework bietet nun Annotationen und Hilfsklassen an welche verwendet werden können um so einen selbst optimierender AST Interpreter zu bauen. Die Truffle Runtime kann nun einen solchen Interpreter ausführen und verwendet Partial Evaluation über den Graal JIT um für oft gebrauchte AST’s effizienten Maschinen Code zu generieren. Der Folgende code zeigt einen Ausschnitt aus dem + node welcher sich mithilfe von Truffle selbst optimiert.

Der Code ausschnitt zeigt die Integer Addition welche beliebige ganze Zahlen addieren kann. Anstatt nun einfach einen BigInterger zu verwenden starten wir mit einem AST knoten der auf long Additionen spezialisiert ist. Für den fall das wir einen BigInteger antreffen oder die Addition zu einem Overflow führt wechseln wir zu einer representation welche auf BigInteger spezialisiert ist. Wird somit dieser + knoten immer nur mit long’s verwendet ist er sehr effizient obwohl er auch grössere zahlen handhaben kann. Der JIT kann nun diesen AST zu machinen code compilieren, welcher auf longs arbeitet und sehr effizient ist. Für den fall, dass dann unerwartet doch noch ein BigInterger gebraucht wird, wird der kompilierte code verworfen und wieder in den interpreter gewechselt, welcher nun den knoten neu spezialisiert um BigIntergers handhaben zu können (der neue AST kann durchaus später wieder kompiliert werden).

Es gibt viele use cases die von dieser Strategie profitieren können. Das Paradebeispiel sind dynamisch typisierte sprachen wo die Argument typen von Operationen erst zur Laufzeit bekannt sind. Hier können sich die Operationen auf die konkret verwendeten typen spezialisieren. Ein anderes Beispiel sind Funktionen und Methoden mit einem dynamischen Dispatch, das heisst, dass das Konkret aufzurufende Ziel erst zur Laufzeit bekannt ist, wie zum Beispiel bei virtuellen Methoden in Vererbungshierarchien oder Closures in funktionalen Programmiersprachen.

Interessierte finden im GitHub Repository die slides des Tech Talks sowie den Prototyp von nora, einer Programmiersprache die implementiert wurde um mit Truffle und Graal zu experimentieren.

Tech-Talk und Blog-Beitrag: Markus Knecht (markus.knecht@fhnw.ch) Wissenschaftlicher Mitarbeiter.