Just-in-time compilation

from Wikipedia, the free encyclopedia

Just-in-time compilation (JIT compilation) is a method from practical computer science to translate (partial) programs into machine code at runtime . The aim is to increase the speed of execution compared to an interpreter . JIT compilers are mostly used in the context of a virtual machine , where platform-independent bytecode is to be executed.

Just in time in this context means “on time”, “when required” (analogous to just-in-time production ).

motivation

Nowadays software is written in a variety of different programming languages. Many of these programming languages are typically not compiled into machine code prior to execution, but instead are executed by a virtual machine . Reasons for this are, for example, platform independence or the dynamic nature of the programming language. Some examples of such programming languages ​​are JavaScript and Python . The execution speed of the VM corresponds to that of an interpreter and is often slower compared to natively compiled programs that consist of instructions that can be executed directly by the processor. One tries to compensate for this disadvantage by just-in-time compilation.

However, it is also possible to modify or optimize the machine code of compiled programs at runtime, which is also a form of just-in-time compilation.

Differentiation from ahead-of-time compilation

Just-in-time compilers differ from ahead-of-time compilers (AOT) in terms of the time at which the translation is carried out:

  • Ahead-of-time compilers translate the entire program before it is executed: The programmer translates the program into the finished, directly executable compilation using the AOT compiler . It is then passed on (to the user).
  • JIT compilers, on the other hand, only compile during runtime, sometimes only parts of the program.

In addition, AOT compilers and JIT compilers typically have different optimization options.

Some languages ​​such as B. C , C ++ or Fortran are particularly suitable for ahead-of-time compilation (e.g. due to static typing ), while other, more dynamic languages ​​such as Python or JavaScript find it difficult to be "ahead of time" efficiently Let machine code compile. A JIT compiler is therefore suitable for such languages, since it can collect and use information about the executed program at runtime.

functionality

The general functionality of a JIT compiler is to generate executable machine code while the program is running. Since the compilation is carried out during the execution of the program, it cannot be arbitrarily complex, as this could otherwise noticeably impair the execution speed of the actual program. Therefore, one usually limits oneself to frequently executed program parts. These are typically responsible for most of the program's execution time, which is why compiling and optimizing them is particularly worthwhile. The task of the JIT compiler is to identify these program parts, to optimize them and then to translate them into machine code which can be executed directly by the processor. The generated code is usually cached so that it can be reused at a later point in the program execution.

There are two common methods for implementing a JIT compiler:

Method JITs

A method JIT translates complete functions or methods of the program at runtime. The information about the call context of the functions or methods is used here, e.g. B. At runtime it is known which types the parameters passed.

Tracing JITs

Tracing JITs are based on the assumption that programs spend most of their time in loops. Therefore a tracing JIT tries to identify frequently executed paths in loops. The sequence of operations that make up these execution paths are also called traces. After their identification, traces are typically optimized and then translated into machine code.

Optimization possibilities

Similar to AOT compilers, JIT compilers have the option of optimizing the generated machine code in various ways. Since just-in-time compilation takes place at the same time as program execution, a JIT compiler tends to have fewer resources available than an AOT compiler.

The potential optimizations include:

  • Constant convolution - pre-evaluation of static expressions
  • Loop Invariant Code Motion - Extracting iteration-independent calculations from loops
  • Loop Unrolling - unfolding loops
  • Dead Code Elimination - removing unnecessary code
  • Polymorphic Inline Caching - Holding the addresses of called methods in a cache
  • Maps - sharing type information of similar objects

Since runtime information is also available to a JIT compiler, it can make closed-world assumptions . Therefore, there are further optimization options compared to the AOT compiler:

  • Using the collected type information in the polymorphic inline caches to compile specialized versions of the methods called
  • Runtime Type Feedback - Gathering execution time type information that can be used to optimize the code being executed.
  • Maps - speed up the look-up of attributes

A JIT compiler can also recognize and carry out dynamic optimizations .

history

The idea of ​​generating machine code while the program is running has existed since the 1960s. The different approaches range from the compilation of regular expressions and the generation of machine code for dynamic languages ​​to the automatic generation of JIT compilers.

In the 1980s Peter Deutsch and Allan Schiffman worked on a more efficient implementation for the Smalltalk-80 language. In their publication “Efficient Implementation of the Smalltalk-80 System”, the creation, use and provision of “n-code” (native code) at runtime is described. Their work showed that it is possible to translate highly dynamic reflexive code into machine language.

In the mid-1980s, David Ungar and Randall Smith designed SELF , a prototype-based dynamic programming language with a strong Smalltalk 80 influence. Using various optimization techniques such as "Maps" and "Message Inlining / Message Splitting", they achieved roughly half the speed of an optimized C in some benchmarks .

In 1999 HotSpot was released, a virtual machine for Java with a built-in methods JIT compiler. The name comes from the fact that it recognizes and optimizes frequently executed code (hotspots).

JIT compilers are used, among other things, in web browsers to accelerate the execution of JavaScript. Examples are Jaeger or IonMonkey in Mozilla Firefox or V8 in Google Chrome .

See also

Individual evidence

  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 , pp. 1–12 , doi : 10.1145 / 349299.349303 ( cseweb.ucsd.edu [PDF; accessed on March 21, 2012]).
  2. ↑ see Polymorphic inline caching in the English language Wikipedia
  3. ↑ 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 , pp. 49–70 , doi : 10.1145 / 74878.74884 ( bibliography.selflanguage.org [PDF; accessed March 21, 2012]).
  4. ↑ Urs Hölzle, Craig Chambers, David Ungar: Optimizing dynamically-typed object-oriented languages ​​with polymorphic inline caches . In: Pierre America (Ed.): ECOOP '91 Proceedings of the European Conference on Object-Oriented Programming . Springer, Berlin / Heidelberg 1991, ISBN 978-3-540-54262-9 , pp. 21–38 , doi : 10.1007 / BFb0057013 ( selflanguage.org [PDF; accessed November 22, 2017]).
  5. ↑ 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 , pp. 326–336 , doi : 10.1145 / 178243.178478 ( cs.ucsb.edu [PDF; accessed on March 21, 2012]).
  6. ^ John Aycock: A brief history of just-in-time . In: ACM Computing Surveys (CSUR) . tape 35 , no. 2 , June 2003, p. 97–113 , doi : 10.1145 / 857076.857077 ( csie.cgu.edu.tw [PDF; accessed on March 21, 2012]). csie.cgu.edu.tw ( Memento of the original from December 17, 2013 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  @1@ 2Template: Webachiv / IABot / web.csie.cgu.edu.tw
  7. ↑ John McCarthy: Recursive functions of symbolic expressions and Their computation by machine, Part I . In: Communications of the ACM . tape 3 , no. 4 , April 1960, p. 184–195 , doi : 10.1145 / 367177.367199 ( formal.stanford.edu [PDF; accessed on March 21, 2012]).
  8. ↑ Ken Thompson: Programming Techniques: Regular expression search algorithm . In: Communications of the ACM . tape 11 , no. 6 , June 1968, p. 419-422 , doi : 10.1145 / 363347.363387 ( fing.edu.uy [PDF; accessed April 17, 2012]).
  9. ^ 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 , pp. 18–25 , doi : 10.1145 / 1565824.1565827 ( bitbucket.org [PDF; accessed November 22, 2017]).
  10. ^ 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 , pp. 297-302 , doi : 10.1145 / 800017.800542 .
  11. ↑ Jaeger Monkey site
  12. ↑ IonMonkey site