A Deep Introduction to JIT Compilers: JITs are not very Just-in-time
carolchen.me
carolchen.me
And lucky you. (Seniors this year got a raw deal.)
PS. Great use of "jit" in a different context.
Great blog, and you're into aerials! Always exciting to see someone else here who gets their invert on.
EDIT: When I was in high school, msdos and windows viruses were all the rage: self-modifying polymorphic code that injected itself into the RAM of other processes, having no identical strings longer than a few bytes between each instance of the virus, etc. Way useless than jit stuff, but a comparable level of "depth", and 100% assembly code.
It seems like a big part of all these strategies is making sure the checks for the optimizations (checking if they're possible, checking if they're done) don't take more time than the optimizations save.
Or could there be a way to alter the execution graph so that once you add in the optimization, you never have to check if it's there?
You can't really check that, you can only hope your heuristics are right. You don't know in advance how many times a method will be executed and thus how much optimization budget is worth it. If you boot up a java application that runs for months and handles tons of traffic then you could theoretically justify many minutes of CPU cycles for optimization.
And that's not all that makes JITs complex. Some also do speculative optimizations that require guards and deoptimization points so they can fallback and recompile if those assumptions are violated. If the language has a garbage collector then the GC and JITs have to cooperate for ideal performance.
One of the things V8 does is store "field dependencies" -- a list of optimized code attached to fields that is invalidated if that field is modified in a certain way. The optimized code is known to only access that field in a certain way, thus doesn't need to check it, so this only slows down unoptimized paths (and only on their slow paths too, since even unoptimized code has fast paths for known access patterns thanks to inline caches). Comes with a memory/generality cost though, so this isn't used for every type of check.
It's there though not very in depth c:
https://openjdk.java.net/jeps/310
https://www.eclipse.org/openj9/docs/xcodecachetotal/
https://docs.oracle.com/cd/E13188_01/jrockit/docs142/usergui...
https://source.android.com/devices/tech/dalvik/jit-compiler#...
Absolutely correct that LLVM is a fair amount slower than C1 or C2. Azul augmented our JITs with a compilation recording & replay mechanism to combat the general start-up problems posed by JITs (including Falcon).
For those who are curious, here's my presentation on the topic: https://2018.jpoint.ru/en/talks/63npsyjpokmukqsag80oia/.
(this is in the post~)
Interestingly in 30 years I have not once heard of a case where this theoretical benefit has manifested as a clear advantage in any real world application when looking at the system as a whole... amdahls law and all that.
You can always hand tune the 1-10% hotspots for reasonable cost most of the time, and even static tools can do PGO which generally gets you where JIT would anyway.
Today you make make a very direct empirical comparison to see this - using the Graal compiler. This lets you compile exactly the same Java code either ahead-of-time or just-in-time, but using the same compiler logic except for the runtime information available when running just-in-time. The just-in-time code is (ignoring startup and warmup time) in my experience always faster, due to the extra runtime information.
With PGO, I can get a more representative profiling dataset, allowing the JIT to see actual production loads instead of startup loads.
And for CLI apps, PGO code starts up fast and never slows down to profile or optimize.
Funny you should mention that - the author of this blog post has another post on fixing that problem for one specific (but very practical) case where we want to disregard some profiling information from the startup phase because it pollutes the genuine profiling information.
https://engineering.shopify.com/blogs/engineering/optimizing...
With the most common type of JITs, which profile once and compile once, I'm going to get code that is optimized for startup and initialization.
If I have an "advanced" JIT, which is constantly deoptimizing and reoptimizing for whatever it sees as the hottest path for some arbitrarily chosen snapshot of time, I'm going to see my compute-intensive code slowed down so that it can optimize and compile it every time that endpoint is called, but then subsequently deoptimized while it is sitting around waiting for something to do, ensuring that I have to go through the same process the next time it is called. You can actually see a lot of situations where this regime could be even worse than a naive startup-based single optimization, which is why it is actually not that common outside of dynamically typed languages.
With PGO, I can select a profile snapshot during a stress test, and get heavily optimized code specifically for the things that actually stress the server. And it will stay optimized for that use case.
Basically, it will do something like: interpret a function for a the first few thousand times it is executed, collecting execution metrics. After a threshold is reached, next time that function is called, start compiling it, optimizing based on the execution metrics collected earlier. Leave behind a few hooks for future changes. Keep collecting metrics from function execution. If the profile of execution changes significantly, re-compile the function according to the new profile (possibly doing things like un-inlining).
This is perfectly aligned with a startup vs normal production use workflow. The only problems can appear if you have a continually changing pattern of execution through the same function.
OpenJ9 and ART also have similar capabilities.
I don’t know, there are a lot of people who browser the web using Chrome…
Languages built with AOT compilation in mind (e.g. Rust or Nim) usually give you lots of ways make choices at compile time and give hints to the AOT compiler that the JIT compiler would instead try to infer at runtime in Java.
But by infering these things at runtime intead, maybe the JIT approach makes it easier to get fast code in those cases where you (as an application developer) don't want to put a lot of effort into optimization?
Most compilers for embedded systems have always offered that option, and in what concerns enterprise JVMs, JIT compilers have had the capability to cache JIT code and PGO data between runs.
Both options that have come now to OpenJDK, OpenJ9 and Graal.
Android also learned the hard way that changing to pure AOT did not achieve the performance improvements that they expected, while compilation on device achieved C++ compile times when it was time to update all apps, hence the multi-tier interpreter/JIT/AOT with PGO introduced in Android 7.
The main problem of AOT compilation with PGO, is that first of all one needs a good dataset so that the optimizations are in line with the actual behaviour in production, still doesn't work across dynamic libraries so optimizations like devirtualization are not possible, and most of the time the tooling is quite cumbersome to use.
Basically what I’m saying is that I’ve never seen any substantial rewrite of decent C++ code into Java perform better, even if jitting has benefits on a small scale, it’s not substantial enough to overcome other overheads in managed languages.
In reality it was a bit of a mixed bag.. and to some of us that remember the hype from 30 years ago it comes across as over promising and underdelivering.
That isn’t to say that the technology isn’t incredible, I don’t mean to dump on it. But overpromising is sort of the status quo for tech.
> The just-in-time code is (ignoring startup and warmup time) in my experience always faster, due to the extra runtime information.
I don't think that result is surprising. The issue is that in the real world you can't ignore startup and warm up times.
I've never heard the claim that JIT compiled code is slower than statically compiles code. The issue is that the extra costs associated with JIT don't outweigh its benefits.
Because JIT or AOT is just one little piece of the overall puzzle.
In practice, PGO has been the best possible compilation regime that I have ever found.
It's really workload dependent and depend a lot of the GC involved (a pretty dumb one like Python's or Go's won't get you anything performance wise), but a copying collector can achieve allocation way faster than a regular heap allocator (the allocation can be almost as cheap as allocating on the stack). If you can't avoid boxing and your objects aren't all long-lived, you can run circles around a program not using such a GC.
I get that it is theoretically possible for GC to be faster, but I literally have never seen it pan out in practice.
And whichever way you look at it, the GC doesn't really have to outperform manual memory management to be extremely useful. It just has to be close enough, the correctness guarantees alone make it worth it as long as the performance difference is not too large, in many domains, not to mention the productivity boost and program readability.
I agree with all of this. But it is a very different argument than the theoretical argument that garbage collection can be faster than manual memory management.
Rust, for example, is manually managed or compiler managed, depending on how you look at it. But its semantics are extremely crude and naive: allocate on creation, free once an object leaves its current scope. There is no optimization of heap fragmentation, there is no optimization of large bulk frees...the compiler literally just inserts the malloc/free statements for you in a static location that you don't get to choose.
And despite the crudeness of its memory allocation behavior, it runs circles around garbage collected languages all day long. Even fast ones...I have done more than a handful of comparisons between Scala, Java, Go, SML (MLTon), OCaml, F#, and Rust...and Rust always comes out on top. That doesn't mean the performance advantages are worth the extra pain of dealing with a borrow checker...for most of my code, I default to Scala for all the reasons you've mentioned. But I don't delude myself into thinking it is faster.
As a more concrete example splitting strings by copying in Rust and hammering malloc and memcpy is 4-5x slower than using slices in Go and letting the GC deal with keeping things alive.
You might say that's not a fair comparison but few businesses can tolerate the messing around that is writing zero copy Rust.
malloc implementations actually do optimize by delaying the work of free(1). They do a lot of complex stuff hidden behind those function calls to improve performance.
Most likely if you compare a Rust and Java program that both run a loop creating a million node linked list and then starting over, you'll see that the Java program is much faster. I'll actually try to do that and confirm, but I believe it should be the case.
Even if you were to allocate arrays (Vec) you may see the same.
But, of course, that is not a fair comparison. Rust gives you tools to avoid allocation in the first place. It also optimizes so many things that Java doesn't. Summing up all of the values in an ArrayList<Integer> in Java is going to be so much slower than doing the same in Rust it's not even funny. I'm not even sure that Java implements vectorization yet.
It would be very interesting to see what performance a Rust program would get with a good, concurrent parallel generational copying collector. Perhaps in a few years there will be some interest in that.
Most generational gc's don't call free (the ones in Java can, but not per object, the reason for doing it is for returning memory to the OS). The GC will scan every _living_ object, but only those it is interested in. So if the decision to be made is which newly allocated objects should be copied over to the old gen, the gc will avoid scanning objects known to already be old.
The sentence you wrote made it seem like it scans the entire heap and decides which object should be kept, which should be copied and which should be free'd, but this is far from the case.
Since allocation with a GC is usually much cheaper than in non-GC systems (bump allocator) and since free is rarely, if ever, called, you can in theory get better performance from a GC than in a system with manual memory management. Of course, it all depends on the system.
The systems I write (mostly CRUD web apps) benefit from it, because requests to my service allocate little and run pretty fast, they're unlikely to survive to the next GC, and so I mostly pay for bump-allocation (which is cheap).
However, while the performance might be better my systems are prone to unexpected pauses while the GC does run. That pause might be less than the time spent in free in a manual memory managed system, but of course saving up all that time and spending it in one place does make it more noticable.
Thankfully, Java's G1 and collectors have managed to reduce these pauses so they're no longer noticable for my use. Pauses are less than 100ms (usually much lower) which is about the same variation I get from calling a third-party http service.
> Pauses are less than 100ms (usually much lower) which is about the same variation I get from calling a third-party http service.
Note that a pause for calling a web service is different than a GC pause, because in the former you can do other useful things while you wait.
CPython has a specialized arena allocator for small allocations called obmalloc.
Go's allocator is descended from tcmalloc but faster because it doesn't need to support the free(1) api and all the book-keeping required.
It's like comparing speed of a bike vs airplane: the brand and the quality of the bike doesn't really matter…
Freelist based allocation is actually very nearly as fast as bump pointer allocation. Like 10% if you compare the allocation function in isolation and 1% if you benchmark the whole object allocation path.
http://users.cecs.anu.edu.au/~steveb/pubs/papers/mmtk-sigmet...
Some older malloc implementations like Hoard have bump pointer allocation into empty pages but the newest allocator impementations found that the branch prediction cost of having both paths outweighed the benefits
https://www.microsoft.com/en-us/research/uploads/prod/2019/0...
- first, as you said, people repeat the opposite a lot, including world class GC experts.
- then, unless I'm missing something, that claim sounds equivalent to claiming than heap allocation is no more than 10% more expensive than stack allocation, which is arguably completely false.
Even if they lose in micro-benchemarks championships, it hardly matters in most enterprise codebases.
You do see JITs winning in Java because Java's "everything is virtual" and "most for loop are interface calls to Iterator<T>" makes it very hard to statically compile efficiently.
Languages designed for static compilation generally consider virtual dispatch to have a user-visible cost and don't unilaterally make users paying it without them asking for it.
In a long enough time frame nearly everything is variable: over decades even computer architectures and language syntax change. In a short enough time frame nearly everything is constant: in a single cycle a von Neumann computer will only change a single memory location and all the others will have a constant value.
Even though an AOT compiler might have minutes or more to work on a code fragment, the code it generates has to work for a long time and on many different machines. A JIT might have milliseconds or less to work on the same code fragment but what it generates only needs to work on this exact machine and only for minutes or hours. In fact, it might even be wrong and have to be recompiled less than a second after the JIT produced it.
So the code generated by the AOT must treat as variable things that the JIT can pretend are constant (with hook to recompile if it proves not to be so).
This is slightly related to partial evaluation, which is a key idea in Graal.
In certain cases [1] JIT can beat AOT by a decent margin because it has access to live information that isn't available at compile time. In theory you could AOT compile, profile, and recompile but in practice my understanding is that nothing beats doing it live.
Consider that if the workload suddenly changes in production and your heuristic violates an invariant as a result, you can deoptimize, reprofile, and recompile everything on the fly.
But wait, you say! Can't an AOT compiler do that? But no, the state space is almost certainly going to be too large by many orders of magnitude. So unless your AOT compiler effectively inserts a JIT compiler ...
[1] Sorry, no examples to hand. Nobody knows but I'm actually a dog. Don't trust me!
- Dynamic method calls that get de-virtualized, because there is only one visible implementation, including across shared libraries
- Inlining across shared libraries
- Adaptation of new CPU opcodes, for example a Java application written in 2000 could in theory make use of AVX, without being recompiled.
- In the same vein, that is how shading languages work