4 ms·
For anyone interested in learning more about Tracing JITs and the problems involved in implementing them should read the paper "Trace-based Just-in-time Compila
by krig 11y ago
For anyone interested in learning more about Tracing JITs and the problems involved in implementing them should read the paper "Trace-based Just-in-time Compilation for Haskell" by Thomas Schilling [1].
In it, he explains the details of implementing a basic VM and tracing JIT based on LuaJIT, and deals with a lot of the issues involved. For example, the choice of where to begin a trace and for how long to trace is crucial for performance. Traces that are too long will rarely complete, and selecting poorly and tracing something that won't actually be on the hot path has significant cost. With poor trace selection, a tracing JIT can even be slower than an optimized interpreter. Interestingly, the language itself also influences the viability of tracing: A language with explicit loop instructions is easier to trace since any loop instruction is an intuitive starting point, whereas a language which relies on recursion and TCO is less cooperative in this regard. One possibility is rewriting recursive constructions to imperative loops in a pass prior to trace selection.
Personally, after reading the paper I think that there is the possibility for amazing performance from tracing JITs, but the unpredictability and reliance on heuristics makes the practical value over method JITs or static compilation questionable. It is similar to the complexities of GC implementation: As performance gains are made, complexity shoots through the roof while predictability suffers. There's no easy answer to that problem.
[1]: http://src.acm.org/2013/ThomasSchilling.pdf http://src.acm.org/2013/ThomasSchilling.pdf
- pron 11y agoI had a short conversation at ECOOP with Ben Titzer (who works on V8 at Google, and I think used to work on HotSpot at Sun), who said simply: tracing JITs are good for short programs; for large programs you need a partial-evaluation method JIT. Partial evaluation also produces better results for a larger class of programs. Tracing JITs' advantages are that they're simpler to write than partial evaluation JITs, and produce decent code faster, which is why they're used for JavaScript. There is great progress in partial evaluation JITs going on in the Graal/Truffle project[1] (Graal is the compiler; Truffle is a framework to write language frontends for Graal), which will be available as a pluggable compiler for HotSpot in Java 9. Here are a couple of optimizations Graal yields for Ruby: https://twitter.com/ChrisGSeaton/status/619885182104043520 https://twitter.com/ChrisGSeaton/status/619885182104043520 [1]: https://wiki.openjdk.java.net/display/Graal/Publications+and+Presentations https://wiki.openjdk.java.net/display/Graal/Publications+and...
- mafribe 11y agoAs far as I'm aware partial evaluation JITs like Graal/Truffle have atrociously bad warmup times. Warmup is the phase before the optimised code is ready to be executed. This is already a problem for tracing JITs, but is supposedly worse for partial evaluation JITs. All papers I have seen measure JIT performance post warmup.
- pron 11y agoRight, and this is why people say that the JVM is slow to start. It actually starts up pretty fast (a hello world program starts the JVM, reads the class file from a JAR archive, runs it and terminates in under 80ms), but it takes a while to achieve max performance. This is hardly a problem for server apps, and a potentially serious issue for client code like JavaScript on a web page. HotSpot has recently moved to a tiered-compilation scheme, where a fast compiler produces unoptimized code quickly, which continues to collect metrics for the profile-guided optimization, and the optimizing compiler kicks in later, once enough profiling information has been collected.
- mafribe 11y agoThe JVM is not a tracing JIT compiler. Tracing is a very slow operation. Hence the warmup problem is substantially worse for tracing JITs. I saw figures for warmup in tracing JITs that were so hillariously bad, that I thought they must be a typo. People I know are currently writing a paper on this subject. I hope it will come out in the next 2 or 3 months. That should put our discussion, and the warmup performance of tracing JITs, on a firmer basis.
- loganhough 11y ago> The JVM is not a tracing JIT compiler He didn't claim or imply it was. > Tracing is a very slow operation. Wait a second - you were just saying that PE was slow. Now you are saying that tracing is slow instead? > Hence the warmup problem is substantially worse for tracing JITs. This is contrary to everything I've seen in the research. Tracing JITs like LuaJIT and PyPY as fast to warm up compared to method JITs and PEs.
- mafribe 11y agoThe Schilling paper is mostly a re-rendering of the original paper Dynamo: A Transparent Dynamic Optimization System [1] by Bala et al, which invented (or better reinvented and popularised) tracing JIT compilation. It might be worth reading the original. In addition, Haskell is not such a great target for JITing, as it's statically typed, leaving less scope for optimisation at run-time. [1] https://www.cs.virginia.edu/kim/courses/cs771/papers/bala00dynamo.pdf https://www.cs.virginia.edu/kim/courses/cs771/papers/bala00d...
- chrisseaton 11y ago> Haskell is not such a great target for JITing, as it's statically typed, leaving less scope for optimisation at run-time I'd refute this. Types are just one thing that you can speculatively optimise for at runtime which may not be practical to do at compile time. Other things include value ranges, tighter types than there are in the source code, branches taken/not-taken, contended/non-contended shared resources such as MVars and TVars, whether an Integer fits into a word or not, etc etc. In my group we're looking at using a JIT for C, where we can do things such as inline through a function pointer by speculating that it is stable.
- mafribe 11y agoI agree that there is scope for JITing in Haskell. But JITing is not without cost, and in statically typed languages, some of the big gains that make JITs for Javascript or Python so powerful, go away. If you are using C in a way that requires frequent invocation through a function pointer in hot code, you are probably using an OO-idiom, so casting, so circumventing C's typing.