Tracing JITs and modern CPUs
github.com
github.com
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.
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.
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.
How many do that to their students nowadays?
Array programming also keeps absolute program size small which means your program isn't running in main memory but in cache memory which produces anywhere from 10-100x speedups for business software just by itself!
I don't know if I fully understand what you mean by object-orientated.
Yeah, your metapoint is is worthwhile, all the JIT in the world aint gonna help you if you're cache missing every damn fetch(hello Java).
Acton (sort of) has a talk about that too. Except he speaks about traditional, ahead-of-time compilers. Tldr is that because of how the vast majority of programmers arrange their data, CPUs spends the vast majority of their time stalling on memory. Therefore improvements in optimizing compilers can only marginally help the marginally small section of running time spent actually exercising the ALUs. The solution is to devote more effort to changing our habits regarding data layouts.
Working with FPGAs and DRAM really makes a lot of reasons behind this and lot of other "obscure" performance issues like pipelining crystal clear.
You can effectively define a struct as references to separate sub-structs in separate arrays. Member access syntax can be flattened so that it doesn't matter in the syntax which sub-struct a particular field is in. Realize that you aren't using a field as often as you expected? Move it's declaration from the hot sub-struct to the cold one and recompile. That will move all instances of that field from the hot array to the cold array, but no other code needs to be edited.
A fairly random example of OO "business logic": https://git.eclipse.org/c/b3/b3.git/tree/org.eclipse.b3.aggr...
(I went clicking through Eclipse because I knew I could count on it to have lots and lots of this kind of abstraction-heavy bland Java. I'm not even saying this particular bit of code is slow, it's just that there's a lot of OO code that looks vaguely like this.)
If you're iterating over one or two values in a struct via AoS it's very painful from a memory caching standpoint since you're only getting sizeof(member) / sizeof(struct) efficiency.
In a SoA situation all your data for members is tightly packed so you usually get better cache coherency.
That said the best approach is actually looking at your data access patterns and packing your data appropriately. Unfortunately some languages don't have value types(most managed languages except C#). This is why C/C++ is usually faster than managed languages, they can get close on generated code but can be off by a factor of 50x in memory access performance.
This is a common misconception that is a result of Java's current state. Control over memory layout and garbage collection are two completely orthogonal issues. At the moment, Java just happens to be both GCed and to afford little control over memory layout. Currently, the HotSpot team (HotSpot is the name of OpenJDK's JVM) is working on project Valhalla and project Panama, two efforts scheduled for Java 10 and intended to give the JVM all the memory layout control you need.
Most GCs want to be able to compact the heap, that means they lean in favor of reference based models by default.
It's not exclusive like you mention but to my knowledge C# is the only language with explicit guarantees. I was aware of the effort around Java's value types, however how long till we can reasonably see this in production?
You can do this in Java today but it involves lots of nasty ByteBuffer manipulation(in which FlatBuffers is fantastic for). You'll still pay for the conversions from bytes to the actual types you want.
If you're dealing with these types of performance problems it's best to treat them with a language that's well suited to deal with them. There's nothing wrong with using Java for higher level business logic and delegating the heavy lifting to a stack that's designed to deal with them.
I don't see how this follows. Copying GCs do compact the heap, but when you use values you're basically saying "these two things go together". You're only making life easier for the GC (well, you're also creating larger objects, but that might just require a small adjustment of the GC strategy).
> how long till we can reasonably see this in production?
Four years probably... Still, that doesn't change the fact that layout and GCs are orthogonal.
Just that in practice you don't see memory layout in languages that are managed. Since I'm usually not in a habit of building a new languages to solve problems it's something worth understanding when making a technical selection on a language.
Eiffel also offers value types (aka expanded), but it is reference by default.
This only happens because the Pascal branch of languages with GC, sadly failed in the mainstream (for several reasons).
Modula-3, Eiffel, Oberon, Oberon-2, Component Pascal all offer the same data access patterns and packing available to C and C++.
Those boxes have a lot of overhead (in PHP it's around 140 bytes!), and because a major identified problem is the waste of valuable cache space and CPU time book-keeping these boxes, a lot of JIT and compiler research is about how to eliminate the boxes.
You can see why they do this when considering a program like:
$a = array();
for($i = 0; $i < 100000; ++$i) $a[$i] = rand()*65536;
sort($a);
However.
Eliminating those boxes has proven to be very difficult, and while I have heard great things about Java 10, I am reserved because I also heard great things about Java 5. And Self. I do not expect JIT/compilers will get smart enough to actually solve this problem in my lifetime.
On the other hand, array programming languages allow you to get that space-overhead that C/C++ has in an interactive (and usually interpreted) language, so it so happens that you don't have to choose between a nice interpreted programming language with introspection, automatic memory management, and so on, and high performance, but it does mean you have to program the arrays instead of the atoms.
I do not understand how that source file is "OO business logic".
Markdown, tags, comments plus a index (README.md) if you need one.
> Consider these optimization tips: Avoid nested loops.
I don't think this is true at all. The article is arguing that because a trace only contains one loop, that nested loops can't be trace-compiled.
As I understand it, nested loops are totally possible to trace-compile by having multiple traces that link to each other. See what Mike Pall wrote about LuaJIT (http://www.freelists.org/post/luajit/How-does-LuaJITs-trace-...):
"If the inner loop has a low iteration count, it'll be unrolled and inlined. For most loop nestings there'll be a single trace for the outer loop that goes 'around' the inner loop and joins its exit with its entry. Otherwise traces link to each other in linear pieces."
I would take what this article says with a heavy grain of salt. I don't think that tracing JITs are at all like "programming in a straight jacket."
Look at the LuaJIT performance optimization guide. There is nothing in there about avoiding nested loops, avoiding tiny loops, or avoiding loops with unpredictable iteration counts. It does however recommend reducing unpredictable branches: http://wiki.luajit.org/Numerical-Computing-Performance-Guide
Luke (the posts' author) and others are building a high performance software Ethernet switch[1] using LuaJIT. Let me assure you that these considerations actually come from experience rather than speculation.
> As I understand it, nested loops are totally possible to trace-compile by having multiple traces that link to each other.
Sometimes it works, sometimes it doesn't. We can't really expect everybody using Snabb Switch to understand the internals of LuaJIT so restrictive guidelines are useful for us.
Disclaimer: Consulting for Snabb GmbH
[1]: https://github.com/snabbco/snabbswitchhttps://github.com/sna...
Good to know. The article did not make this clear.
I wish it was possible to do things along the lines of "fetch this data from RAM and at the same time start recomputing it, whichever is faster".
And also, I wish there was a "branch upcoming / branch execute" split. In other words, instead of just "here's a branch", it's more along the lines of "you will have to branch on <x>. <other instructions> now branch on <x>." Effectively a variable number of branch-delay slot(s). Wouldn't help for straight pointer-chasing, but in other situations it could.