Escaping the Giant Switch

a true story about bytecode interpreters

Last year, Thomas, bearer of the One Graal, came to us with a prompt:

「 /goal make the GraalPy interpreter faster than CPython 」

To understand what Thomas was asking, it helps to know what the two interpreters are made of. The GraalPy interpreter is written in Java. CPython’s is written in C. So the real assignment was to make a Java interpreter outrun a C one, without giving up the high-level Java programming model.

The good news was that we controlled the compiler.

The bad news was that we controlled the compiler.

There are very few hard limits when you own the entire stack. There are also very few excuses.

If the branch predictor was unhappy, that was our problem.

If the register allocator was unhappy, that was our problem.

So we started looking for something dangerous to optimize.

The Giant Switch

The most obvious suspect was the interpreter dispatch loop. To keep the discussion concrete, let us start with a tiny program:

static int plus1(int x) {
    return x + 1;
}

On a stack-based virtual machine, this could be compiled into a bytecode sequence like:

iload_0
iconst_1
iadd
ireturn

Even if you have never looked at Java bytecode before, the instructions are fairly self-explanatory: load the first local variable (which happens to be the method parameter in this example), push the constant 1, add the two values, and return the result.

One natural way to implement such a bytecode interpreter is a large dispatch loop:

while (true) {
    int opcode = bytecodes[pc];
    switch (opcode) {
        case ILOAD_0:
            stack[sp++] = locals[0];
            pc++;
            break;
        case ICONST_1:
            stack[sp++] = 1;
            pc++;
            break;
       case IADD:
            int b = stack[--sp];
            int a = stack[--sp];
            stack[sp++] = a + b;
            pc++;
            break;
       case IRETURN:
            return stack[--sp];
       // imagine a few hundred more friends here
    }
}

Before continuing, it is worth acknowledging that this is not the only way to implement a bytecode interpreter. HotSpot’s template interpreter, for example, is famously efficient. Rather than relying on a giant switch loop, it generates platform-specific native code for executing bytecodes.

That option is powerful, but it also moves the burden onto handwritten or explicitly generated low-level machinery. Our challenge was different: keep the interpreter expressed through Java objects and methods, while still giving the compiler enough information to recover some of the same efficiencies automatically.

The real dispatch loop was, of course, much larger than this toy example, with hundreds of bytecode handlers.

Still, the execution pattern remains the same: every bytecode handler eventually returns to the same dispatch loop, which fetches the next opcode and jumps to the corresponding handler.

This architecture has many virtues. It is well understood, easy to maintain, and surprisingly effective. It also has a tendency to accumulate state. The program counter lives there. The operand stack lives there. The local variables live there. Profiling information lives there. Before long, every piece of interpreter state is flowing through the same compilation unit.

That last detail would eventually matter a great deal.

For now, all we saw was a giant switch sitting in the middle of one of our hottest execution paths.

Naturally, we blamed it for the performance gap.

Take I: Thread the Switch

The first theory was branch prediction.

At the end of each non-terminating bytecode handler, control returns to the switch. The interpreter reads the next opcode and uses the same dispatch branch to select the next handler. So every transition in our plus1 example passes through the same machine-code branch.

Modern processors do not wait politely for every branch to resolve. They speculate. The processor predicts where a branch will go and starts executing along that path before the branch has actually completed.

When the prediction is correct, much of that work is effectively free. When the prediction is wrong, the speculative work is discarded and execution restarts from the correct target. Ideally, the processor would learn that after iload_0 comes iconst_1, after iconst_1 comes iadd, and after iadd comes ireturn.

Unfortunately, the predictor does not see bytecodes. It sees machine instructions.

From the processor’s perspective, all of these transitions originate from the same dispatch branch.

To build some intuition, imagine that each branch instruction is a signpost. Whenever the branch resolves, the signpost turns to point toward the destination it just took. The next time execution reaches that signpost, the processor speculates by following its current direction. Under this simple model, the shared dispatch signpost will mispredict every transition in our example.

Real branch predictors use considerably richer history, but each time the branch executes, the predictor must still choose one specific target and begin speculating along that path.

This is the classic motivation behind threaded dispatch. The trick is to duplicate the signposts.

The bytecode sequence stays the same, but each handler gets its own copy of the dispatch branch at a different machine-code location.

The obvious question is how to generate such a layout. Fortunately, the replay itself is surprisingly straightforward.

We expose this through a feature of the Truffle Bytecode DSL. The dispatch sequence is marked for special treatment:

while (true) {
    int opcode = bytecodes[pc];
    switch (markThreadedSwitch(opcode)) {
        // ...
    }
}

Because we control the compiler, that marker can trigger a late code-generation step. During code generation, we record the machine code for the dispatch path, from the loop header through the table jump generated for the switch. At the very end of compilation, the compiler replaces each interpreter backedge with a copy of those exact machine-code bytes.

No re-optimization is required. No new register allocation is required.

As a result, all registers, memory operands, and addressing modes remain exactly as they were in the original dispatch sequence. The important difference is that the branch instruction is no longer shared by every bytecode transition.

Some patching is still required. Branches leaving the copied region, metadata references, and other bookkeeping details need to be adjusted. These details matter, but they do not change the basic idea: copy the generated dispatch path to each backedge.

One unpredictable dispatch branch becomes many more predictable ones.

That was the theory, at least.

The Rabbit Hole

As expected, threaded dispatch helped, but the magnitude never felt right.

Honestly, I never really bought branch prediction as the whole story.

So we opened the intermediate representation our compiler emits.

As compiler engineers, this is usually the point where we hope to find a small, local mistake instead of a new research project.

Fortunately, there was one.

The shared dispatch loop header was carrying around a surprising amount of register pressure.

To understand why this matters, imagine an interpreter that keeps enough state live to exceed the number of available registers. On x86–64, that is not as difficult as it sounds. Despite decades of progress elsewhere in computing, most of us are still developing on machines with 16 general-purpose registers. Intel APX promises relief, but it has yet to appear on the machines that generate our management update charts.

Eventually, some values must be spilled to memory. In our case, the scheduling heuristics had a tendency to pull interpreter states into the shared dispatch loop header.

The unfortunate part is that many of those states were not needed by every bytecode handler. An interpreter state that was only relevant to a handful of bytecodes could still compete for registers in the shared dispatch path executed by all of them. The more registers a handler needed locally, the fewer good choices remained for values live around the shared loop header.

A straightforward mitigation was to tweak the heuristics so fewer interpreter states were scheduled into the loop header.

This did not make register pressure disappear. It changed where the cost was paid. An interpreter state needed by one handler should ideally compete for registers in that handler, not in the shared dispatch path executed by every bytecode. That is a much better trade-off.

Ordinarily, increasing code size would be a concern.

At this point we were already duplicating the dispatch loop onto every interpreter backedge. Worrying about a few more instructions felt somewhat academic.

The optimization worked, surprisingly well.

Unfortunately, this was also where we fell into the rabbit hole.

We had reduced the cost of the shared dispatch path, but the compiler was still fundamentally reasoning about the same enormous program.

A giant switch had become a giant compilation unit. A giant compilation unit had become a giant live-range problem.

Values from unrelated bytecode handlers were still competing for the same limited register budget. For an interpreter, not all values are equal. Spilling a rarely used handler-local temporary is annoying. Spilling the program counter, the stack pointer, the bytecode array, or frequently accessed frame state can add memory traffic to almost every bytecode transition.

While a register allocator can often find excellent solutions, it cannot exhaustively explore the optimization space of a large compilation unit in a reasonable amount of time.

It must therefore make more heuristic decisions, and heuristic decisions inevitably leave some performance on the table.

Register allocation was only where the problem first became obvious. The same shape affected every optimization that had to reason about the interpreter as one enormous body.

We could keep tuning heuristics and teaching the compiler new tricks.

Or we could ask a more uncomfortable question.

Why was the entire interpreter being optimized as one giant compilation unit in the first place?

Take II: Escape the Giant Switch

Once we framed the problem as a giant compilation unit, the obvious solution seemed equally obvious.

Split it.

After all, compilers already know how to compile multiple methods independently. Why force the entire interpreter through one enormous optimization problem?

In fact, there is a remarkably straightforward way to do exactly that. Every bytecode handler can simply become its own method:

@DontInline
static void iload0(...) { ... }
@DontInline
static void iconst1(...) { ... }
@DontInline
static void iadd(...) { ... }

Now every handler is compiled independently. The giant compilation unit disappears. The giant live-range problem disappears. The register allocator can focus on one bytecode handler at a time.

The problem is gone. Unfortunately, so is most of the performance.

The issue is that compilation boundaries are not free.

For an interpreter, there is quite a lot of state to carry around. The bytecode stream. The program counter. The operand stack. The stack pointer. Profiling information. Exception state. Various pieces of bookkeeping accumulated over years of evolution.

Inside a single compilation unit, many of these values can remain virtual. The compiler is free to keep them in registers and move them around as it sees fit.

Across a method boundary, that illusion breaks down: values must cross a calling convention, and virtual state may need to be materialized.

In a language like Java, primitive interpreter state is particularly awkward. One option is to store everything in an object and pass that object from handler to handler. The register allocator will certainly appreciate the smaller compilation units.

The memory subsystem, less so.

We would have traded a register allocation problem for a memory traffic problem. What we really wanted was something contradictory.

We wanted each bytecode handler to be compiled independently, as if it were its own compilation unit.

At the same time, we wanted interpreter state to flow between handlers as if no compilation boundary existed at all.

In other words, we wanted optimization across compilation units.

Normally, those words do not belong in the same sentence.

The Valhalla-Shaped Trick

The obvious question was how to move interpreter state across compilation boundaries without sacrificing the optimization opportunities we had just fought so hard to recover.

The idea itself was not entirely new.

Project Valhalla had already spent years exploring a similar observation: programmers like objects, but compilers often prefer their contents.

Consider our running example:

class State {
    int pc;
    int sp;
}
static void iadd(State state, int[] stack) {
    int b = stack[state.sp--];
    int a = stack[state.sp--];
    stack[++state.sp] = a + b;
    state.pc++;
}

From the interpreter author’s perspective, this is exactly what it should be: a small mutable object carrying interpreter state from one bytecode handler to the next. From the compiler’s perspective, however, the interesting part is rarely the object itself. The interesting part is the values it contains.

Conceptually, instead of reasoning about State state, the compiler would much rather reason about <pc, sp>.

So we took the idea and developed it further for interpreter state. Rather than passing interpreter objects across compilation boundaries, we expand selected fields into a tuple of values. Together with the existing handler arguments, that gives the compiler the boundary tuple it actually wants to optimize. To preserve the original programming model, the compiler leaves the original handler signature unchanged and synthesizes a small stub:

static void __stub_iadd(int pc, int sp, int[] stack) {
    State state = new State(pc, sp);  // To be virtualized
    iadd(state, stack);               // To be inlined
}

After inlining, escape analysis can often remove the reconstructed state object from the optimized representation and replace its fields with compiler values. Even when it cannot do so globally, Graal’s control-flow-aware Partial Escape Analysis can apply the same optimization on the fast path where object materialization is unnecessary.

Expanding interpreter state into a tuple solves only half of the problem. The tuple still needs to come back, but Java methods are much happier accepting many inputs than returning many outputs. So the generated stub grows a tuple return value:

// Pseudo-Java
static <int, int, int[]> __stub_iadd(int pc, int sp, int[] stack) {
    State state = new State(pc, sp);  // To be virtualized
    iadd(state, stack);               // To be inlined
    return <state.pc, state.sp, stack>
}

At first glance, this may look like constructing and returning a tuple object. The important detail is where the updated values land. The generated calling convention returns the tuple through the same locations that carried it in. If pc enters the stub in one register, the updated pc' comes back in that same register. The caller-side write-back can then be inserted mechanically:

// Pseudo-Java
<pc', sp', stack> =
    __stub_iadd(state.pc, state.sp, stack);
state.pc = pc';
state.sp = sp';

Interpreter state now follows a round trip:

The state objects preserve the Java programming model on both sides of the boundary. Interpreter authors keep working with objects, fields, and ordinary method signatures, while the compiler uses the tuple to carry selected state between compilations as register values.

Escape analysis also runs independently in the caller, which may keep the original state object virtual.

The write-back itself does not necessarily become memory traffic. If both state objects remain virtual, the updated values may continue flowing as compiler values throughout the entire round trip. In practice, this gives us much of what we wanted from escape analysis across compilation boundaries, without requiring the two compilations to become one.

The register allocator offers another perspective. Previously, the dispatch loop and all bytecode handlers formed one enormous register-allocation problem. Now the caller and each handler are allocated independently, with fixed argument locations connecting them into one continuous execution.

The Hidden Boundary Tax

There are still some limits to what this interface can express. In principle, we could carry every interpreter state across the call boundary. In practice, we must reserve part of the register budget for each handler’s local work. Even a simple bytecode such as iadd needs scratch registers for its local calculation, so the boundary tuple cannot occupy every useful register.

In the old giant compilation unit, an unselected value could still be visible to the inlined handler body and remain register-resident through scalar replacement. After outlining, a value that is not part of the boundary tuple is no longer carried into the handler as a compiler value. If the handler needs it, it must recover the value from materialized interpreter state through an ordinary memory access.

Usually this is still acceptable. We can select the most important states, and leave statistically negligible state to be recovered from memory when a handler actually needs it.

The more unavoidable issue is the call itself.

Besides ordinary call mechanics such as return-address bookkeeping and frame setup, a managed runtime like Native Image has to emit safepoint metadata for the call, describing where live references are. Unlike non-call operations, calls force the compiler to treat the callee as a black box. Live references residing in registers may be clobbered during the call, even if our special calling convention restores them once the call returns. That means the references need a GC-visible home, which often means a stack slot.

The outlined call boundary therefore turns part of the original register-pressure problem into a backup-and-restore problem around the stub call.

Yet the call also gives us the clue for escaping that cost. When the handler returns, the updated tuple already occupies the locations where the next handler expects its inputs. At that point, the obvious question is no longer just how to make the call cheaper. Why are we returning to the caller at all?

Thread the Calls

The answer, of course, is that we do not.

Instead, each handler stub performs the dispatch itself. This optimization is often called tail call threading. After executing the bytecode implementation, it fetches the next opcode, looks up the corresponding handler stub, and jumps directly to it. The bytecode stream therefore becomes a first-class part of the handler interface, extending the tuple to <pc, sp, stack, bytecodes>.

The generated code now looks roughly like this:

// Pseudo-Java
static <int, int, int[], short[]>
__stub_iadd(int pc, int sp, int[] stack, short[] bytecodes) {
    State state = new State(pc, sp);  // To be virtualized
    iadd(state, stack);               // To be inlined
    int nextOpcode = bytecodes[state.pc];
    jump handlerTable[nextOpcode]
        with <state.pc, state.sp, stack, bytecodes>
}

The specialized calling convention makes this natural: the jump requires no reshuffling and transfers the current interpreter state directly.

Viewed from a distance, the handlers resemble LEGO bricks: the shared tuple interface forms the studs that let them snap directly together.

The dispatch loop still exists. It simply stops getting invited to every bytecode.

The Benchmark Everybody Came For

At this point, we should probably return to the benchmark that drove this whole adventure.

To recap, the first suspect was branch prediction in the dispatch loop, and we threaded the switch to attack it. The spill came later; we tuned the scheduling heuristic and pushed the spill cost into individual handlers. Eventually, the compilation unit itself became suspicious. We outlined the handlers, then threaded the tail-call between them.

The final, threaded-tail-call configuration is GraalVM 25.1 as released. The other configurations use that same release with the relevant optimizations selectively disabled, allowing us to reconstruct each stage of the journey. All measurements are interpreter-only, with GraalPy’s JIT compilation disabled.

We selected a few arithmetic-heavy benchmarks that are representative of the interpreter optimizations discussed above. Other workloads are dominated by different costs, such as guest-language calls or attribute access, and therefore depend more heavily on the implementation of the Python runtime itself.

bytecode-benchmark fits the story most clearly. The baseline starts below CPython. Threading the switch brings it to roughly parity, and tuning the scheduling pushes it ahead.

Then we got greedy. To thread execution directly from one handler to the next, we first outlined the handlers into separate compilation units, and hit the boundary tax. The handlers were smaller, but every call was surrounded by bookkeeping memory accesses.

Tail-call threading is what makes that structure pay. Once the updated tuple can flow directly from one handler to the next through the specialized calling convention, bytecode-benchmark moves comfortably ahead of CPython.

arith-binop and sieve start from stronger baselines but follow the same broad progression.

Overall, the benchmark result is not simply that threading wins. It is more specific: threading makes the handler boundary cheap enough that outlining stops being structurally fatal.

That leaves a more interesting question. If the compilation boundary between caller and handler no longer has to be an optimization boundary, what about the boundary between one handler and the next?

“One More Thing”

The most frequently accessed values in a stack interpreter are, unsurprisingly, the values at the top of the stack. A typical arithmetic bytecode may load values from the operand stack, perform an operation, and immediately push the result back. Even after escaping the giant switch, these stack accesses remained firmly on the hot path.

This is not a new observation. Top-of-stack caching is a well-established interpreter optimization. The question was how to make it expressible in ordinary Java code while still giving the compiler a register-level representation to optimize. The answer, again, was the tuple.

By this point, interpreter state was already flowing between handlers as a tuple of register-resident values. Nothing limited that tuple to the existing interpreter state, such as the program counter or stack pointer: it could also carry recent operand-stack values, keeping them in registers across handler boundaries.

Conceptually, the handler tuple grows from <pc, sp, stack, bytecodes> to <pc, sp, stack, bytecodes, tos1, tos2, tosDepth>.

Here tosDepth says how many cached values are currently valid. When tosDepth is 1, tos1 is the current top of stack. When tosDepth is 2, tos2 is the current top of stack, while tos1 is the value beneath it.

At this point, some readers may be counting registers and becoming increasingly uncomfortable. Under a conventional calling convention, they would be right. Sooner or later additional arguments would spill onto the stack, undoing much of the benefit we were trying to achieve.

Fortunately, we control the compiler.

Nothing requires us to stop at the six integer argument registers provided by the platform ABI. Handler stubs never cross a language boundary, so we are free to employ a considerably more adventurous calling convention and use essentially the entire allocatable register file for interpreter state. The tuple may be growing, but it is still very much intended to stay in registers.

In our running example, iload_0 pushes the local value into tos1. Then iconst_1 pushes the constant into tos2. Finally, iadd consumes tos2 and tos1, then leaves the result in tos1.

The important part is not merely that tos1 and tos2 avoid memory accesses inside one handler. The value loaded by iload_0 remains in a register across iconst_1 and into iadd, without ever touching the operand stack.

No stack loads.

No stack stores.

At least not immediately.

Of course, reality is slightly less convenient. Two registers can only hold two stack values. Sooner or later a bytecode sequence will push a third value, then a fourth, and eventually the cache must spill into the backing operand stack. Likewise, some handlers may need to materialize cached values before interacting with code that expects the operand stack to reside in memory. The interpreter therefore carries tosDepth as part of its state and lets individual handlers decide when values should remain in registers and when they must be synchronized with the backing stack array.

Without further help, every push and pop now has to account for all possible cache states. A push is no longer simply stack[++sp] = value;. It starts to look more like:

switch (tosDepth) {
    case 0:
        tos1 = value;
        tosDepth = 1;
        break;
    case 1:
        tos2 = value;
        tosDepth = 2;
        break;
    case 2:
        stack[++sp] = tos1;
        tos1 = tos2;
        tos2 = value;
        break;
}

A pop has the same problem in reverse.

After spending several sections moving interpreter state into registers, we had accidentally introduced a new runtime state machine.

The (Compile-) Time (State) Machine

If tosDepth merely describes the shape of the cached stack, perhaps it should not travel in the tuple at all. Instead, we could turn the runtime state machine into a compile-time one, sending that decision backward in time from every bytecode execution to handler generation.

Consider iadd written in the most boring possible way:

static void iadd(...) {
    int b = stack.pop();
    int a = stack.pop();
    stack.push(a + b);
    state.pc++;
}

Without specialization, each pop and push must inspect tosDepth at runtime, as in the push example above.

Instead of generating a single handler that must reason about every possible cache state, we generate multiple handler variants. Each variant gets assigned a constant tosDepth, which is enough for ordinary compiler optimizations to fold away the irrelevant arms of push and pop. After those branches disappear, the updated tosDepth often becomes deterministic as well. Dispatch can then use that value to choose the next variant.

Returning to our LEGO example, imagine that each bytecode brick now bundles several handler variants, one for each possible incoming tosDepth. We stack these composite bricks vertically, and the tosDepth produced by one handler selects the path into the next.

The state machine still exists, but it no longer lives as control flow inside every handler. It lives in the transitions between handler variants.

Now consider the iadd<2> specialization. The compiler knows that both operands already reside in registers. The first pop becomes int b = tos2;. The second pop becomes int a = tos1;. And the push becomes tos1 = a + b;.

After constant folding and dead-code elimination, the handler is essentially reduced to tos1 = tos1 + tos2;.

Consequently, tosDepth no longer needs to occupy a runtime slot in the tuple.

The columns are not runtime branches; they are separately generated handler variants. The highlighted path follows iload_0<0> to iconst_1<1>, then iadd<2> and ireturn<1>. Each handler’s output cache shape determines the next variant, so neither a runtime tosDepth value nor a test of it appears along the path.

We traded runtime state transit for instruction bytes: multiple handler variants eliminate a runtime value and its control flow, freeing a register for actual interpreter state. The previous sections taught the interpreter how to carry state efficiently across compilation boundaries. This section taught it that some state never needed to travel in the first place.

The remaining concern is register pressure. For the mechanism to work well, the handler interface needs enough registers to carry two or more cached top-of-stack values in addition to the existing interpreter state. That is already a tight budget. GraalPy’s tail-call-threaded handlers pass a fairly heavy argument tuple today, and adding more top-of-stack values can exhaust registers and push other state back to memory.

The situation is even trickier because the Python stack can hold both primitive values and object references. Those may need special treatment, or even separate cached top-of-stack values, which would make the interface wider again. At that point, the optimization starts fighting the same register-pressure problem it was meant to avoid.

We are still exploring ways to mitigate this register cost, or at least warn interpreter authors when the handler interface becomes too wide.

Take III: ?

This article started with a giant switch.

The giant switch led to a spill.

The spill led to a giant compilation unit.

And the giant compilation unit turned out to be hiding far more than a few misplaced registers.

We first threaded the switch, giving each bytecode handler its own dispatch branch. We then tuned scheduling so handler-local state spilled only where necessary, rather than across the entire dispatch loop. Finally, we outlined the handlers into separate compilation units and connected them through a specialized tail-call convention. Interpreter state crosses those compilation boundaries as a tuple of values in fixed register locations, allowing the handlers to remain separate compilation units without turning their boundaries into optimization boundaries.

The threaded-handler implementation shipped in GraalVM 25.1.3 and is enabled by default in GraalPy. On the interpreter-only, arithmetic-heavy workloads shown above, it takes bytecode-benchmark from below CPython to comfortably above it, while arith-binop reaches roughly three times CPython.

This does not make every Python workload three times faster. Calls, attribute access, and other runtime operations are dominated by different parts of the GraalPy implementation. Even within the handler interface, registers remain a finite resource: carrying more interpreter state eventually risks pushing existing values back to memory.

That is also where the next experiment begins. If compilation boundaries no longer prevent values from remaining visible to the optimizer, the same interface can carry cached operand-stack values directly from one handler to the next. The mechanism works; finding the right register budget is still ongoing work.

For now, the giant switch is gone.

Until the next rabbit hole.