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
BearbeitenSoftware 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
BearbeitenEin 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
BearbeitenDie 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
BearbeitenEin 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
BearbeitenTracing-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
BearbeitenJIT-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
BearbeitenDie 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.
Siehe auch
BearbeitenEinzelnachweise
Bearbeiten- ↑ Vasanth Bala, Evelyn Duesterwald, Sanjeev Banerjia: Dynamo: a transparent dynamic optimization system. In: PLDI ’00 Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation. 2000, ISBN 1-58113-199-2, S. 1–12, doi:10.1145/349299.349303 (cseweb.ucsd.edu [PDF; abgerufen am 21. März 2012]).
- ↑ siehe Polymorphic inline Caching in der englischsprachigen Wikipedia
- ↑ a b c C. Chambers, D. Ungar, E. Lee: An efficient implementation of SELF a dynamically-typed object-oriented language based on prototypes. In: OOPSLA ’89 Conference proceedings on Object-oriented programming systems, languages and applications. 1989, ISBN 0-89791-333-7, S. 49–70, doi:10.1145/74878.74884 (bibliography.selflanguage.org [PDF; abgerufen am 21. März 2012]).
- ↑ Urs Hölzle, Craig Chambers, David Ungar: Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In: Pierre America (Hrsg.): ECOOP ’91 Proceedings of the European Conference on Object-Oriented Programming. Springer, Berlin/Heidelberg 1991, ISBN 978-3-540-54262-9, S. 21–38, doi:10.1007/BFb0057013 (selflanguage.org [PDF; abgerufen am 22. November 2017]).
- ↑ Urs Hölzle, David Ungar: Optimizing dynamically-dispatched calls with run-time type feedback. In: PLDI ’94 Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation. ACM, New York NY 1994, ISBN 0-89791-662-X, S. 326–336, doi:10.1145/178243.178478 (cs.ucsb.edu [PDF; abgerufen am 21. März 2012]).
- ↑ John Aycock: A brief history of just-in-time. In: ACM Computing Surveys (CSUR). Band 35, Nr. 2, Juni 2003, S. 97–113, doi:10.1145/857076.857077 (csie.cgu.edu.tw [PDF; abgerufen am 21. März 2012]). csie.cgu.edu.tw ( vom 17. Dezember 2013 im Internet Archive)
- ↑ John McCarthy: Recursive functions of symbolic expressions and their computation by machine, Part I. In: Communications of the ACM. Band 3, Nr. 4, April 1960, S. 184–195, doi:10.1145/367177.367199 (formal.stanford.edu [PDF; abgerufen am 21. März 2012]).
- ↑ Ken Thompson: Programming Techniques: Regular expression search algorithm. In: Communications of the ACM. Band 11, Nr. 6, Juni 1968, S. 419–422, doi:10.1145/363347.363387 (fing.edu.uy [PDF; abgerufen am 17. April 2012]).
- ↑ Carl Friedrich Bolz, Antonio Cuni, Maciej Fijalkowski, Armin Rigo: Tracing the meta-level: PyPy’s tracing JIT compiler. In: ICOOOLPS ’09. Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems. ACM, New York NY 2009, ISBN 978-1-60558-541-3, S. 18–25, doi:10.1145/1565824.1565827 (bitbucket.org [PDF; abgerufen am 22. November 2017]).
- ↑ L. Peter Deutsch, Allan M. Schiffman: Efficient implementation of the smalltalk-80 system. In: POPL '84 Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages. ACM, New York NY 1984, ISBN 0-89791-125-3, S. 297–302, doi:10.1145/800017.800542.
- ↑ JaegerMonkey-Website
- ↑ IonMonkey-Website