Dynamo: A Transparent Dynamic Optimization System [1]
[1] https://www.cs.virginia.edu/kim/courses/cs771/papers/bala00d...
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.
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.
You were specifically talking about tracing a static vs dynamic language. I agree, the opportunities for a speed up under dynamic languages is larger because there is more code bloat to dispatch on object type, where in Haskell that should have been elided during compilation, the Haskell code is much tighter to begin with. So the speedups seen for tracing Haskell should be similar to the gains seen by the Dynamo team when they traced native executables (most were generated from C afaik). Dynamo didn't have type information other than what it could extract from the assembly.
I'll try and make a more complete post next time.
As to Dynamo, I think some of the key gains came from the ability to shortcut jumps to jumps to jumps to ... that could arise from linking separately compiled code. However, modern CPUs diminish the penalty such frivolous jumping incurs, so Dynamo became less and less competitive with tracing on higher-level languages. (BTW, Dynamo can trace everything, not just C executables.)
Haskell seems like an interesting language to implement, being both statically typed and lazy. Static typing provides some optimization avenues but having to evaluate thunks at runtime complicates many common optimization strategies.
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
[1]: https://wiki.openjdk.java.net/display/Graal/Publications+and...
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.
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.
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.
Tracing JITs like LuaJIT and PyPY as fast to warm up compared to method JITs and PEs.
I'm a bit uncomfortable with saying "I have heard ..." As far as I'm aware there is no actual published research on this question. But there will soon be, so I would like to withdraw from this debate until I have read that research.
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