Computed Goto and Direct Threading in Bytecode Interpreters

An interpreter executes a loop with one iteration per bytecode instruction. Between two instructions it must do four things: read the opcode, find the handler for it, transfer control there, and then return to the top of the loop. The first and last are unavoidable. The middle two are overhead, and on modern out-of-order processors they cost more than the arithmetic most bytecodes perform. A single iadd handler may do one machine addition and then spend an indirect branch plus a return on getting to the next one.

The design of that transfer is therefore not a detail. It decides whether the processor’s branch predictor can learn the sequence of handlers, and whether the instruction cache sees a small hot loop or a sprawling switch body.

The switch loop and its indirect branch

The straightforward implementation puts every opcode’s code in a switch statement inside a for loop. The compiler turns the switch into a jump table or a chain of comparisons, and each case ends by breaking back to the loop header, which re-reads the opcode and re-enters the switch. The load_u32 used for the jump operand is the alignment-safe helper shown further down, which reads the immediate in the host’s byte order.

while (pc < end) {
    switch (*pc++) {
    case OP_PUSH: stack[++sp] = *pc++; break;
    case OP_ADD:  sp--; stack[sp] += stack[sp + 1]; break;
    case OP_JMP:  pc = code + load_u32(pc); break;
    default:      return OP_INVALID;
    }
}

Two costs are structural here. First, there is one indirect branch per instruction, taken through the switch’s dispatch table. Indirect branches are harder to predict than conditional ones, and a predictor that sees a rotating set of targets struggles. Second, every case exits through the same loop header, so the branch at the bottom of the switch is a single site with a single successor. That sounds good for prediction, but it means the loop’s back edge and the dispatch jump are both hot, and the front end has to keep the whole switch body resident.

Compilers can duplicate the dispatch into each case, a transformation sometimes called loop unrolling of the dispatcher or, when applied to the tail, replication of the dispatch. With that, each case ends with its own indirect jump, so a case that is always followed by the same case can be predicted as a correlated pair by a modern predictor. Whether a compiler performs this transformation varies, and it interacts badly with code size: replicating a 256-way switch inflates the text section substantially.

One indirect branch per instruction, with a label table

Computed goto removes the return-to-header step. The interpreter builds an array of handler addresses at startup, indexed by opcode, and each handler ends by jumping through that array using the next opcode byte. GCC and Clang expose this through the labels-as-values extension, which lets a program take the address of a label and store it in a void * or a function-pointer-sized variable.

#include <stdint.h>
#include <string.h>

static void *dispatch[256];
static uint8_t *pc;         /* instruction pointer */
static Value   *stack;
static uint32_t sp;

static uint32_t load_u32(const uint8_t *p)
{
    uint32_t v;
    memcpy(&v, p, sizeof v);   /* avoids alignment and aliasing issues */
    return v;
}

#define NEXT do { goto *dispatch[*pc++]; } while (0)

static void run(uint8_t *code)
{
    pc = code;
    NEXT;
do_push:
    stack[++sp] = *pc++;
    NEXT;
do_add:
    sp--;
    stack[sp] += stack[sp + 1];
    NEXT;
do_jmp:
    pc = code + load_u32(pc);
    NEXT;
}

The table is filled at startup with dispatch[OP_PUSH] = &&do_push; and so on, using the same labels-as-values extension.

Each handler now ends with an indirect jump whose target is read from the same array. That is still one indirect branch per instruction, but the branch site is now per-handler rather than per-loop, so the predictor can learn handler-to-handler transitions instead of a single site with hundreds of targets. Ertl and Gregg compared dispatch techniques across several interpreters and reported that the choice changes total run time on its own, before any change to the handlers, with the difference widest for interpreters whose opcodes do little work between dispatches.

The technique is not portable. Labels-as-values is a GNU extension, adopted by Clang and a few other compilers, and the C standard has no equivalent. The alternative standardized mechanism, switch on a value, cannot express “jump to the address stored here”. An interpreter that must compile on a compiler without the extension has to keep a portable path, which is why many bytecode engines carry two dispatch implementations selected at build time.

Threading: moving the next opcode into the handler

Direct threading is the name for the arrangement above, where the code array holds opcodes and each handler jumps to the next handler through a table. The term dates to Bell’s 1973 description of threaded code, in which the code stream is a sequence of addresses of small routines rather than a sequence of calls to them.

Two variants matter. In indirect threading the code array holds pointers to the handler code itself, so the interpreter does not need a separate dispatch table; the next instruction is the pointer read from the code array. This eliminates one memory indirection but makes the code stream four or eight bytes per opcode, and it makes the bytecode non-portable because it contains host addresses. In subroutine threading the code array holds addresses of small machine-code routines and each routine returns to a central loop; that is essentially the switch design with the switch replaced by a return.

Direct threading in the narrower sense keeps the bytecode portable: the stream is bytes, and the table lookup translates opcode to address. That lookup is one dependent load, and the load’s latency sits on the critical path between two instructions. Some interpreters reduce it by storing, for each opcode, a small record containing both the handler address and a precomputed operand size, so the handler and the length arrive in one cache line.

Inline caching and superinstructions change the economics

Dispatch overhead is proportional to the number of dispatched instructions, so every mechanism that removes a dispatch is worth more than making a dispatch faster. Superinstructions fuse common opcode pairs into a single bytecode with a single dispatch; a sequence such as load-local, load-constant, add becomes one instruction with one handler. The handler executes the same work, but the loop pays one dispatch instead of three. The fused opcodes can be generated ahead of time by the bytecode compiler for a fixed set of patterns, or discovered at run time by counting adjacent pairs and rewriting the code array.

Quickening is the related trick of replacing a general opcode with a specialized one after the first execution, so the second execution takes a shorter path. A load-global instruction that must check a dictionary on first use can be rewritten in place to a load-from-slot instruction that assumes the layout has not changed, with an invalidation path if it does. This is a form of self-modifying bytecode, and it requires the code array to be writable, which rules out sharing a single code array between threads unless the rewrite is done per-thread or guarded.

Both techniques trade memory and complexity for fewer dispatches. Fusing increases the size of the opcode space, which in a one-byte encoding means evicting or relocating existing opcodes, and it interacts with jump targets: a fused instruction that spans a branch target cannot be inserted without invalidating the target. Quickening requires tracking which assumptions each rewritten instruction depends on, and undoing all of them when an assumption fails. These are the mechanisms behind the more elaborate adaptive systems covered under superinstructions and opcode quickening.

When dispatch stops being the bottleneck

The dispatch loop dominates only while handlers are short. An opcode that calls a generic addition routine, checks types, and allocates a result object spends most of its time elsewhere, and improving dispatch yields little. Dispatch therefore accounts for a large share of run time in arithmetic-heavy integer code and a small share in code dominated by calls into runtime helpers.

There is also a hardware ceiling. Each dispatch is an indirect branch, and even a well-predicted indirect branch consumes a branch-target-buffer entry and front-end bandwidth. Processors predict indirect branches by correlating with branch history, and a handler reached from many different predecessors has a target that varies, which defeats the correlation. Handlers that appear in many contexts, such as a generic load, become misprediction sources no matter how the dispatch is coded. This is one reason why engines that must go faster stop interpreting: they compile hot regions so that the opcode sequence is fixed in the instruction stream and the processor’s ordinary conditional-branch prediction applies.

For cold code, though, the interpreter remains and its dispatch design still matters. A tree-walking interpreter that recurses over syntax nodes has no dispatch loop at all, but it pays a function call per node and cannot share state across a fixed register file. A bytecode interpreter with computed goto pays one indirect branch per opcode and keeps the working state in a small number of fixed variables that the compiler can keep in registers across handlers, which is the real reason the technique wins: not the branch itself, but the fact that a single function containing all handlers lets the compiler allocate the stack pointer, instruction pointer, and frame pointer to machine registers for the whole dispatch loop.

The frame layout those registers point into is the subject of interpreter stack frame layout.