Das eierlegende Truffleschwein

Dr. Lars Hupel

Viele, die im Java-Umfeld unterwegs sind, werden von ihr gehört haben: der sagenumwobenen GraalVM. Diese magische neue Virtual Machine für Java soll vor allem für blanke Performance sorgen, indem sie den Java-Bytecode in nativen Code kompiliert. Dadurch fällt insbesondere der Startup-Overhead weg, da weite Teile der Initialisierung bereits vom Compiler erledigt werden. So oder so ähnlich ist es vielerorts zu lesen, z.B. in dem Einführungsartikel von Christopher Schmidt und Sascha Selzer. Doch das ist bei weitem nicht das einzige Feature, welches Oracle der GraalVM gegeben hat. Hinzu kommt, dass die GraalVM zu nicht weniger das Potential hat als eine neue Ära der polyglotten Programmierung auf der JVM einzuläuten. Die Rede ist von der Truffle API, einem generischen Framework zur Implementierung von Interpretern.

Die Anfänge der JVM

Als die JVM 1994 neu herauskam, war sie noch untrennbar mit Java, der Sprache, verbunden. Deutlich zu erkennen ist, dass der JVM-Bytecode so angelegt worden war, dass sich Javas Geschmacksrichtung der objektorientieren Programmierung gut darin abbilden ließ. Das ist aus historischer Sicht konsequent, denn schließlich sollte die JVM den kompilierten Java-Code effizient ausführen können.

Über die Jahre hinweg bekamen sowohl die JVM als auch Java neue Features, Optimierungen und Verbesserungen. Klar war, dass Sun Rückwärtskompatibilität als höchstes Gut auffasst. So sollen einmal kompilierte Java-Programme praktisch unbegrenzt in zukünftigen JVM-Versionen lauffähig bleiben.

Die Krönung der Rückwärtskompatibilität erfolgte dann knapp zehn Jahre später mit der Veröffentlichung von Java 5. Im Java-Compiler wurde das Typsystem durch die Einführung von Generics kräftig umgekrempelt. Doch am Bytecode änderte sich recht wenig: generische Typen werden vom Compiler kurzerhand entfernt, um Kompatibilität mit existierendem Code nicht zu gefährden. Man spricht von Type Erasure.

Anders und un-getypte Sprachen

Parallel zu diesen Entwicklungen haben kluge Köpfe an alternativen Sprachdesigns gearbeitet, die mehr oder weniger an Java angelehnt sind.

Odersky’s Scala, ungefähr zeitgleich mit Java 5 erschienen, hat das Grundkonzept der Objektorientierung beibehalten, alte Zöpfe abgeschnitten und gleichzeitig funktionale Programmierung auf der JVM salonfähig gemacht. Dank Type Erasure konnte Odersky sich im Typsystem austoben und musste nur wenig Rücksicht auf die Generics in Java 5 geben. Scalas fortgeschrittenes Typsystem spielt so in dem generierten Bytecode gar keine Rolle mehr.

Ungefähr ein Jahr zuvor war bereits die Sprache Groovy erschienen, welche ursprünglich als standardisierte Skriptsprache auf der JVM antreten wollte. Aus dem zugehörigen JSR 241 wurde jedoch nichts, so dass sich Groovy zu einer unabhängigen Programmiersprache entwickelt hat. Als Kontrast zu Java verzichtet Groovy an vielen Stellen auf Typen, so dass Methoden öfter als in Java per Reflection aufgerufen werden. Erst zur Laufzeit ist klar, in welcher Klasse die jeweilige Methode implementiert ist. Für einen Aufruf ohne Reflection müsste die konkrete Methode aber schon klar sein, wenn der Bytecode generiert wird. Also muss man den Reflection-Overhead hinnehmen.

Ist die JVM groß genug für mehrere Sprachen?

Scala und Groovy sind bei weitem nicht die einzigen Beispiele für alternative JVM-Sprachen. Manche getypt, andere eher dynamisch; aber allen ist gemeinsam, dass die JVM wegen ihrer Performance und bestehender Bibliotheken für sie eine attraktive Plattform darstellt. Auch Portierungen existierender Sprachen (Jython, JRuby) wurden in den 2000er-Jahren zunehmend populär.

2011 folgte dann Java 7, welches die lange erhoffte Bytecode-Erweiterung invokedynamic brachte. Damit lassen sich sehr effizient dynamische Methodenaufrufe implementieren, die in ungetypten Sprachen dominieren. Vorangegangen war Arbeit an der so genannten Da Vinci Virtual Machine, mit der Sun an “first-class support” für andere Sprachen auf der JVM experimentiert hat.

In Java selbst werden nicht-statische Methodenaufrufe mit den Instruktionen invokevirtual oder invokeinterface durchgeführt. Dabei sind die Argumenttypen bereits festgelegt, aber die implementierende Klasse wird zur Laufzeit ausgewählt. Im einfachsten Beispiel:

class A { int f() { /* ... */ } }
class B extends A { @Override int f() { /* ... */ }}

Je nachdem, welcher Klasse ein Objekt x angehört, wird beim Aufruf x.f() entweder A.f() oder B.f() ausgeführt.

In ungetypten Sprachen hingegen müssen regelmäßig Methoden auch nach ihren Argumenten ausgewählt werden, um z.B. zwischen Addition von Zahlen oder von Strings zu unterscheiden. Dazu dient invokedynamic, wozu die Oracle-Dokumentation folgendes erläutert:

[it] enables the runtime system to customize the linkage between a call site and a method implementation

Implementierungsaufwand

Ambitionierten Entwickler*innen, die ihrer Sprache ein JVM-Backend verpassen wollen, steht eigentlich nichts im Wege. Wäre da nicht das Problem des Compilerbaus. Oftmals werden daher Interpreter statt Compiler für Sprachen gebaut, denn dann kann man die Laufzeitinfrastruktur der Hostumgebung einfach direkt benutzen.

Im Gegensatz dazu ist es sehr schwierig, maßgeschneiderten, korrekten JVM-Bytecode zu produzieren. Die invokedynamic-Instruktion ist ein Paradebeispiel hierfür: Jeder solcher Aufruf erfordert eine Bootstrap-Methode, die den korrekten Method Handle – ebenfalls eine Neuerung in Java 7 – bereitstellt. Diese Handles lassen sich zwar viel effizienter aufrufen als die üblichen Reflection-Methods, haben aber eine komplexere API. Eine Einführung in diese API gibt es z.B. in diesem Artikel.

Doch nur mit einem “echten” Compiler kann man effektive Programmoptimierungen vornehmen. Ein Interpreter auf Basis der JVM hat zudem immer das Problem, dass man zwei Interpreter-Schichten aufeinander hat (JVM-Bytecode durch die JVM, Sprach-Quelltext durch den Sprach-Interpreter). Wenig überraschend ist das der Performance nicht sonderlich zuträglich.

Futamuras Vision

Wie wäre es also, wenn es ein System gäbe, was einen Sprachinterpreter vollautomatisch in einen Sprachcompiler transformiert? Also sozusagen einen Compiler-Compiler?

Dieses futuristisch anmutende Konzept wurde bereits 1971 von Yoshihiko Futamura beschrieben und trägt daher passenderweise den Namen Futamura Projection.

Die Futamura-Projektionen, auch unter partieller Auswertung bekannt, bezeichnen einen Bündel von Technologien, mit denen man ein gegebenes Programm für bestimmte Eingaben spezialisieren kann. Angenommen, eine Funktion erwartet zwei Eingabewerte. Der erste Eingabewert bestimmt den Programmfluss, z.B. durch eine Kaskade von if-else-Anweisungen. Eine mögliche Optimierung wäre es hier, für alle bekannten Möglichkeiten dieses Eingabewerts (z.B. wenn es sich um ein enum handelt) spezialisierte Funktionen zu generieren, die keine weiteren Bedingungen enthalten. Zu einem bestimmten Grad können das bestehende JVMs das bereits, wobei sie z.B. virtuelle Methodenaufrufe optimieren können, wenn klar ist, welche konkrete Methode angesprungen wird.

Scala hat eine ähnliche Optimierung in den Compiler eingebaut. Die Sprache erlaubt es nämlich, Generics auch mit primitiven Typen zu instanziieren, wobei der Compiler automatisch Boxing und Unboxing betreibt. Wird der Typparameter einer Methode oder Klasse mit @specialized annotiert, so werden zur Compile-Zeit Varianten erzeugt, die direkt mit nativen Typen arbeiten. Dadurch kann man sowohl Speicher- (keine Objektallokation) als auch Laufzeit-Overhead (keine Konvertierungen) einsparen.

Trotzdem sind solche Optimierungen bestenfalls punktuell. Eine vollwertige Futamura-Projektion ist hingegen allgemein und erzeugt ein sogenanntes “residual program”, sprich ein Programm, bei dem der gesamte Kontrollfluss, der bereits zur Compile-Zeit bekannt ist, ausgeneriert ist.

Man kann sich das – angewendet auf Interpreter – wie folgt vorstellen. Ein mögliches Interface für einen Interpreter kann man in etwa so definieren:

interface Interpreter {
    Object runCode(String code, Object input);
}

Dieser Interpreter führt zwei verschiedene Logiken aus:

1. Interpreter-Logik (gegeben durch die Implementierung von runCode)
2. Programm-Logik (gegeben durch den Programmtext code[1])

Die erste Futamura-Projektion verlangt, auf Basis eines gegebenen Programmtextes die runCode-Methode dergestalt zu optimieren, dass keine Interpreter-Logik mehr vorhanden ist, sondern nur noch Programm-Logik. Es gibt noch zwei weitere Projektionen, die aber für diesen Artikel nicht relevant sind.

Viele Jahrzehnte nach der erstmaligen Beschreibung dieses Konzepts ist Oracle mit GraalVM gelungen, eine produktionsreife Implementierung der ersten Futamura-Projektion vorzulegen: man schreibe einen Interpreter – zum Beispiel für JavaScript (JS) – in Java und erhält automatisch einen JIT-optimierenden Compiler, der die bisherigen spezialisierten Interpreter Rhino und Nashorn schlägt.

Bleiben wir doch bei JS als Beispiel einer Sprache, die mittlerweile universell eingesetzt wird und für die es gute Gründe gibt, sie in die JVM einbetten zu wollen. Mit Hilfe der Truffle API, die mit GraalVM ausgeliefert wird, lässt sich z.B. Multiplikation in JavaScript wie folgt implementieren (stark eingekürzt):

public abstract class JSMultiplyNode extends JSBinaryNode {

    public abstract Object execute(Object a, Object b);

    @Specialization(guards = "b > 0", rewriteOn = ArithmeticException.class)
    protected int doIntBLargerZero(int a, int b) {
        return Math.multiplyExact(a, b);
    }

    @Specialization(rewriteOn = ArithmeticException.class)
    protected int doInt(int a, int b) {
        // ...
    }

    @Specialization
    protected double doDouble(double a, double b) {
        return a * b;
    }

    // ...
}

Durch einfache Annotationen wie @Specialization wird Truffle signalisiert, welche Methoden für spezielle Objekttypen aufgerufen werden soll. Im Allgemeinen kann in JavaScript erstmal alles mit jedem multipliziert werden, aber für die Fälle int,int und double,double werden hier effiziente Implementierungen vorgegeben.

Dank der Truffle API kann man systematisch einen Interpreter implementieren, der von der GraalVM automatisch als JIT-Compiler benutzt wird. Performanceoptimierungen wie oben annotiert werden dabei automatisch berücksichtigt.

GraalVM vs. JVM

An dieser Stelle sollten wir einmal genau unter die Lupe nehmen, wie Truffle in Beziehung zum Ökosystem steht. Dazu müssen wir einige Begrifflichkeiten klären.

Unter der GraalVM versteht man sowohl das gesamte Projekt unter Federführung von Oracle als auch eine (derzeit) Java-8-kompatible Implementierung einer Java Virtual Machine. Damit reiht sich die GraalVM in eine Reihe anderer Implementierungen ein, z.B. Azul, und existiert neben HotSpot, der am weitesten verbreiteten JVM von Oracle, die mit dem OpenJDK ausgeliefert wird.

Code, der auf der GraalVM läuft, wird weiterhin wie üblich als Bytecode interpretiert. Für die Umwandlung in nativen Code ist ein sogenannter Ahead Of Time (AOT) Compiler zuständig. Gegensätzlich zum bekannten Just In Time (JIT) Compiler wird Bytecode damit bereits vor der Ausführung in Maschinencode übersetzt. Der AOT-Compiler der GraalVM erzeugt ein Native Image, welches eine minimale Laufzeitinfrastruktur beinhaltet (SubstrateVM). AOT-Kompilierung wird ebenfalls in der Android Runtime (ART) benutzt.

Die Implementierung von alternativen Sprachen wie z.B. JavaScript erfolgt mit dem Truffle Framework, was sowohl auf der GraalVM als auch der SubstrateVM lauffähig ist. Darüber hinaus können manche mit Truffle implementierten Sprachen (aber nicht alle) auch auf der HotSpot-VM (oder anderen JVMs) ausgeführt werden, wobei in diesem Fall die Performance niedriger ist.

Die nahtlose Einbettung solcher Sprachen in Java-Programme erfolgt mittels der Polyglot API, die über Sprachen abstrahiert und den Austausch von Objekten ermöglicht. Wie im oberen Codeschnipsel zu sehen ist, werden intern die gewohnten Java-Typen verwendet. Umgekehrt kann man auch sehr einfach aus JS-Code Java-Code aufzurufen. Trotzdem erlaubt es die GraalVM, den Guest-Code isoliert laufen zu lassen (separater Heap und Garbage Collection) und die Menge der zulässigen Operationen feinziseliert festzulegen.

Eine neue Ära?

JavaScript ist derzeit eine der am besten unterstützten Sprachen in der GraalVM. Für diejenigen, die sich aber weniger für die coole Technologie im Hintergrund interessieren, sondern sich fragen, welche konkreten Vorteile die GraalVM in der Praxis bringt, haben die Entwickler*innen von Oracle vorgesorgt.

Zum einen bringt die GraalVM-Distribution eine komplette Node.js-Umgebung mit, die auch das Kommandozeilentool node beinhaltet. Das bedeutet, dass sich die allermeisten üblichen npm-Pakete auch nahtlos in einer Java-Umgebung ausführen lassen. Damit hat GraalVM einen haushohen Vorteil sowohl gegenüber Rhino als auch Nashorn, die viele neuere Sprachkonstrukte aus den Revisionen ES6 und später nicht unterstützen.

Zum anderen lässt sich eine polyglotte Anwendung nahtlos in nativen Code übersetzen. Damit hat Oracle einen hohen Grad an Orthogonalität ihrer Features erreicht.

Damit wird heute schon Realität, wovon man früher nur träumen konnte: gemischte JS/JVM-Projekte können mit wenig Aufwand gebaut und effizient ausgeführt werden. Nutzt man z.B. Gradle als Build-Tool, so gibt es dafür ein Node.js-Plugin, mit dem sich npm-Pakete installieren und bauen lassen. Die so paketierten JS-Files lassen sich dann direkt in die JVM laden und ausführen.

Neben JavaScript gibt es aber noch andere unterstützte Sprachen:

• Sofern man an statistischen Berechnungen interessiert ist, bindet man kurzerhand R ein.
• Dank Python-3-Support lässt sich im Gegensatz zu Jython moderner Python-Code ausführen.
• Ruby-Applikationen können parallelisiert werden, da die Einschränkung durch den Global Interpreter Lock (GIL) wegfällt.

Auch für Menschen, die von Java nichts halten, könnte ein Blick auf die GraalVM lohnen: selbstverständlich lässt sich die Polyglot-API auch aus JavaScript, Ruby oder Python heraus nutzen, weshalb man auch diese Sprachen miteinander mischen kann. Faszinierenderweise implementiert GraalVM das Chrome Devtools Protocol, womit sich normalerweise JavaScript im Browser debuggen lässt, dank Polyglot-API aber auch andere Sprachen. Damit lassen sich in Chrome Breakpoints z.B. in Ruby-Code, der einen JavaScript-Webserver startet, setzen.

Die Truffle API ist aber auch ausgezeichnet dafür geeignet, domänenspezifische Sprachen zu designen. Wie das geht, wird in einem Beispiel-Repository demonstriert.

Nativer Code? In meiner JVM?

Die oben genannten Sprachen werden gewöhnlich immer in einer VM beziehungsweise einem Interpreter ausgeführt. Daher ist es nicht so überraschend, dass man sie auch auf einer JVM implementieren kann. GraalVM kann allerdings auch LLVM Bitcode – eine Art Assemblersprache – ausführen. Dadurch kann man performance- oder speicherkritischen Code in systemnahen Sprachen wir Rust zu implementieren und Seite an Seite mit Java-Code laufen lassen.

Es lohnt sich, diese Interoperabilität genauer unter die Lupe zu nehmen. Wenn man bisher nativen Code in der JVM laufen lassen wollte, hatte man im Wesentlichen zwei Optionen:

1. Java Native Interface (JNI), offizieller Bestandteil der Java-Spezifikation
2. Java Native Access (JNA), als Community-Bibliothek bereitgestellt

Unterschiede der beiden Ansätze zeigen sich z.B. daran, dass es in JNA nicht vorgesehen ist, Java-Objekte direkt aus C/C++ zu manipulieren oder Methoden aufzurufen. Im Gegensatz dazu braucht nativer Code für die Benutzung in JNA nicht mit speziellen Headerfiles kompiliert werden. Daneben gibt es noch zahlreiche andere Unterschiede, z.B. in der Performance.

Beiden Ansätzen ist allerdings gemein, dass Java-Code, der nativen Code aufrufen möchte, eine plattformspezifische native Bibliothek geladen werden muss. Eine solche muss im Regelfall binärkompatibel zu C sein. Wenn es sich dabei nicht um die Standard-C-Bibliothek handelt, sind entweder User dafür verantwortlich, diese nachzuinstallieren oder die Java-Bibliothek dafür, diese mitzuliefern. Im schlimmsten Fall müssen dabei Varianten für Windows, Linux, macOS, BSD und weitere berücksichtigt werden. Ferner führen Crashes in nativem Code automatisch zum Crash der gesamten JVM.

GraalVM verbessert diese Situation deutlich. Statt nativem Code direkt einzubinden, geht man den Umweg über den sogenannten Bitcode des LLVM-Projekts. Ähnlich wie GraalVM ist LLVM ein Infrastrukturprojekt, was unter anderem vom Apple und Google vorangetrieben wird. Unter dessem Dach wird ein moderner C/C++-Compiler entwickelt (clang), sowie ein generisches, optimierendes Backend, welches andere Compiler zur Codegenerierung benutzen können. Das Rust-Projekt nutzt LLVM zu diesem Zweck. In gewisser Weise kann man sich also LLVM-Bitcode als Konkurrenten zu JVM-Bytecode vorstellen. Im Gegensatz zu JVM-Bytecode wird LLVM-Bitcode aber im Regelfall vor der Ausführung in nativen Code transformiert (AOT). GraalVM hingegen kann den Bitcode ausführen und damit in die Polyglot-Infrastruktur einbinden.

Darüber hinaus bietet die Enterprise Edition von GraalVM auch einen Sandbox-Modus für C-Programme. In diesem Modus werden sämtliche Speicherzugriffe und Systemaufrufe umgebogen, so dass dieselben Zugriffsbeschränkungen wie z.B. bei JavaScript konfiguriert werden können. Insbesondere reißen Crashes nicht die ganze Applikation mit sich, sondern äußern sich in einer Exception. Beispiel gefällig? Betrachten wir folgenden C-Code (adaptiert von einem Blog-Eintrag des Graal-Teams):

#include <stdio.h>

int main(int argc, char *argv[]) {
    printf("number of arguments: %n\n", argc);
    return 0;
}

Der Fehler ist, dass der Format-Modifier %n die Zahl der bisher geschriebenen Bytes in das Argument speichert, aber argc kein Zeiger ist. Gängige Compiler warnen zwar vor diesem Problem, kompilieren das Programm aber trotzdem.

Mit folgendem Java-Code kann man den Bitcode laden und ausführen:

class Sandbox {
    public static void main(String[] args) throws IOException {
        Source source =
            Source.newBuilder("llvm", new File("bug.bc")).build();

        Context.Builder builder =
            Context.newBuilder()
                .allowIO(true)
                .option("llvm.sandboxed", "true");
        try (Context polyglot = builder.build()) {
            polyglot.eval(source).execute();
        }
        catch (Exception ex) {
            System.out.println("something went wrong: " + ex);
        }
    }
}

Zur Laufzeit erhält man diese Exception:

number of arguments: something went wrong: org.graalvm.polyglot.PolyglotException: Illegal pointer access: 0x0000000000000001

Normalerweise würde das reine C-Programm aber abbrechen.

Rusten statt rosten

Dank der Sandbox lassen sich auch fehlerhafte C-Programme sicher ausführen. Wer aber die Enterprise Edition nicht nutzen kann oder möchte, muss stattdessen auf eine sichere Programmiersprache zurückgreifen. Dafür bietet sich Rust an, da der Compiler ebenfalls LLVM-Bitcode erzeugen kann.

Die Herausforderung dabei ist, eine robuste Integration zwischen der objektorientierten Java-Welt und der eher systemnahen Rust-Welt zu schaffen. Diese Integration basiert darauf, dass einerseits Java- und Rust-Funktionen sich gegenseitig aufrufen und Objekte austauschen können.

Um das zu verstehen, ist die Struktur des LLVM-Bitcodes wichtig. Diese ähnelt nämlich der Stuktur des JVM-Bytecodes: es wird eine Reihe von Funktionen (optional mit Parametern und Rückgabewert) definiert. Die Funktionskörper bestehen dann aus einer Reihe von Instruktionen, z.B. arithmetische Routinen oder Aufrufe von anderen Funktionen. LLVM verlangt (genau wie die JVM), dass der Bitcode typkorrekt ist.

Eine weitere Gemeinsamkeit ist es, dass der Bitcode unvollständig sein kann. Das bedeutet: manche Funktionen werden nur deklariert, d.h. sie müssen an einer anderen Stelle definiert sein, damit ein Aufruf erfolgreich ist. In Java ist das der Fall, wenn eine Methode einer anderen Klasse aufgerufen wird. Die JVM lädt Klassen lazily, d.h. wenn ein Aufruf erfolgt, wird im Classpath nach der passenden Klasse gesucht.

Bei LLVM bzw. nativem Code ist das etwas komplizierter. Normalerweise müsste man sich auf das dynamische Linken des Betriebssystems verlassen. Im Kontext von Graal ist das nicht möglich, da die JVM nicht beliebige Bibliotheken nachladen kann.[2] Stattdessen muss man durch geeignete Compiler-Flags dem Rust-Compiler anweisen, statisch gelinkte Bitcode-Dateien zu erzeugen. Das funktioniert aber nur soweit, wie alle benutzen Abhängikeiten selbst wiederum in Rust implementiert sind und daher auch als LLVM-Bitcode vorliegen. Systemnaher Code ruft aber eben auch manchmal Routinen des Betriebssystems auf. GraalVM kann solche Calls durchführen, indem es sie 1:1 weiterreicht. Die Enterprise Edition kann im Sandboxing-Modus eine bestimmte Liste von Calls auch abfangen und umleiten.

Ruft nun Java-Code eine Funktion aus Rust auf, wird diese im geladenen Bitcode per Namen gesucht, denn Überladung ist in Rust nicht möglich. Der umgekehrte Weg ist nicht so einfach. Zunächst bietet die Installation der GraalVM eine C-Header-Datei an, in der bestimmte Funktionen deklariert sind, mit denen sich Java-Klassen laden, instanziieren und deren Methoden selektieren und aufrufen lassen. Diese C-Funktionen werden in der GraalVM implementiert und liegen daher nicht im Bitcode vor. Während der Ausführung von Rust-Code werden sie in entsprechende Java-Reflection-Aufrufe umgewandelt. Bekannte Typen wie Integer werden automatisch konvertiert.

Typischer Code, mit dem sich Java-Objekte erzeugen und manipulieren lassen, sieht so aus:

unsafe {
    let buf = polyglot_new_instance(polyglot_java_type("java.lang.StringBuffer\0"));
    let value = polyglot_from_string_n(str, str.len(), "UTF-8\0".as_ptr());
    polyglot_invoke(buf, "append\0".as_ptr(), value);
    // ...
}

Bei aller Interoperabilität bleibt eine Einschränkung: Es ist nicht möglich, Zeiger auf Java-Objekte außerhalb des lokalen Stacks einer Rust-Funktion zu verwalten. Insbesondere kann man sie nicht in komplexere Datenstrukturen verpacken. Das liegt daran, dass diese Zeiger von GraalVM sich nicht wie gewöhnliche Zeiger verhalten; daher sind Arrays auch nur schwer und Zeigerarithmetik sogar unmöglich abzubilden.