JEXP
JEXPNormalerweise sind wir mit der Performance von Java ganz zufrieden. Der Bytecode-Compiler und die Hotspot VM mit Laufzeit-Compilierung (JIT) leisten recht gute Arbeit. Solange man auf Datenstrukturen und vernünfigte Interaktion (Mechanical Sympathy) mit CPU / Caches und Hauptspeicher sowie dem Garbage Collector achtet kann man sogar bis zu 70% der theoretischen Prozessorleistung mit Java erreichen, was mich immer wieder verblüfft.
Etwas anders sieht es aus, wenn wir dynamische Sprachen anschauen. Seien das Programmiersprachen wie jRuby, Groovy, Clojure oder Javascript, die zwar mit InvokeDynamic und MethodHandles einen Bonus bekommen haben, aber trotzdem noch nicht so schnell sind wie Java. Aber auch Domänenspezifische Sprachen (DSL), wie Funktionen für Rule-Engines, Abfragesprachen, Routing-Definitionen oder Template-Sprachen würden davon profitieren, nicht interpretiert, sondern compiliert zu werden.
Bisher wurde für Bytecoderzeugung zur Laufzeit meist ein Toolkit wie ASM oder CGlib benutzt. Damit können vorhandene Typen erweitert oder Bytecode für neue Klassen erschaffen werden. Ein anderer Ansatz, den die Auslieferung der Compiler-Tools mit der JRE ermöglicht, ist die Generierung von Java-Quellcode, der dann on-the-fly compiliert und geladen werden kann. Aber diese beiden Lösungen sind nur statische Ansätze, die den Laufzeitkontext der Ausführung des Codes nicht berücksichtigt. Bei dynamischen Sprachen, hat man zum Teil vor der konkreten Ausführung noch nicht alle Informationen z.b. Typen von Parametern oder Datenstrukturen die verarbeitet werden oder die konkrete Operation, die angewandt wird (Metaprogrammierung). Und natürlich möchte man diese Ausführung auch so weit wie möglich optimieren, um nah an die Ausführungsgeschwindigkeit von statisch compiliertem Code zu kommen.
Von einer Gruppe von Ingenieuren bei Oracle Labs und diversen Universitäten wird seit einigen Jahren eine Infrastruktur entwickelt die es ermöglicht dynamischen Code während der kontinuierlich zu optimieren und dynamische zu compilieren - das Gespann aus dem Truffle-AST-Framework und dem Graal Compiler, die aus der Arbeit mit der Maxine VM (einer in Java implementierten JVM) entstanden sind.
Graal unterliegt der GPLv2 Lizenz und die Truffle API der GPLv2 mit Classpath Exception. Der Quellcode der Projekte ist für wissenschaftliche Arbeiten für nichtkommerzielle Nutzung verfügbar. Es gibt eine Menge von Informationen zu diesem Projekt, sowohl von Oracle als auch als Teil des OpenJDK - Hotspot Projektes auf [Graal Projekt]
Der JIT Compiler der JVM tritt nach der Warmup-Phase (-XX:CompileThreshold=10000) einer Methode in Erscheinung, indem die bisher gesammelten Informationen über statische Code-Struktur, aber auch Laufzeitinformationen über wiederholt genutzte Codepfade, geladene Subklassen und Spezialisierungen (Generics) berücksichtigt werden, um optimaleren Laufzeitcode zu erzeugen.
Falls globale oder lokale Annahmen (Assumptions) nicht mehr zutreffen, wird wieder deoptimiert, d.h. bisher eingefügte Code-Pfade werden wieder entfernt.
Ein gutes Beispiel dafür ist das effiziente Inlining (Aufruf wird durch Methodencode ersetzt) von Methoden, das bis zu einer Größe von 35 Bytecode-Instruktionen geschieht (-XX:MaxInlineSize=35).
Diese Operation kann natürlich nur erfolgen, wenn keine polymorphen Subklassen die Methode überschreiben.
Falls neben der ersten, noch weitere Subklassen geladen werden, stellt eine Fallunterscheidung für 2 Fälle, die erste Deoptimierung dar.
Wenn noch mehr Subklassen geladen werden, die die Methode überschreiben, dann bleibt nur die Option des vollständigen Rückgängigmachens des Inlinings die Option.
Ähnliche Optimierungen gibt es noch für viele andere Fälle: Aufrollen von Schleifen, Escape-Analyse von Variablen und Locks, On Stack Replacement usw.
Einen anderen Ansatz verfolgen dynamische Compiler wie Graal, dort wird nicht nur auf dem Bytecode-Level optimiert, sondern auf den Knoten des Abstrakten Syntaxbaums (AST).
Nach dem Parsen eines Programms liegt dieses in einem Abstrakten Syntaxbaum (AST) vor. Dieser Baum besteht aus vielen Knoten von denen jeder eine strukturelle Einheit auf einem bestimmten Level beschreibt, z.B. Klasse → Methode → Block → Statement → Ausdruck. Die Kindknoten stellen die Bestandteile dieser Einheit auf dem nächstniedrigen Level dar.
Normalerweise arbeiten nur Parser, Interpreter, Checker oder statische Compiler auf dem AST, nicht dynamische Laufzeitcompiler. Graal nutzt den Ansatz des Truffle Interpreter Framework, für den jeweiligen AST Knotens die Interpreter-Operation auszuimplementieren. Dabei können neben der generischen Variante, typ- und kontextabhängig massiv optimierte Spezialisierungen bereitgestellt werden. Diese ermöglichen eine sehr effiziente Kompilierung, soweit wie möglich direkt auf die entsprechenden CPU-Operationen.
In der Umgebung der experimentellen, minimalen und effizienten Substrate VM erfolgt die Kompilierung mittels Graal direkt zu Maschinencode, so dass kein Java- und JVM Start- und Laufzeitoverhead entsteht.
Wenn Graal in Verbindung mit Hotspot eingsetzt wird, dann erfolgt die Kompilierung nach Bytecode, der dann vom Just in Time Compiler weiter optimiert werden kann.
In Graal und Truffle wurde Wert auf eine saubere Architektur mit Trennung der Verantwortlichkeiten der verschiedenen, feingranularen Module gelegt. Einen prinzipiellen Überblick gibt die folgende Abbildung.
Zur Zeit liegt der Fokus auf dynamischen Programmiersprachen, wie Javascript, Ruby, Clojure, Groovy und R aber es sind viele weitere Anwendungen angedacht. Je nach Laufzeitumgebung des Hostsystems sind verschiedenste Optimierungen des Compilers möglich. Diese sollten aber nicht durch #defines oder bedingte Verzweigungen sondern durch dedizierte Module pro Runtime realisiert werden.
Create an extensible, modular, dynamic, and aggressive compiler using object-oriented and reflective Java programming, a graph-based and visualizable intermediate representation, and Java snippets.
Graal ist ein in Java geschriebener, optimierender JIT Compiler im OpenJDK, der der Laufzeitumgebung JIT-APIs zur Verfügung stellt. Damit können Anwendungen den Compiler direkt steuern. In unserem Fall übernimmt Truffle diesen etwas komplexen Vorgang.
Für eine minimale Beispielsprache (SL, SimpleLanguage), die dynamische Typdefinitionen, einfache Operationen, ganze Zahlen beliebiger Länge, Strings und Booleans unterstützt, soll am Beispiel der Addition gezeigt werden, wie diese in Truffle abgebildet werden kann.
Welche Ansätze gibt es im allgemeinen, um Interpreter-Code für diese Operation zu schreiben?
Typchecks innerhalb einer Entscheidugnskette mit jeweiligen typspezifischen Blöcken
Problem: teure Operationen (BigInteger.add, toString()), aufwändiger Kontrollfluss für jeden Durchlauf
class AddNode extends TypedNode {
TypedNode left, right;
Object execute(Frame frame) {
Object l = left.execute(frame); Object r = right.execute(frame);
if (l instanceof BigInteger && r instanceof BigInteger) return ((BigInteger) l).add((BigInteger) r);
if (l instanceof String || r instanceof String) return left.toString() + right.toString();
throw new RuntimeException("type error");
}
}Typcheck auch für Integer, Double usw. mit Math.addExact()
Problem: Boxing primitiver Werte, zuviele Typüberprüfungen
Spezialisierte AST-Knoten, die genau einen Fall abhandeln oder generisch sind
Problem: Was passiert, wenn die aktuellen Parameter nicht den Erwartungen entsprechen, was passiert bei Überläufen?
Ersetzen des aktuellen Knotens durch den korrekten Knoten (spezialisierter oder generischer) im Fall des Typfehlers
Problem: Sehr viel Zusatzcode für die ganzen Checks und Ersetzungen
Nutzung von Annotationen für die Definition der Spezialfälle, der Zusatzcode wird transparent aus den Annotationen generiert. Das ist der Ansatz den Truffle gewählt hat.
Truffle ist ein Framework (API und Hilfsklassen), um AST Interpreter in Java zu schreiben. Um es zu nutzen, müssen neben den Knoten des Syntaxbaumes der Sprache auch noch zusätzliche Interpreter-Methoden implementiert werden, die die Realisierung der jeweiligen Operation darstellen.
Anders als andere Interpreter unterstützt Truffle das Konzept der Spezialisierung. Abhängig vom Laufzeitzustand, Typinformationen und Werten aktueller Parameter kann der Knoten durch optimierte Spezialisierungen der Operation ersetzt werden. Wenn sich dieser Kontext ändert, wird der AST-Knoten gegen eine andere Spezialisierung ausgetauscht oder zurück zur unspezialisierten Variante gewechselt. Basierend auf einer AST-Superklasse, sowie weiteren Hilfsklassen, wird das Ersetzen der Knoten vorgenommen, sowie die Ausführung kontrolliert. Das betrifft vor allem den Wechsel in den Interpretermodus und die Überpüfung von lokalen Bedingungen sowie globalen Annahmen.
Hier ist noch einmal das Beispiel der Addition, umgesetzt mit den APIs des Truffle Frameworks:
public abstract class Node implements Cloneable { private Node parent;
protected final Node updateParent(Node newChild) { ... }
public final Node replace(Node newNode) { ... }
public final Iterable<Node> getChildren() { ... }
public Node copy() { ... }
}public abstract class TypedNode extends Node {
// abstract methods
boolean executeBoolean(Frame frame) throws UnexpectedResultException;
int executeInteger(Frame frame) throws UnexpectedResultException;
BigInteger executeBigInteger(Frame frame) throws UnexpectedResultException;
String executeString(Frame frame) throws UnexpectedResultException;
Object executeGeneric(Frame frame);
}@TypeSystem(types = {int.class, BigInteger.class, boolean.class, String.class, Object.class}, nodeBaseClass = TypedNode.class)
abstract class SLTypes {
public boolean isString(Object l, Object r) {
return l instanceof String || r instanceof String;
}
}@Operation(typeSystem = SLTypes.class, values = {"left", "right"})
public final class AddOp {
@SpecializationThrows(javaClass = ArithmeticException.class,
transitionTo = "doBigInteger") (2)
@Specialization public static int doInteger(int l, int r)
{ return Math.addExact(l, r); } (1)
@Specialization public static BigInteger doBigInteger(BigInteger l, BigInteger r)
{ return l.add(r); }
@SpecializationGuard(methodName = "isString", dynamic = true) (3)
@Specialization public static String doString(Object l, Object r)
{ return l.toString() + r.toString(); }
@Generic public static Object doGeneric(Object l, Object r)
{ throw new RuntimeException("type error"); } (4)
}@Specialization annotiert eine spezialisierte Operation.
Beim Überlauf der Addition Ausführung durch die doBigInteger Operation.
Typ-Annahme, wenn String, dann soll doString benutzt werden.
Wenn keine der Spezialisierungen zutrifft, dann wird die generische Implementierung genutzt.
Ansatz: Typüberprüfung und Boxing primitiver Werte ist zu teuer, stattdessen wird der aktuelle AST-Knoten durch einen spezialisierten ersetzt, der nur die primitive Operation vornimmt. Der Graal Compiler nimmt eine automatische, teilweise Auswertung/Umschreibung vor, um mit sovielen Vorbedingungen wie möglich, effizient compilierbaren Code in den Hotspots der Ausführung z.b. in Schleifenkörpern zu erzeugen.
Erst zusammen mit dem Graal Compiler kann Truffle seine Vorteile ausspielen, da dieser die spezialisierten Knoten optimal zu Maschinencode compilieren kann. Die Typüberprüfungen, Vorbedingungen, globalen Annahmen usw. sind kein Teil des Compilats sondern werden ausserhalb gehandhabt. Falls eine dieser Änderungen triggert, die eine alternative Spezialisierung oder Generalisierung zur Folge hätte (was in der Realität nur sehr selten auftritt), wird kurzerhand in den Interpreter-Modus zurückgewechselt. Von dort aus wird dann entweder zu einer alternativen optimierte Variante gewechselt, oder für generische Fälle interpretiert.
Wenn nach einigen Ausführungen sich die Ausprägung und Anordnung der AST-Spezialisierungen stabilisiert hat, tritt der dynamische Compiler auf den Plan und konvertiert die spezialisierten Operationen in optimalen Maschinencode. Dabei werden alle Methodenaufrufe geinlined, Konstanten werden aufgelöst und Variablennutzung optimiert.
Der Code für Entscheidungen und Überprüfungen bleibt aussen vor, so dass dieser die Effizienz der Kernoperationen nicht beeinflusst. Sie lösen stattdessen bei entsprechenden Änderungen einen Wechsel in den Interpreter-Modus aus und ermöglichen dann eine erneute Anpassung an die geänderten Verhältnisse.
Auf einer normalen JVM läuft Truffle nur im Interpretermodus, also ziemlich langsam. Diesen Modus kann man aber gut dazu nutzen, die AST-Implementierungen der eigenen Sprache zu entwickeln, testen und debuggen. Truffle Code ist ganz normaler Java-Code, man muss sich nicht mit Bytecodegenerierung, Classloading, JIT oder anderen Compilertechniken auseinandersetzen. Das übernimmt die Truffle-Graal Kombination im Hintergrund.
Auf der Graal-VM dagegen wird die JIT-API von Graal exponiert und Truffle stellt dem JIT die in eine einzige Methode / Objekt kombinierte Gesamtheit der spezialisierten Interpreter-Methoden zur Verfügung die dann von Graal dynamisch compiliert wird. Über die bereitgestellten JIT-APIs kann auch die Deoptimierung / Rückkehr in den Interpretermodus gesteuert werden.
Mit der Substrate VM kann ein minimales Bundle aus effizienter Laufzeitumgebung und optimalem Maschinencode geschnürt werden. Dabei wird der Original-Java-Code von Truffle und Graal, des Sprach-Parsers und der AST-Knoten Implementierungen einer aggressiven statischen Analyse unterzogen, die allen nicht erreichbaren Code (Klassen, Methoden, Variablen) entfernt.
Der verbleibende Bytecode wird effizient nach Maschinencode für das Zielsystem und die Substrate-VM übersetzt, dabei wird sogar schon in entsprechenden Datensegmenten Platz für statisch initialisierte Objekte und Konstanten mit bereitgestellt.
Dieser Ansatz wurde auch genutzt, um eine beeindruckend schnelle Ruby-Implementierung zu entwickeln.
Ein Team um Chris Seaton hat für die dynamische Sprache Ruby eine Truffle Implementierung umgesetzt. [jRuby Truffle] Dieses Projekt unterstützt alle dynamischen und exotischen Sprachfeatures wie Metaprogrammierung und feingranulare Methodenkomposition. Bei realistischen, rechenintensiven Benchmarks (Bildverarbeitung, ohne massive I/O Anteile) zeigte sich eine beeindruckende Leistungssteigerung im Vergleich mit anderen Ruby und JRuby-Implmementationen. Besonders in den dynamischen Szenarien mit hoher Variabilität zeigen sich die Vorteile der dynamischen Compilierung mit Truffle und Graal. Viele der existierenden Ruby-VMs inlinen Code nicht aggressiv genug, so dass mögliche Grenzen der Leistungsfähigkeit nicht erreicht werden.
Wenn man einen Ruby-Parser mit Truffle, der Ruby-Implementierung, Graal und der sparsamen Substrate VM zusammen paketiert, erhält man eine hochperformante, standalone Ruby-VM.
In den mittels Truffle umgesetzten Implementierungen für dynamische Sprachen wie JRuby, Javascript und R zeigt sich die Sinnhaftigkeit der dynamischen Kompilierung. In allen Fällen ist eine deutliche Leistungssteigerung zu verzeichnen.
Sogar im Vergleich mit C-Compilern schneiden Truffle & Graal nicht schlecht ab. In vielen Fällen wird fast die Leistung der besten C-Compiler-Optimierungs Leistung erreicht.
TODO Fr. Weinert Diagramme???
Es gibt eine Menge von Projekten und eine aktive Community rund um Truffle und Graal. Von Forschungsprojekten bei Oracle und an diversen Universitäten von Arbeiten an der virtuellen Maschine über den Compiler und Interpreter bis zu Implementierungen für eine Reihe von (dynamischen) Sprachen (JRuby, Javascript, C, FastR, ZipPy, Groovy, GPU).
Bei Neo Technology wollten wir testen, welche Auswirkung der Ansatz der dynamischen Kompilierung für unsere Abfragesprache Cypher hat. Zur Zeit ist diese in Scala (Parser + Plan-Builder + Interpreter-Runtime) geschrieben. Bei ersten Experimenten mit einer minimalen Runtime haben wir einen Performancezuwachs um den Faktor 5-7 gesehen. Das ist natürlich nicht repräsentativ.
Die Abbildungen wurden aus den Präsentationen des Graal/Truffle Teams, die als Referenzen gelistet sind entnommen.