Just-in-time-Kompilierung
Just-in-time-Kompilierung (JIT-Kompilierung) ist ein Verfahren aus der praktischen Informatik, um (Teil-)Programme zur Laufzeit in Maschinencode zu übersetzen. Ziel ist es dabei, die Ausführungsgeschwindigkeit gegenüber einem Interpreter zu steigern. JIT-Compiler kommen meist im Rahmen einer virtuellen Maschine zum Einsatz, wo Plattform-unabhängiger Bytecode ausgeführt werden soll.
Just in time bedeutet in diesem Kontext „termingerecht“, „bei Bedarf“ (analog zur Just-in-time-Produktion).
Motivation
Software wird heutzutage in einer Vielzahl unterschiedlicher Programmiersprachen geschrieben. Viele dieser Programmiersprachen werden typischerweise nicht vor ihrer Ausführung zu Maschinencode kompiliert, sondern stattdessen durch eine virtuelle Maschine (VM) ausgeführt. Gründe dafür sind beispielsweise Plattformunabhängigkeit oder die dynamische Natur der Programmiersprache. Einige Beispiele für solche Programmiersprachen sind JavaScript und Python.
Die Ausführungsgeschwindigkeit der VM ist im Vergleich zu nativ kompilierten Programmen, die aus direkt durch den Prozessor ausführbaren Instruktionen bestehen, potentiell geringer. Durch Just-in-time-Kompilierung versucht man, diesen Nachteil auszugleichen.
Es ist allerdings auch möglich, den Maschinencode kompilierter Programme zur Laufzeit zu modifizieren oder auch zu optimieren, was ebenfalls eine Form von Just-in-time-Kompilierung ist.[1]
Abgrenzung zur Ahead-of-time-Kompilierung
Ein Just-in-time-Compiler unterscheidet sich von Ahead-of-time-Compilern (AOT) durch den Zeitpunkt, zu welchem die Übersetzung durchgeführt wird:
- Ahead-of-time-Compiler übersetzen das gesamte Programm vor seiner Ausführung: Der Programmierer übersetzt das Programm mittels des AOT-Compilers in das fertige, direkt ausführbare Kompilat. Anschließend wird es weitergegeben (an den Benutzer).
- JIT-Compiler übersetzen hingegen erst während der Laufzeit, mitunter auch nur Programmteile.
Außerdem haben AOT-Compiler und JIT-Compiler typischerweise verschiedene Optimierungsmöglichkeiten.
Einige Sprachen wie z. B. C, C++ oder Fortran eignen sich besonders für die Ahead-of-time-Kompilierung (z. B. aufgrund statischer Typisierung), während sich andere, dynamischere Sprachen wie Python oder JavaScript nur schwer „ahead-of-time“ zu effizientem Maschinencode kompilieren lassen. Für solche Sprachen eignet sich daher ein JIT-Compiler, da er zur Laufzeit Informationen über das ausgeführte Programm sammeln und nutzen kann.
Funktionsweise
Die generelle Funktionsweise eines JIT-Compilers ist es, zur Laufzeit des Programms lauffähigen Maschinencode zu erzeugen. Da die Kompilierung während der Ausführung des Programms durchgeführt wird, kann sie nicht beliebig aufwendig sein, da dies sonst die Ausführungsgeschwindigkeit des eigentlichen Programms merklich beeinträchtigen könnte. Daher beschränkt man sich meist auf häufig ausgeführte Programmteile. Diese sind typischerweise für den Großteil der Ausführungszeit des Programms verantwortlich, weshalb sich deren Kompilation und Optimierung besonders lohnt. Die Aufgabe des JIT-Compilers ist es, diese Programmteile zu identifizieren, zu optimieren und anschließend in Maschinencode zu übersetzen, welcher vom Prozessor direkt ausgeführt werden kann. Der erzeugte Code wird meist zwischengespeichert, um ihn zu einem späteren Zeitpunkt der Programmausführung wiederverwenden zu können.
Für die Implementierung eines JIT-Compilers bieten sich zwei gängige Verfahren an:
Methoden-JITs
Ein Methoden-JIT übersetzt komplette Funktionen bzw. Methoden des Programms zur Laufzeit. Man nutzt hierbei die Information über den Aufrufkontext der Funktionen bzw. Methoden aus, z. B. ist zur Laufzeit bekannt, welche Typen die übergebenen Parameter haben.
Tracing-JITs
Tracing-JITs basieren auf der Annahme, dass Programme den Großteil ihrer Zeit in Schleifen verbringen. Daher versucht ein Tracing-JIT, häufig ausgeführte Pfade in Schleifen zu identifizieren. Die Folge der Operationen, aus denen sich diese Ausführungspfade zusammensetzen, werden auch Traces genannt. Nach ihrer Identifikation werden Traces typischerweise noch optimiert und anschließend in Maschinencode übersetzt.
Optimierungsmöglichkeiten
JIT-Compiler haben, ähnlich wie AOT-Compiler, die Möglichkeit, den erzeugten Maschinencode auf verschiedene Weisen zu optimieren. Da die Just-in-time-Kompilierung gleichzeitig mit der Programmausführung stattfindet, stehen einem JIT-Compiler allerdings tendenziell weniger Ressourcen zur Verfügung als einem AOT-Compiler.
Zu den potentiellen Optimierungen zählen unter anderem:
- Konstantenfaltung – Vorauswertung statischer Ausdrücke
- Loop Invariant Code Motion – Herausziehen iterationsunabhängiger Berechnungen aus Schleifen
- Loop Unrolling – Entfalten von Schleifen
- Dead Code Elimination – Entfernen von nicht benötigtem Code
- Polymorphic Inline Caching[2] – Vorhalten der Adressen von aufgerufenen Methoden in einem Cache
- Maps – Teilen von Typinformationen ähnlicher Objekte[3]
Da einem JIT-Compiler zusätzlich Laufzeit-Informationen zur Verfügung stehen, kann er Closed-World-Annahmen treffen.Daher ergeben sich gegenüber dem AOT-Compiler noch weitere Optimierungsmöglichkeiten:
- Benutzen der gesammelten Typinformationen in den Polymorphic Inline Caches, um spezialisierte Versionen der aufgerufenen Methoden zu kompilieren[4]
- Runtime Type Feedback – Sammeln von Typinformationen zur Ausführungszeit, mit denen der ausgeführte Code optimiert werden kann.[5]
- Maps – Beschleunigung des Nachschlagens von Attributen[3]
Ein JIT-Compiler kann auch dynamische Optimierungen erkennen und durchführen.
Geschichte
Die Idee der Generierung von Maschinencode zur Laufzeit des Programms existiert schon seit den 1960er Jahren.[6][7] Die verschiedenen Ansätze reichen von der Kompilierung von regulären Ausdrücken[8] über das Erzeugen von Maschinencode für dynamische Sprachen bis hin zur automatischen Generierung von JIT-Compilern.[9]
In den 1980er Jahren arbeiteten Peter Deutsch und Allan Schiffman an einer effizienteren Implementierung für die Sprache Smalltalk-80. In ihrer Publikation „Efficient Implementation of the Smalltalk-80 System“ wird das Erzeugen, Verwenden und Vorhalten von „n-code“ (nativem Code) zur Laufzeit beschrieben.[10] Ihre Arbeit zeigte, dass es möglich ist, auch hochdynamischen reflexiven Code in Maschinensprache zu übersetzen.
Mitte der 1980er Jahre entwarfen David Ungar und Randall Smith SELF, eine prototyp-basierte dynamische Programmiersprache mit starkem Smalltalk-80-Einfluss. Unter Verwendung verschiedener Optimierungstechniken wie „Maps“ und „Message Inlining/Message Splitting“ erreichten sie in einigen Benchmarks in etwa die Hälfte der Geschwindigkeit von optimiertem C.[3]
1999 wurde HotSpot veröffentlicht, eine virtuelle Maschine für Java mit eingebautem Methoden JIT-Compiler. Der Name rührt von der Tatsache her, dass sie häufig ausgeführten Code (Hotspots) erkennt und optimiert.
JIT-Compiler werden unter anderem in Webbrowsern eingesetzt, um die Ausführung von JavaScript zu beschleunigen. Beispiele sind Jaeger-[11] bzw. IonMonkey[12] in Mozilla Firefox oder V8 in Google Chrome.
