Just-in-time-Kompilierung

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von JIT-Compiler)
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 ausgeführt. Gründe dafür sind beispielsweise Plattformunabhängigkeit oder die dynamische Natur der Programmiersprache. Einige Beispiele für solche Programmiersprachen sind JavaScript, Python oder Java. Die Ausführungsgeschwindigkeit ist jedoch häufig langsamer im Vergleich zu nativ kompilierten Programmen, welche aus direkt durch den Prozessor ausführbaren Instruktionen bestehen. Durch Just-in-time-Kompilierung versucht man, diesen Nachteil auszugleichen.

Es ist allerdings auch möglich, den Maschinencode kompilierter Programme zur Laufzeit zu modifizieren bzw. zu optimieren, was ebenfalls eine Form von Just-in-time-Kompilierung ist.[1]

Abgrenzung zur Ahead-of-time-Kompilierung[Bearbeiten]

Just-in-time-Compiler unterscheiden 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, und oft 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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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 - Vorhalten der Adressen von aufgerufenen Methoden in einem Cache
  • Maps - Teilen von Typinformationen ähnlicher Objekte [2]

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[3]
  • Runtime Type Feedback – Sammeln von Typinformationen zur Ausführungszeit, mit denen der ausgeführte Code optimiert werden kann. [4]
  • Maps – Beschleunigung des Nachschlagens von Attributen [2]

Ein JIT-Compiler kann auch dynamische Optimierungen erkennen und durchführen.

Geschichte[Bearbeiten]

(Hauptquelle des gesamten Abschnitts: [5])

Die Idee der Generierung von Maschinencode zur Laufzeit des Programms existiert schon seit den 1960er Jahren [6]. Die verschiedenen Ansätze reichen von der Kompilierung von regulären Ausdrücken [7] über das Erzeugen von Maschinencode für dynamische Sprachen bis hin zur automatischen Generierung von JIT-Compilern [8].

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.[9] 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.[2]

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 Browsern eingesetzt, um die Ausführung von JavaScript zu beschleunigen. Beispiele sind Jaeger-[10] bzw. IonMonkey[11] im Firefox Browser oder V8 in Googles Chrome Browser.

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1.  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 (PDF, abgerufen am 21. März 2012).
  2. 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 (PDF, abgerufen am 21. März 2012).
  3.  Urs Hölzle, Craig Chambers, David Ungar: Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In: America, Pierre (Herausgeber) (Hrsg.): ECOOP '91 Proceedings of the European Conference on Object-Oriented Programming. Springer Ort = Berlin/Heidelberg, 1991, ISBN 978-3-540-54262-9, S. 21–38, doi:10.1007/BFb0057013 (PDF, abgerufen am 21. März 2012).
  4.  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, USA 1994, ISBN 0-89791-662-X, S. 326–336, doi:10.1145/178243.178478 (PDF, abgerufen am 21. März 2012).
  5.  John Aycock: A brief history of just-in-time. In: ACM Computing Surveys (CSUR). 35, Nr. 2, 2003, S. 97–113, doi:10.1145/857076.857077 (PDF, abgerufen am 21. März 2012).
  6.  John McCarthy: Recursive functions of symbolic expressions and their computation by machine, Part I. In: Communications of the ACM. 3, Nr. 4, 1960, S. 184–195, doi:10.1145/367177.367199 (PDF, abgerufen am 21. März 2012).
  7.  Ken Thompson: Programming Techniques: Regular expression search algorithm. In: Communications of the ACM. 11, Nr. 6, 1968, S. 419–422, doi:10.1145/363347.363387 (PDF, abgerufen am 17. April 2012).
  8.  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, USA 2009, ISBN 978-1-60558-541-3, S. 18–25, doi:10.1145/1565824.1565827 (PDF, abgerufen am 21. März 2012).
  9.  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, USA 1984, ISBN 0-89791-125-3, S. 297–302, doi:10.1145/800017.800542.
  10. JaegerMonkey-Website
  11. IonMonkey-Website