JIT and GC — Getting Faster While Running, Cleaning Up While Running

A just-in-time compiler and a garbage collector are both services that have to work without stopping the application. Hot spot detection, tiered compilation, inlining, speculation and deoptimization, generational GC, tri-color marking and write barriers — built up from zero, ending where you can read a GC log and a JIT log yourself.

Remodelling the kitchen without closing

Picture a busy diner. Prepping every dish on the menu equally before opening is ahead-of-time compilation. Once service actually starts, though, you discover that eight out of ten orders are for three dishes.

A JIT (just-in-time) compiler rebuilds the line around those three dishes while the restaurant is open. A GC (garbage collector) clears plates and frees up tables without pausing service. Textbooks put them in separate chapters, but they share a predicament: neither is allowed to close the shop. So both end up being budgeting problems — when to intervene, and how much.

The information that isn't in the source code

As Compilers from scratch showed, a compiler gets to survey the whole program before emitting anything. Even so, some facts are out of reach:

• how many times each function will actually be called
• which side of an if is taken essentially every time
• how many distinct classes actually show up in a given variable
• whether an object ever escapes the function that made it

All of these depend on the input data, so no amount of re-reading the source will reveal them. A runtime compiler can measure them while the program runs — at the cost of having its own compilation time billed to the application's wall clock.

Hot spots — time is wildly uneven

Execution time is not spread evenly across methods. Even in an application with thousands of them, most CPU time lands in a handful of loops. That skew is the whole premise of a JIT. Whether a given method is worth compiling comes down to one inequality:

Here $n_i$ is how many more times the method will run, $c_i$ is what one interpreted run costs, $s$ is the speedup once compiled, and $K$ is the one-time price of compiling it. In words: compile it if the time you are about to save adds up to more than the compilation bill you pay now.

Of those quantities, only $n_i$ is cheap to observe at runtime. So the runtime keeps an invocation counter per method and queues anything that crosses a threshold. That is where the HotSpot JVM gets its name — it goes looking for the hot places.

Splitting it into tiers

A single threshold puts you in a bind. Set it low and the compile queue drags down startup; set it high and the code stays slow for ages. The answer was to add tiers. In HotSpot, level 0 is the interpreter, levels 1–3 are the C1 compiler, and level 4 is C2. C1 emits code quickly and optimizes conservatively; C2 takes its time and goes for the throat. Because the C1 code carries profiling instrumentation, by the time C2 gets its turn there are real statistics — "this branch goes one way 99% of the time" — to work from. V8 stacks its own tiers the same way: Ignition, Sparkplug, Maglev, TurboFan.

Counters alone still miss one shape: an enormous loop that is only entered once. The invocation counter sits at 1 forever. So the runtime also counts backward branches inside loops, and when the count crosses a threshold it swaps the running frame over to compiled code mid-loop. That is on-stack replacement (OSR).

Inlining is the parent of every other optimization

Inlining pastes the callee's body into the caller. It is usually described as saving the few nanoseconds a call costs, but the real payoff is what becomes possible afterwards. Constant folding, dead branch elimination, loop-invariant hoisting, and the escape analysis discussed below all start working across what used to be a function boundary.

Java methods are virtual by default, so the target isn't statically known. This is where the runtime profile earns its keep. If every receiver seen at a call site so far has been an ArrayList, the compiler can bet on that single class, guard the bet with one class check, and inline. One observed type is monomorphic; once three or more show up the site is megamorphic and the compiler gives up and falls back to an ordinary virtual call.

Expansion can't be unbounded, though. Inlining to depth $d$ with $b$ callees at each level grows code size roughly like $b^d$.