Ask HN: Have tracing JIT compilers lost? | Hacker News Reader

Ask HN: Have tracing JIT compilers lost?

9 pointsbakery2k3 comments

The title refers to the famous 2010 thread "Have tracing JIT compilers won?" [1] on "Lambda the Ultimate". There, it was hypothesized that for dynamically-typed languages (JavaScript with Firefox's TraceMonkey and Lua with LuaJIT), "tracing JITs are turning up as the winners" and that per-method JITs, such as V8, may not "be able to keep up".

Since then, however, Firefox has left TraceMonkey behind and switched to a succession of method JITs, and in general, the major JavaScript engines have converged on an implementation strategy of a fast interpreter and one or more JIT compilation tiers (V8's TurboFan [2]/JavaScriptCore's Baseline & DFG & FTL [3]/SpiderMonkey's Baseline & IonMonkey [4]/ChakraCore's Simple & Full [5]).

Notably, none of these JavaScript JITs use tracing. Other dynamic language JITs that have appeared since 2010 (e.g. Julia, Pyston) have also avoided tracing. The only remaining major tracing JITs seem to be LuaJIT (which is no longer receiving new features) and PyPy (which uses a unique meta-tracing approach).

Contrary to what was predicted in 2010, it appears that for dynamic languages, method JITs have won over tracing JITs. For what reason(s) have tracing JITs been superseded? Have method JITs proven:

- Less complex to develop and maintain?

- Faster in the best/average case?

- To provide more consistent performance, i.e. less slowdown in the worst case?

Do you see any future for tracing JIT compilers, or do you expect future dynamic language JITs to only use the per-method strategy? Does tracing have any advantages - are there any situations in which tracing may be a good choice, or have tracing JITs proven to be a dead end?

[1] lambda-the-ultimate.org/node/3851 | [2] v8project.blogspot.com/2017/05/launching-ignition-and-turbofan.html | [3] webkit.org/blog/3362/

[4] blog.mozilla.org/javascript/2013/04/05/the-baseline-compiler-has-landed/ | [5] github.com/Microsoft/ChakraCore/wiki/Architecture-Overview

> To provide more consistent performance, i.e. less slowdown in the worst case?

AFAICT, this is the reason for the decline of trace-based JIT compilers. When Mozilla introduced JaegerMonkey, their first method-based JIT (which went on to make TraceMonkey obsolete), their reasoning was "tracing tends to interact poorly with certain styles of code" - specifically "the downside of the tracing JIT is that we have to switch back and forth between the [slow] interpreter and the machine code [...] a lot" [https://hacks.mozilla.org/2010/03/improving-javascript-perfo...].

For an example of a situation in which tracing performs poorly, consider a hot trace through an if-else statement. The trace will only contain one of the statement's two branches - leading to reduced performance if the "off-trace" branch is frequently taken.

> Faster in the best/average case?

The issue with tracing isn't best-case performance - again, from Mozilla: "when we’re able to “stay on trace” TraceMonkey wins against every other engine" [ibid]. Also, it seems tracing can compete in the average case against somewhat-advanced method-based JITs: "type inference was added to JaegerMonkey, which made it faster on average" [https://blog.mozilla.org/nnethercote/2011/11/23/memshrink-pr...].

> Less complex to develop and maintain?

In fact, I believe a good method-based JIT is probably more complex than a trace-based one. When compiling at method-granularity, with incomplete information about types, complex features are required e.g. On-Stack Replacement (if the current method becomes "hot", it needs to be replaced by a compiled version), Inline Caches, Hidden Classes and Deoptimization.

In a trace-based JIT, all these features can be replaced by "just compile another trace".

> Does tracing have any advantages?

In summary, I think the advantage of tracing is its ability to give very good best- and average-case performance (albeit with poor worst-case performance), with less complexity than method-based compilation. This is a good trade-off for LuaJIT (a few people supporting ~50kLoC and specifically targeting a small footprint), but not for the leading JavaScript engines (who can afford large teams and millions of LoC).

> In fact, I believe a good method-based JIT is probably more complex than a trace-based one. When compiling at method-granularity, with incomplete information about types, complex features are required e.g. On-Stack Replacement (if the current method becomes "hot", it needs to be replaced by a compiled version), Inline Caches, Hidden Classes and Deoptimization.

Don't you have exactly the same problems in a tracing jit? For example, if the running while-loop becomes hot it would need to be replaced with an optimized version of it.

Reply on news.ycombinator.com