5
$\begingroup$

How the implementations of JIT in R, Python and Julia differs? Are there characteristics of the language that make the compiler's job harder or less efficient in some language compared to others?

On a user point of view, the benefits JIT/not JIT (or type unstable in Julia) seems to differ largely in the different implementations, and I was curious why.

(edited following comments)

$\endgroup$
3
  • 3
    $\begingroup$ Pypy, Jython, and IronPython all do have automatic JIT compilation; CPython has none at all. There are also multiple implementations of R with different characteristics too. What are you interested in specifically here? It will help to narrow in on a particular application domain, design vs implementation, etc. $\endgroup$
    – Michael Homer
    Oct 23, 2023 at 18:03
  • 5
    $\begingroup$ The way your question is written, suggests you think JIT compilation is a feature of a language, rather than a property of a language implementation. But languages can have multiple implementations, so there may be implementations of the same language with and without JITs, and there may be implementations with JITs which work the same way. Nonetheless, it may still make sense to ask how the language design affects the usefulness of a JIT or the ease of implementing one. $\endgroup$
    – kaya3
    Oct 23, 2023 at 18:38
  • 1
    $\begingroup$ I don't know enough to post this as an answer, but it seems from comments and links below that this question is open to a frame challenge: it's not that Julia has a particularly powerful JIT compiler, it's that it doesn't have a JIT compiler at all in the sense that other implementations use that term, it has an unusual "just ahead of time" compiler. $\endgroup$
    – IMSoP
    Oct 29, 2023 at 15:14

3 Answers 3

3
$\begingroup$

One difference is whether the code is compiled to bytecode or native code.

GNU R evaluates code by converting it to bytecode and then interpreting the bytecode (the bytecode interpreter is called a virtual machine, because this bytecode is similar to assembly or machine code). I know some Python interpreters also use bytecode because that's what .pyc files are.

Julia evaluates code by type-checking, converting it to LLVM IR, and then LLVM converts that to native code (AKA machine code) which the processor can run directly. Some R and Python implementations may also do this but I'm not sure.

Native code runs faster than bytecode, but usually takes longer to generate. Bytecode has the flexibility that you can create whatever kinds of instructions you want, but LLVM IR and assembly have a fixed set of low-level instructions you must use. Because they're low-level, LLVM IR and native code are also trickier for the developer to generate correctly and debug.*

There are also compilers that generate bytecode, but then optimize the bytecode and/or generate native code from it. Usually the optimizations and native code generation are done after the code is run multiple times, because they use feedback recorded from previous runs (such as the runtime types of values) and also take longer (don't want to waste time generating expensive native code which ends up rarely used). Bytecode is more high-level than native code, and many of these optimizations would be much harder or straight-up impossible if they were done on machine-code directly.

More resources:


* Another benefit of bytecode over native code: the same bytecode can be run on any platform (assuming there's an interpreter for the platform), but native code will only run on the architecture/vendor/OS is was generated for. This isn't very important for JIT compilers since you can just share the source code across platforms, but sometimes it's useful to pre-compile and share the bytecode to reduce startup times.

Questions related to "bytecode vs native code": What are the pros and cons of interpreted programming language? (substitute "interpreted language" for "bytecode" and "compiled language" for "native code"), What are the pitfalls of using an existing IR/compiler infrastructure like LLVM?

There's a very recent paper (AST vs. Bytecode: Interpreters in the Age of Meta-Compilation) which claims that interpreting the AST directly may be as fast or even faster than interpreting its bytecode (of course it depends on the bytecode implementation). (Related question: What are the pros/cons of a tree-based interpreter vs a bytecode-VM-based interpreter?)

$\endgroup$
3
  • $\begingroup$ Maybe I'm misunderstanding, but this answer seems to mostly be discussing compilation to bytecode vs native code in general, rather than how that impacts the design and effectiveness of a JIT compiler. My understanding is that many (most?) JIT compilers are going from a bytecode of some sort to native code, e.g. Java HotSpot, PHP OpCache, Mozilla SpiderMonkey for JS, etc. Julia seems to be unusual not in that it targets native code, but that it does so directly from the source (or an AST?), rather than having a bytecode interpreter running alongside the JIT compiler. $\endgroup$
    – IMSoP
    Oct 29, 2023 at 15:07
  • $\begingroup$ There's a broad spectrum. Some "compilers" translate AST to bytecode only (and some wouldn't even call these "JIT compilers" although bytecode translation is a form of compilation and it happens during runtime). Most "real" JIT compilers translate AST into bytecode, do some recording, and then translate "hot" bytecode into optimized native code. Julia is unusual in that it doesn't do any recording, and AFAIK does go directly from AST to LLVM "bytecode"; its types allow it to do optimizations other JITs need recording for (and also, never has to deoptimize from native code back to bytecode). $\endgroup$
    – tarzh
    Oct 30, 2023 at 0:37
  • $\begingroup$ My point stands: what you are describing is the variety of compilers, not JIT compilers. For instance, the original part of SpiderMonkey that compiles JS source to bytecode and interprets it would not be called a JIT compiler; the JIT compiler is an additional component (TraceMonkey, IonMonkey, etc) that runs on top of that. The same with PHP - nobody called the original Zend Engine and OpCache "JIT", but PHP 8.0 added a JIT component on top of it. Maybe there are counterexamples where the bytecode compiler itself is referred to as JIT, but you haven't mentioned any. $\endgroup$
    – IMSoP
    Oct 30, 2023 at 7:33
2
$\begingroup$

Overview

Your question implicitly covers three different comparisons:

  • Different execution models used in implementations of a language. For instance, the same Python code can be executed using either CPython or PyPy.
  • Differences between languages in what execution models are most effective. For instance, JavaScript is designed to be highly dynamic; Rust is designed to use extensive up-front analysis.
  • Differences within an implementation between different settings. For instance, systems often combine an interpreter and a JIT compiler, allowing comparisons "with and without JIT".

Rather than thinking of different "implementations of JIT compilation", it is perhaps more helpful to think of JIT compilation as a category of techniques. Different languages, and different implementations, will apply those techniques differently, so it's hard to put a single value on "the benefits of JIT".

Compilation vs Interpretation

Discussions of execution models generally begin with the traditional distinction between a compiler which takes a unit of source code, produces equivalent processor instructions, and discards the source code; contrasted with an interpreter which reads directly from the source code, translating and immediately executing one instruction at a time. In practice, the picture is considerably more complex than that.

Firstly, there is a spectrum of how much is compiled. Modern compilers proceed through multiple stages of intermediate representation - for instance, a stream of tokens, an abstract syntax tree, a target-independent bytecode, and then the target instruction set. An interpreter can take over at any stage of this process - some BASIC implementations replace keywords with binary tokens, then interpret one instruction at a time. One of the most common current models is to compile source code to some level of bytecode, then interpret that.

Secondly, there is variation in when compilation happens. Compilation may be a separate step explicitly invoked by the user, or it may happen implicitly when a particular module of source code is loaded. The result may be stored on disk, kept in the running process's memory, or cached in shared memory owned by the run-time.

For example:

  • Java source code is compiled explicitly by the user to JVM bytecode, and saved to disk. The bytecode is a low-level instruction set for a stack-based virtual machine, and can be produced for languages other than Java.
  • The PHP reference implementation is the Zend Engine, which compiles PHP source code one file at a time into "op codes"; the compiler is generally invoked the first time a file is included and the result cached in shared memory by a module called OpCache. The op codes are high-level instructions closely tied to the language, which are then executed in an interpreter as the program runs.

Why JIT?

This leads us to "dynamic compilation" and "just-in-time compilation". There's a fascinating look into the history of the concepts here: John Aycock. 2003. A brief history of just-in-time. ACM Comput. Surv. 35, 2 (June 2003), 97–113. The term "JIT" was popularised by Sun's "HotSpot" implementation of Java, and is generally used to refer to systems where:

  • Machine code is generated while the program is running
  • The compiler optimises the result with information obtained from the running program

(Note that while the PHP Zend Engine discussed above could be described as "compiling just in time", it is not normally referred to as a "JIT compiler"; we could instead label it a compile and go system.)

The fact that the program is already executing rather than about to execute makes additional information available to the optimiser, such as:

  • Which path through conditional code is most often taken
  • Which types are most often passed to a function which takes a dynamic type as input
  • Which polymorphic methods / dynamically dispatched functions are frequently resolved in a particular context

Theoretically, producing optimised machine code in advance can always give better run-time performance than producing that same machine code while the program is running, because the optimisation and compilation itself take time. This can include feedback from a previous execution of the program, as in profile-guided optimisation. JIT compilation is mostly useful when it is impossible, or very difficult, to produce that "perfect" code ahead of time; for instance:

  • The implementation stores an intermediate representation rather than a native executable by design; e.g. Java's JVM (which provides portability) or .Net's CLR (which provides secure interoperation between source languages)
  • The language itself is highly dynamic, making static analysis difficult; e.g. Python, PHP, JavaScript, etc.

JIT implementations

This commonly leads to a JIT compiler being added alongside a bytecode interpreter - examples include Sun's HotSpot mentioned earlier, Mozilla's TraceMonkey and successors for JavaScript, PyPy for Python, and the current version of the PHP Zend Engine + OpCache. This allows the flexibility to spend additional time optimising "hot paths" which are frequently executed, and fall back to the interpreter for less used paths, or those which are hard to analyse and optimise.

In such implementations, you can see the impact the JIT is having on a particular scenario by disabling it and forcing everything through the interpreter; but that doesn't mean a different interpreter (e.g. with a different form of bytecode) couldn't be just as fast. In the case of PHP, the improvements to the Zend Engine in PHP 7.0 had a bigger impact on many workloads than adding a JIT on top in PHP 8.0.

The reference implementation of Julia uses a slightly different strategy, sometimes referred to as a "just ahead of time compiler". Rather than treating the interpreter as the default, and optimising certain paths during run-time, it focusses primarily on compiling individual functions specialised to particular types. It is just one example of how varied strategies can be, and how hard it is to compare unless there are multiple mature implementations for the same language.

$\endgroup$
1
$\begingroup$

Are there characteristics of the language that make the compiler's job harder or less efficient in some language compared to others?

This is the main difference. For lots of details, I recommend reading https://arxiv.org/abs/1411.1607, but to summarize, Julia uses type inference and specialization to generate native code for functions based on the argument types of it's arguments (section 3).

It is not that “for loops” are inherently slow by themselves. The slowness comes from the fact that in the case of most dynamic languages, the system does not have access to the types of the variables within a loop... This leads to users often talking about “slow for loops” or “loop overhead”... Julia has a transparent performance model. For example a Vector{Float64} as in our example here, always has the same in-memory representation as it would in C or Fortran; one can take a pointer to the first array element and pass it to a C library function using ccall and it will just work. The programmer knows exactly how the data is represented and can reason about it... In the case of say, Complex128, Julia stores complex numbers in the same way as C or Fortran. Thus complex arrays are actually arrays of complex values, where the real and imaginary values are stored consecutively... a programmer can also define immutable data types, and enjoy the same benefits of performance for composite types as for the more primitive number types (bits types).

This is in large part made possible by a number of relatively core differences in the language. For example, in Julia the result of evaling a function is only visible when you next enter the global scope. This ensures that the definition of functions doesn't change out from under you which enables many optimizations that are basically impossible in more dynamic languages. Another similar difference is that Julia is careful to make some math functions return the same type. For example, in python 2**-2 will return 0.25 while 2**2 will return 4. This means that the language is unable to (even in theory) propagate the types of variables past a call to the function. In julia, Int^Int always returns an Int (and errors if the exponent is negative). This is slightly less friendly to a new user, but allows for generation of much faster code, since you don't have to insert type-checks everywhere.

$\endgroup$
5
  • $\begingroup$ This doesn't really seem to address JIT compilation at all. The fundamental point of any optimising JIT compiler is that you can use runtime information in place of static to produce appropriately-specialised code, and the quote is all about data representation. $\endgroup$
    – Michael Homer
    Oct 23, 2023 at 21:14
  • 2
    $\begingroup$ The JIT compiler in Julia is particularly simple and effective vs other JITs, because Julia has more static guarantees. Simple JIT compilers in very dynamic languages have limited optimizations. e.g.: if a function's arguments don't have checked types (like R and most Python), the compiler has to support the case where the function is called with "wrongly"-typed arguments, so it can't unbox the arguments and devirtualize e.g. math operators. If a function name can be re-assigned to, the program must lookup the function by name every time it's called, and can't make guarantees about it. $\endgroup$
    – tarzh
    Oct 23, 2023 at 21:57
  • 1
    $\begingroup$ There are techniques for dynamic languages to do things requiring stronger guarantees like unboxing, skipping redundant variable lookups, and function inlining; but these are complicated. For example speculation: the compiler checks a certain property at runtime (e.g. variable is an integer) and then the following code assumes this property (e.g. unbox the variable and perform an integer addition). Except the compiler must handle the case where the property doesn't hold and deoptimize: transfer code execution to unoptimized code, so that semantics are preserved. $\endgroup$
    – tarzh
    Oct 23, 2023 at 22:09
  • 2
    $\begingroup$ (Some R compilers do speculation and deoptimization, and I believe some Python compilers do as well. Notably, JavaScript V8 does). Julia's JIT doesn't do any speculation, and doesn't even collect feedback (which is used to determine the speculated properties). Yet it can do optimizations like unboxing and inlining because of it's semantics. At the same time, its semantics still enable rather dynamic code (e.g. you can still write functions without types) and it's still JIT compiled, vs. a language like C which has even stronger optimizations but must be fully compiled and linked first. $\endgroup$
    – tarzh
    Oct 23, 2023 at 22:12
  • 2
    $\begingroup$ > The fundamental point of any optimising JIT compiler is that you can use runtime information in place of static to produce appropriately specialised code Julia doesn't really do this. (and for that reason is often referred to as a "Just Ahead of time compiler") $\endgroup$ Oct 23, 2023 at 22:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .