VMtypical

The Dispatch Loop

Fetch, decode, execute, repeat. Three lines of structure hold an entire language implementation, and the branch at the centre of them is one of the least predictable in ordinary software — which is why so much interpreter engineering is really branch engineering.

The question

What is actually at the centre of an interpreter, and why does the way it branches matter so much?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

The program is a linear instruction array and the machine's control state is a single integer, the instruction pointer. The dispatch loop is the function that turns that pair into execution: it reads the instruction at ip, advances, and transfers control to the code implementing that opcode. Everything else in a VM is state; this is the only part that is control.

What this phase may assume or do

A dispatch technique may be replaced by any other technique that preserves the same sequence of instruction effects, in the same order, with the same faults at the same points. That is a low bar for correctness and a high one for observability: switching to threaded dispatch is transparent to programs, but it changes what a profiler attributes work to and can make single-stepping in a native debugger considerably harder to follow.

Key points

  • The dispatch loop is fetch, advance, execute, repeat — and its body runs once per bytecode instruction, so everything in it is multiplied by the program's instruction count.
  • The transfer to an opcode handler is an indirect branch, and in switch dispatch there is only one such site with one history.
  • Threading gives each handler its own dispatch site, so the branch predictor gets per-opcode history and exploits the strong correlation between adjacent opcodes.
  • Direct threading stores handler addresses in the code array itself, which is fastest and makes the code non-portable and non-serializable.
  • Dispatch is not always the dominant cost: type tests and boxing often exceed it in dynamically typed VMs.
  • Every dispatch technique is a way to spend less per instruction; a JIT is the way to stop executing the loop at all.

Three lines that run everything

Strip an interpreter of its opcode implementations and this is what is left: a loop that reads an instruction, works out what kind it is, and runs the corresponding code. Our VM's loop is literally this, with a step budget wrapped around it so a non-terminating program stops rather than hanging the browser tab.

Two observations before any optimization. First, the loop body executes once per bytecode instruction, so anything in it is multiplied by the whole program's instruction count — this is the definition of a hot path. Second, the transfer to the opcode implementation is an indirect branch whose target changes constantly, and that single property drives most of what follows.

The switch-dispatch loop, which is what almost every interpreter starts as
1while (running) {
2  Instr ins = code[ip];      /* fetch  */
3  ip = ip + 1;               /* advance */
4  switch (ins.op) {          /* decode */
5    case OP_PUSH:  push(ins.operand);            break;
6    case OP_ADD:   b = pop(); a = pop();
7                   push(a + b);                  break;
8    case OP_JUMPF: if (!pop()) ip = ins.operand;  break;
9    case OP_HALT:  running = 0;                   break;
10    /* ... one case per opcode ... */
11  }
12}

The switch compiles to a bounds check and an indirect jump through a table — one indirect branch, at one code address, whose target is a different opcode handler almost every iteration. Every break returns to that same branch. This is the structure the rest of the lesson is trying to improve on.

Why the indirect branch is the whole story

typicalThe claim that threaded dispatch beats switch dispatch was established on processors whose indirect-branch predictors kept a single history per branch site. Later predictors use much longer global histories and can predict a shared dispatch site far better, so measured gains from threading have shrunk on recent hardware and in some published measurements have nearly vanished. The technique is still worth knowing and is no longer a guaranteed win — measure on the machine you ship to.

A modern CPU predicts branches in order to keep its pipeline full, and an indirect branch is predicted by guessing the target address from the history of that branch site. In a switch-dispatch interpreter there is *one* such site, and its target sequence is the program's opcode sequence — which is, from the predictor's point of view, close to noise. Every mispredict costs a full pipeline refill.

This is the mechanism behind the classic threading optimization. If each opcode handler ends with its own copy of the dispatch — its own indirect branch — then the predictor sees many sites instead of one, and each site has its own history. Opcode sequences in real bytecode are highly correlated (a LOAD is very often followed by another LOAD, a compare by a conditional jump), so per-site histories predict much better than one shared history does.

  • Switch dispatch — one switch at the top of the loop. Portable, readable, and concentrates every dispatch into a single hard-to-predict indirect branch.
  • Token threading (computed goto) — a table of label addresses, and each handler ends with goto *table[code[ip++].op]. Requires a compiler extension such as GCC and Clang's labels-as-values; removes the loop and the bounds check, and gives each handler its own branch site.
  • Direct threading — the instruction array holds handler addresses rather than opcode numbers, so the dispatch is goto *code[ip++] with no table lookup at all. Faster still, and the code array is no longer portable or serializable, because it contains addresses from this process.
  • Subroutine threading — each instruction is a call to a handler; the hardware return-address predictor then does the work. Simple, and pays a call and return per instruction.
  • Replication and superinstructions — duplicate handlers, or fuse common pairs into one, so that fewer dispatches happen and each site sees a narrower distribution of successors. Covered as a performance technique in [[interpreter-performance]].

The other costs in the loop

Dispatch is the famous cost and not always the largest one. Every iteration also loads the instruction, extracts its operand, touches the operand stack, and — in a language with dynamic types — asks what the operands actually are before it can do anything with them. In a dynamically typed VM, that type test and the boxing around it frequently cost more than the dispatch does.

The structural fix for all of these is the same and it is not a better loop: it is executing fewer, larger instructions. Superinstructions do it at the interpreter level; a JIT does it by removing the loop entirely for hot code, which is why [[jit-compilation]] is the next module rather than a footnote here.

Where an iteration goes, and what removes each parttypical
Cost per instructionWhat it isWhat removes or reduces it
DispatchAn indirect branch to the handler, frequently mispredictedThreading, replication, superinstructions — and a JIT, which removes it entirely
Fetch and decodeLoading the instruction and extracting its operand fieldsDirect threading removes the table lookup; wider instructions amortize it over more work
Operand accessReading and writing the operand stack in memoryStack caching — keeping the top one or two entries in host registers
Type dispatchimplementationAsking what the operands are before operating on themInline caching and specialized opcodes — see [[inline-caches]]
BoxingimplementationAllocating or unwrapping a heap object per valueTagged representations, unboxed fast paths, escape analysis

Our loop, and what it is honest about

simplifiedOur dispatch loop is a JavaScript switch inside a while, running under a JIT-compiled host that is itself doing everything this lesson describes one level down. Nothing about its measured speed says anything about interpreter dispatch techniques; the C listings above are where the actual claims live. Reading our loop teaches the shape — fetch, advance, execute, check the budget — and nothing about cost.

The AtlasLang VM uses plain switch dispatch, because it is written in JavaScript and neither threading technique is expressible there — there is no computed goto and no way to put a code address in an array. So our loop demonstrates the *structure* faithfully and the *performance techniques* not at all, and saying so is better than implying a JavaScript switch teaches you anything about branch prediction.

What it does add is a step budget. The loop condition is executed < stepBudget, and when the budget runs out the result is reported with status steps-exhausted and no answer, rather than a plausible number or a hung tab. A VM that cannot terminate must decide what to do about that in the dispatch loop, because there is nowhere else to put the check — see [[vm-state-model]].

How it works

The steps, in the order the compiler takes them.

  • Load the instruction at the instruction pointer from the code array.
  • Advance the instruction pointer, before executing, so that a jump inside the handler simply overwrites it.
  • Transfer control to the code for this opcode — via a switch table, a computed goto, or a stored handler address.
  • Execute the opcode's effect on the operand stack, the slots, the frame stack or the output.
  • Check whatever the loop is responsible for besides execution: the step budget, a pending interrupt or signal, a garbage-collection safepoint.
  • Record a trace row if tracing is enabled and the trace limit has not been reached, then return to the top.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • The instruction pointer is advanced after the handler rather than before, so a jump instruction has its target overwritten by the increment and every branch goes to the wrong place by one.
  • A new opcode is added to the compiler and not to the dispatch switch; the default case does nothing and the program produces a wrong answer instead of an error.
  • The loop checks for interrupts only at back edges, so a long straight-line stretch cannot be interrupted and the user sees an unresponsive process that eventually recovers.
  • A handler falls through to the next case because a break was omitted, giving an opcode the effect of two — a bug that passes every test not containing that exact instruction.
  • Direct-threaded code is serialized to disk with handler addresses in it and fails or behaves erratically when reloaded into a different process with a different code layout.

When it helps

  • Any interpreter at all — this loop is the minimum viable implementation of an executable format.
  • Adding cross-cutting behavior cheaply: budgets, safepoints, interrupt polling, profiling counters and tracing all attach here and nowhere else.
  • Reasoning about interpreter performance, because "what does one iteration cost" is the right unit and this is where an iteration lives.

When it hurts

  • When the loop becomes the place everything is added. Each extra check in the body is multiplied by the instruction count, and a well-meaning per-instruction hook can halve an interpreter's speed.
  • When threading is applied for its own sake: it costs portability and readability, needs compiler extensions, and on recent hardware may buy much less than the literature suggests.
  • When it is optimized instead of eliminated. Past a certain point the answer is not a faster loop, it is compiling hot code and not running the loop for it.

What it costs

Every one of these is paid by something.

  • Switch dispatch buys portability and readability and pays with one heavily shared, poorly predicted indirect branch.
  • Token threading buys per-site branch history and pays with a compiler extension, unreadable macro-heavy handler code, and a debugging experience where every handler ends in a jump to nowhere obvious.
  • Direct threading buys the fastest dispatch and pays by putting process-specific addresses in the code array, which forbids serializing, sharing or memory-mapping the compiled form.
  • Adding per-instruction checks — budgets, safepoints, profiling — buys control and observability and pays a fixed tax on every instruction the program will ever execute.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Compile hot code and stop dispatching for it: the only change that removes the cost rather than reducing it — [[jit-compilation]].
  • Fuse frequent instruction pairs into single superinstructions, cutting dispatch count rather than dispatch cost — [[interpreter-performance]].
  • Subroutine threading, where each instruction is a call, letting the hardware's return-address stack do the prediction; simple, and it pays a call and return per instruction.
  • Closure-based execution, where each operation is a host closure invoked by the previous one, replacing dispatch with an indirect call that the host runtime may itself optimize.

See it for yourself

The flag, dump or tool that shows you this directly.

  • Read a real one: CPython's evaluation loop in Python/ceval.c is the canonical example, and it is written so that it compiles either as a switch or as computed gotos depending on USE_COMPUTED_GOTOS.
  • Measure the branch cost directly: perf stat -e branch-misses,branches ./interpreter on Linux shows the misprediction rate, and it is dramatically higher for a switch interpreter than for ordinary application code.
  • perf annotate on the interpreter binary shows how many instructions the dispatch itself compiles to, which is the honest measure of what threading is saving.
  • Our loop is in src/compilers/sim/vm.ts and is stepped instruction by instruction at /compilers/vm, including the step budget the loop condition enforces.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Computed goto makes interpreters 2x faster." It made some interpreters meaningfully faster on the hardware where the technique was established. On recent predictors the measured gain is often small, and it is a portability and readability cost either way.
  • "The switch is slow because it is a switch." It is slow because it is one indirect branch whose target is essentially unpredictable. A switch over a variable the predictor can learn is not slow at all.
  • "Dispatch is where interpreters spend their time." It is where *some* interpreters spend a large share. In dynamically typed VMs, type tests and allocation frequently cost more, and optimizing dispatch there is optimizing the wrong thing.
  • "Once it is threaded there is nothing left to do." Superinstructions, stack caching and inline caching all still apply, and a JIT still beats all of them by removing the loop.

Misconceptions

The claim, and what is actually true.

The dispatch loop is where you make an interpreter fast.
It is where you make it a few tens of percent faster. Making it several times faster means executing fewer instructions — superinstructions, specialization — and making it an order of magnitude faster means not interpreting hot code at all.
Each bytecode instruction is roughly one machine instruction.
A single iteration is a fetch, an unpredictable indirect branch, the handler body and the loop back edge — commonly tens of machine instructions for one bytecode operation.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

An interpreter is a loop. Read the next instruction, work out which one it is, do what it says, go back to the top. The "work out which one it is" step is a jump to a different piece of code every time, and CPUs are bad at guessing where such a jump is going — which is most of why interpreters are slower than compiled code even when they do the same work.

practical

Write the switch version first; it is portable, readable and fast enough to be useful. Before optimizing the dispatch, measure branch-misses and check how much of your time is really there — in a dynamically typed language it usually is not. And be disciplined about what you add to the loop body: every check you put in it is paid once per instruction for the life of the program, which makes it the most expensive place in the codebase to be casual about a feature.

advanced

The deep version of this subject is that dispatch cost and instruction granularity are the same variable seen from two sides. Threading reduces the cost per dispatch; superinstructions reduce the number of dispatches; specialization reduces the work inside each handler by removing checks the observed types made unnecessary; and a JIT takes the limit of all three by turning a whole trace or method into straight-line native code with no dispatch at all. Each step buys speed with interpreter code size, and interpreter code size pushes against the instruction cache — which is the reason a heavily replicated, heavily specialized interpreter can measure slower than a plain one on a program that touches many opcodes. That tension, and not any single technique, is what interpreter engineering actually consists of.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThreading's advantage over switch dispatch was established on predictors that kept one history per indirect-branch site. Modern predictors use long global histories and predict a shared dispatch site much better, so reported gains have shrunk and vary by microarchitecture. The technique remains standard in production interpreters, and the size of its benefit is a measurement, not a constant.
implementationCPython's ceval.c uses computed gotos where the compiler supports them and a switch otherwise, and its loop has changed substantially across 3.11 and 3.12 with specialization and inlined frames. Any statement about "how the CPython loop works" needs a version attached.
simplifiedOurs is a JavaScript switch running inside a host that is itself JIT-compiling our loop. It shows the structure — fetch, advance, execute, budget check — and nothing about dispatch cost, because neither threading technique can be expressed in the host language.

If you were asked this in an interview

  • Write the three lines at the centre of an interpreter. Now tell me which one the CPU has trouble with and why.
  • What does computed-goto dispatch change, and under what conditions would you expect it to buy nothing?
  • You want to add a garbage-collection safepoint check to a VM. Where does it go, and what does it cost?

Connections

Computer Architecturebranch-predictionbranch-mispredictioninstruction-cachepipeliningout-of-order-execution
Performancecpu-profilingmeasure-before-optimizing
Domains that do not exist yet
  • Programming Languages & Runtime Internals — Safepoints: the points at which the dispatch loop is allowed to stop and let the collector run
    The loop is the only place a VM can poll for collection, interrupts or signals, so where the poll goes determines both pause behavior and how long a runaway loop stays uninterruptible. The compiler decides where safepoints are legal; the runtime decides what happens at them.