bytecode-interpreter

How it is built

Architecture overview

A bytecode interpreter runs a program in two steps. A compiler flattens the source (a script, an SQL statement, a WebAssembly module) into a compact array of instructions plus a pool of constants. A small loop, the dispatch loop, then fetches one instruction at a time and does what it says on a frame of values. CPython, Lua, SQLite and the WebAssembly interpreters all work this way. The interpreter pays a fixed cost per instruction (decode, dispatch, type check), and in return it starts at once, needs little memory, can be paused between any two instructions and is easy to debug.

What makes a design good is mostly the seams: how wide and how regular the instruction is, how the loop jumps from one handler to the next, how a value says what it is, who frees memory, and where the interpreter hands a hot path to something faster (inline caches, a JIT). This page follows one program from text to result and names the blocks at each seam.

Parts:

• Front end — turns text into a syntax tree and binds names — Recursive-descent parsing, Pratt parsing, Name resolution
• Bytecode compiler — lowers the tree to linear instructions with a constant pool — Bytecode compilation, peephole-optimization (no page yet), Varint (LEB128) for variable-length encodings
• Dispatch loop — fetch, decode, execute — bytecode-interpreter (no page yet)
• Values and objects — one word per value, shared layouts, interned strings, tables — Value tagging and NaN-boxing, Hidden classes (shapes), Swiss table, string-interning (no page yet), big-integer-arithmetic (no page yet)
• Quickening and caches — specialize instructions that see stable types — Inline caches, machine-code-emission (no page yet) for a later JIT
• Functions and coroutines — frames, closures, suspended computations — Closures and upvalues, fibers-stackful-coroutines (no page yet)
• Memory manager — frees what is unreachable — Reference counting, Mark-sweep garbage collection, Incremental and concurrent garbage collection, Slab allocator, thread-caching-allocator (no page yet), numa-aware-allocation (no page yet)
• Errors and debugging — exceptions, line tables, native stack walks — stack-unwinding (no page yet), Debug info (DWARF), calling-conventions-abi (no page yet), executable-formats-elf-pe (no page yet)

 text ─► lexer/parser ─► AST ─► name resolution ─► bytecode compiler ─► code object
                                                     (consts, locals, jump targets)
                                                                  │
   ┌──────────────────────────── frame (stack or registers) ◄─────┘
   │   ┌────────────── dispatch loop ──────────────┐
   └──►│ fetch ─► decode ─► handler ─► next opcode │──► host: tables, strings, calls
       └──────┬────────────────────────────┬───────┘
              │ hot, stable types          │ allocation
              ▼                            ▼
     quicken / inline cache          allocator + refcount or tracing GC

How the parts fit together

Front end

Recursive-descent parsing gives one function per grammar rule and full control of error messages; Pratt parsing handles expression precedence in one small loop. Both are hand-written because an interpreter's parser sits on the start-up path and a generator's tables would cost more than they save. Name resolution runs next, because bytecode refers to slots, not names: each local becomes a frame index, each captured variable a closure slot, each global a constant-pool name. The contract to the compiler is a scope table per function saying which names are local, captured or global.

Bytecode compiler

Bytecode compilation walks the tree once and emits linear instructions, a constant pool, and jump instructions whose targets are patched when the target address becomes known. SQLite makes the same split explicit: sqlite3_prepare_v2() is the compiler, sqlite3_step() the virtual machine, and a prepared statement is mostly its bytecode (SQLite, The SQLite Bytecode Engine). Why bytecode and not a tree walked at run time? SQLite's own account is that a flat opcode list can be printed as a table (EXPLAIN), separates front-end bugs from back-end bugs, is smaller than the tree, and can be paused between instructions, so a statement can be run until its first row and resumed later; it also admits that a tree of objects allows plans to change while running, and is easier to parallelize as a dataflow program (SQLite, Why SQLite Uses Bytecode). The author's claim that bytecode is faster is stated there as a belief, not a measurement.

The instruction format sets everything downstream. Examples, each verified in its source:

• Lua 5.4: 32-bit instructions with a 7-bit opcode and register operands of 8 bits (A, B, C), with variants for a 17-bit operand and a 25-bit jump (lopcodes.h).
• CPython: two bytes per instruction since 3.6, and since 3.11 some instructions are followed by inline cache entries (CPython dis documentation). CPython warns that bytecode is an implementation detail that may change between releases.
• SQLite: one opcode and five operands P1 to P5, where P1 to P3 are 32-bit integers and often registers, P4 can be a string, a blob or a function pointer, and P5 is a 16-bit flag word (SQLite opcode documentation).
• WebAssembly: a stack machine with structured control flow in the standard (WebAssembly core specification, overview), encoded with LEB128 integers. The wasm3 interpreter does not run that form directly: it translates it into its own operations in a compile pass and turns the stack model into a register-file model (wasm3 docs/Interpreter.md).

Peephole-optimization (no page yet) fuses common short sequences into one instruction; it is the cheapest optimization an interpreter has, because it shortens the number of dispatches.

Stack machine or register machine

A stack VM needs no operand fields (add pops two, pushes one) and makes the compiler trivial, but it executes more instructions per statement. A register VM names its operands in the instruction, so one instruction does the work of several stack instructions, but each instruction is wider and the compiler needs register allocation for temporaries. Lua is the documented case: it used a stack-based VM from its first release in 1993 and has used a register-based one since Lua 5.0 in 2003 (Ierusalimschy, de Figueiredo and Celes, The Implementation of Lua 5.0). Shi, Casey, Ertl and Gregg compared the two designs experimentally (Virtual machine showdown: stack versus registers, 2008). CPython and WebAssembly stay with stacks; the portability and the size of the bytecode matter more to them.

Dispatch loop

The loop is where the machine-level cost lives. Three styles, all in production:

Lua is the neat illustration: the same handler bodies are compiled either way because vmcase and vmbreak are macros that ljumptab.h redefines to labels and goto (verified in the Lua source).

Why does it matter? Ertl and Gregg (The Structure and Performance of Efficient Interpreters, 2003) measured that indirect branches were 3.2% to 13% of executed instructions in their interpreters and took more than half of run time in some of the simulated configurations, because one shared indirect jump predicts badly; giving each handler its own jump spreads the history. That is the idea of threaded code (Bell, 1973). Rohou, Swamy and Seznec (Branch prediction and the performance of interpreters, CGO 2015) revisited this on three recent generations of Intel processors (Haswell the newest) and found that indirect-branch prediction accuracy is no longer critical, so the old advice is weaker on modern CPUs. Measure on your target before paying for portability.

The tail-call design attacks a different cost: with one big function, the C compiler may keep the interpreter's registers in a poor allocation. CPython 3.14 adds an interpreter in which each opcode is a small C function that tail-calls the next, instead of one large case statement; its release notes report a preliminary geometric-mean gain of 3 to 5% on pyperformance for Clang 19 on x86-64 and AArch64, and keeps it opt-in. The wasm3 author gives the same rationale: with a fixed function signature the virtual machine registers (program counter, stack pointer, memory pointer, a value register) map onto real CPU argument registers (wasm3 docs/Interpreter.md). The cost is a dependence on the compiler guaranteeing tail calls. CPython also generates its handlers from one definition file, bytecodes.c, using the scripts in Tools/cases_generator/, so the three dispatch styles share a single source of truth.

Values and objects

Every instruction touches values, so their representation decides how much a type test costs. Value tagging and NaN-boxing packs type and payload in one word; Lua's own TValue is a tagged union of a value and a type tag (lobject.h), CPython uses a pointer to an object with a reference count. Objects with named fields get a shape, the layout shared by every object built the same way, so a field access can be cached. Tables and dictionaries are the central structure of these languages; a modern open-addressing design is the Swiss table. Strings: Lua interns short strings so equality is a pointer compare (lstring.c); string-interning (no page yet) is the block name. Integers that overflow one word need big-integer-arithmetic (no page yet), which Python needs for its arbitrary-precision int.

Quickening and caches

A plain interpreter re-checks types on every execution. PEP 659 and CPython 3.11 turn the check into state: the interpreter counts executions, and once an instruction is hot it rewrites it in place to a specialized form (for example one that assumes both operands are floats) guarded by a cheap check, with an inline cache entry stored right after the instruction. A failed guard falls back to the generic form and can re-specialize later (PEP 659; What's New in Python 3.11). It is a JIT-style optimization without machine code. When machine code is wanted, the next step is a template JIT; CPython 3.13 added an experimental copy-and-patch JIT (PEP 744), and machine-code-emission (no page yet) is the block that encodes instructions in other designs. The jit-vm system covers that road.

Functions, closures and coroutines

A call pushes a frame holding the code object, the instruction pointer and slots for locals. Closures and upvalues explain how an inner function keeps variables of an outer one after it returns: a captured variable stays in the frame while it is open and moves to the heap when the frame exits (Lua's open and closed upvalues). Lua 5.0 added coroutines (Ierusalimschy et al.), which in a bytecode VM are cheap because a suspended coroutine is just its own frame stack and instruction pointer; fibers-stackful-coroutines (no page yet) is the general block.

Memory manager

CPython manages memory with Reference counting, which frees objects the moment the last owner drops them and costs a count update on every copy; a cycle collector supplements it for reference cycles (CPython gc documentation). Lua uses a tracing collector (Mark-sweep, incremental by design); its source in lgc.h also has a generational mode with object ages. The Incremental and concurrent garbage collection block covers the barriers and pauses. Underneath, small objects come from a Slab allocator-style size-class allocator (CPython ships its own small-object allocator in Objects/obmalloc.c), and thread-caching-allocator (no page yet) and numa-aware-allocation (no page yet) matter when the host has many threads.

Errors, debugging and the native boundary

Exceptions in CPython 3.11 became "zero-cost": a try costs nothing until an exception is raised, because handlers are found through tables instead of runtime setup (What's New in Python 3.11). Unwinding the interpreter's own frames is easy; unwinding the host's C stack for crash reports or profilers needs stack-unwinding (no page yet) and Debug info (DWARF), and a native call from bytecode follows the platform ABI (calling-conventions-abi, no page yet).

Data and control flow

Running a statement end to end (SQLite):

1. sqlite3_prepare_v2() parses the SQL, plans it and emits bytecode: opcode plus P1 to P5 per instruction, registers and b-tree cursors numbered. Time goes into planning and code generation; the AST is dropped before the call returns.
2. The prepared statement is cached by the application; it persists as bytecode only.
3. sqlite3_step() enters the dispatch loop at instruction 0; each opcode reads and writes registers, opens or moves cursors, or jumps by writing a new program counter.
4. A result-row opcode returns control to the caller with a row; the next sqlite3_step() resumes at the following instruction. The pause between rows is why incremental execution is free.
5. EXPLAIN prints the same bytecode as a table of opcode and five operands.

One dispatch step (any VM):

1. Fetch: read the instruction at the program counter, advance it.
2. Decode: split opcode and operands (shifts and masks).
3. Dispatch: jump to the handler (switch, table jump, or tail call).
4. Execute: touch registers or the stack; check types, maybe quicken; maybe allocate.
5. Poll: check for interrupts or hooks at back-edges and calls; then fetch again.

Scaling

In the order you meet them:

1. Dispatch overhead. Fewer, bigger instructions (register form, fused instructions), then computed goto or tail calls, then specialization. Measure each on the target CPU; the gain from a better dispatch style is a few percent on a modern core.
2. Type-check and lookup overhead. Shapes plus inline caches turn property lookup into a compare and a load.
3. Allocation and memory management. Cheaper allocation (size classes, thread caches), fewer allocations (small values unboxed), lower reference-count traffic.
4. Peak speed. Beyond the interpreter's ceiling the lever is a JIT; see the jit-vm system. wasm3's author reports roughly 4x to 15x slower than compiled code (self-reported benchmarks in docs/Interpreter.md), which is about the range to expect.
5. Parallelism. One interpreter state is single-threaded; scale by running several isolated interpreters (SQLite connections, processes, Lua states).

Failure modes

Real implementations

Sources

• SQLite: The SQLite Bytecode Engine, Why SQLite Uses Bytecode; src/vdbe.c in sqlite/sqlite.
• R. Ierusalimschy, L. H. de Figueiredo, W. Celes, The Implementation of Lua 5.0, J.UCS 2005; Lua source lopcodes.h, lvm.c, ljumptab.h, lobject.h, lstring.c, lgc.h in lua/lua.
• M. A. Ertl, D. Gregg, The Structure and Performance of Efficient Interpreters, Journal of Instruction-Level Parallelism 5, 2003.
• E. Rohou, B. N. Swamy, A. Seznec, Branch Prediction and the Performance of Interpreters: Don't Trust Folklore, CGO 2015.
• Y. Shi, K. Casey, M. A. Ertl, D. Gregg, Virtual machine showdown: stack versus registers, ACM TACO 2008. DOI
• J. R. Bell, Threaded code, Communications of the ACM, 1973. DOI
• CPython: PEP 659 Specializing Adaptive Interpreter, PEP 744 JIT compilation, What's New in Python 3.11, 3.13 and 3.14, dis module, gc module; source Python/bytecodes.c, Python/ceval_macros.h, Objects/obmalloc.c.
• wasm3: Interpreter.md; WebAssembly core specification, overview.