Interpreter Dispatch Overhead and the Cost That Justifies Compilation

A bytecode interpreter is a loop with a table lookup in the middle. The loop reads an opcode byte, jumps to the code that implements that opcode, performs the operation, and jumps back. Only the middle step touches the program’s data; everything around it is bookkeeping. On the common architectures the bookkeeping costs more than the arithmetic it enables, and the size of that overhead determines when it becomes worth generating machine code instead.

What One Bytecode Actually Costs

Consider the simplest possible instruction, adding two local integers. A compiled function on x86-64 might express it as a load, an add, and a store to a stack slot: three instructions, and an out-of-order core overlaps them with neighbouring work so the marginal cost can approach a fraction of a cycle. The same operation in a bytecode stream requires fetching the opcode byte at the instruction pointer, incrementing the instruction pointer, decoding the opcode, fetching the two operand indices from the bytecode stream, bounds-checking both against the frame’s local array, loading both values, adding, storing the result, and jumping back to the top of the loop.

The dominant cost is not any single one of those steps but the indirect branch at the end. A switch-based interpreter compiles to a jump through a table, and the target depends on the data being interpreted. Branch predictors handle indirect branches by memorizing recent target history; a repetitive bytecode sequence lets the predictor learn, but real programs alternate between opcodes often enough that it misses. A mispredicted indirect branch costs roughly fifteen to twenty cycles on current server cores, since the pipeline must be flushed and refetched. Two mispredicts per bytecode is enough to put an interpreter an order of magnitude behind compiled code on an arithmetic-heavy loop, and that ratio, rather than any absolute figure, is the thing to hold onto.

A second, quieter cost is that the interpreter’s state lives in memory rather than in registers. The instruction pointer, the frame pointer, the operand stack pointer, and the dispatch target all occupy slots the target compiler cannot keep in registers, because the dispatch code is shared across every bytecode and cannot assume which registers are free. Each bytecode therefore starts and ends with loads and stores that a compiled version of the same code would have eliminated.

Switch Dispatch, Token Threading, and Direct Threading

Three implementation strategies differ in how much of that overhead they leave in place.

A switch dispatcher is a single loop containing a switch on the opcode. It is portable C, easy to debug, and produces one indirect branch per instruction whose target comes from a jump table the compiler emits. Because the loop has one entry point, the dispatch stays compact, but the compiler must spill and reload interpreter state across the switch, and it cannot specialize the tail of each case against the instruction that follows.

Token threading replaces the opcode with an index into a table of handler addresses, so dispatch becomes a load followed by an indirect jump or call. Direct threading stores the handler address itself in the instruction stream, making dispatch a single indirect jump with no table lookup. The stream is no longer portable because it contains raw pointers, which is why direct threading is normally applied to an internal representation built at load time rather than to the on-disk format.

Subroutine threading emits a call to a handler routine per bytecode. It is the slowest of the three, because each handler pays a call and return on top of the dispatch, and the return-address stack gives the predictor less to work with than a direct jump does.

The differences are large enough to matter. Published studies of interpreter design have repeatedly found direct threading ahead of switch dispatch on the same bytecode semantics, with the gap narrowing when the switch version compiles to a jump table rather than a chain of comparisons. The relevant point for compilation policy is that the interpreter’s overhead is not a constant: a well-built interpreter narrows the gap and a poorly built one widens it, so the threshold at which compiling pays off moves with the interpreter’s quality.

/* Switch dispatch: one indirect branch per instruction, target from a jump table. */
for (;;) {
    uint8_t op = code[pc++];
    switch (op) {
    case OP_LOADK:  push(constants[code[pc++]]); break;
    case OP_ADD: {
        Value b = pop(), a = pop();
        push(add(a, b));            /* may allocate or take a slow path */
        break;
    }
    case OP_JUMP:   pc += (int16_t)(code[pc] | code[pc + 1] << 8); break;
    case OP_RETURN: return pop();
    }
}

That loop is the cost model of an interpreter in miniature. pc is stored and reloaded every iteration, the code array is re-indexed every iteration, and the switch compiles to a bounds check plus a jump through a table. A compiled version of the same three operations would keep both operands in registers across the whole sequence.

The Break-Even Point Is a Ratio, Not a Count

Compiling a function costs time proportional to its size and to the optimization applied. Running compiled code instead of interpreted code saves an amount per execution proportional to the difference in per-instruction cost times the number of instructions executed. The two quantities cross at some execution count, and a runtime’s hotness threshold is an approximation of that crossing.

The arithmetic is easy to state and hard to pin down. A function of a few hundred bytecodes might take on the order of tens of microseconds to compile with a simple register-allocating backend, while a loop body inside it might save a few nanoseconds per iteration. Those figures are deliberately loose because they depend on the machine, the compiler, and the code, but the ratio they imply lands in the range of thousands of iterations before the compile cost is repaid. That is why thresholds in adaptive runtimes are expressed in invocation and loop-back-edge counts in the thousands rather than the dozens, and why a single threshold fits neither a long-running server process nor a short-lived command-line tool.

A second consideration pushes the threshold up: compilation competes for the same cores as the program. A runtime that compiles on a background thread hides the latency but not the CPU time, and on a machine already saturated the compile work delays the interpreted execution it is meant to accelerate. Some runtimes cap concurrent compilation and queue requests rather than compiling everything that crosses the threshold.

A lower bound comes from code quality. A baseline compiler that maps bytecodes to machine instructions nearly one-for-one still removes dispatch and keeps values in registers, and it can be cheap enough to compile that the break-even count is small. An optimizing compiler that builds a full intermediate representation, inlines, and allocates registers costs far more per function and needs a much hotter function to justify itself. The natural response is not one threshold but several, which is the subject of tiered compilation and on-stack replacement.

Where the Model Breaks

The dispatch-cost argument assumes the interpreter executes each bytecode separately and that compiled code executes the equivalent operations without that separation. Both assumptions fail in useful ways.

Interpreters can fuse common bytecode pairs into superinstructions, either by rewriting the stream at load time or by adding combined handlers to the dispatch table. A fused load-and-add handler pays one dispatch for two operations, lowering per-operation overhead with no compilation at all. The gain is bounded by how often the pair occurs, and the fused handler set has to be chosen from measured instruction frequencies, which is a profiling problem in itself.

Compiled code can also lose the advantage it gained. A JIT that specializes aggressively inserts guards, and every guard is a conditional branch the predictor must handle. Code with many guards can approach the branch density of an interpreter, though the branches are direct and usually predictable rather than indirect and unpredictable, so the cost per miss is lower. Guard placement and code layout therefore matter as much as the optimizations the guards protect, which is why speculative inlining treats the guard budget as a first-class resource.

The interpreter is not uniformly slower in wall-clock terms either. Startup is dominated by loading, verification, and first executions, all of which the interpreter handles without the fixed cost of code generation. A program that runs for a few milliseconds finishes sooner under an interpreter than under a runtime that compiles eagerly, which is why compiling everything at load is a poor default for interactive tools even when the same code would benefit from compilation after a minute of execution.

The measurement that decides policy is the distribution of execution counts across functions, and in most programs that distribution is sharply skewed: a small fraction of functions accounts for most of the executed bytecodes. Locating that fraction is the job of the counters described in hot code detection.