Interpreters & Bytecode VMs: Tree-Walking to Dispatch

Interpreters & Bytecode VMs

An interpreter executes a program without translating it to machine code first. That sounds like a compromise, and it's how most of the world's software runs: Python, Ruby, and the initial tier of every JavaScript and Java engine all interpret. The reasons are portability (one interpreter, every platform), startup time (no compilation pause), simplicity (you can write a working one in a weekend), and dynamic capability (eval, hot reload, REPLs).

There are two designs, and the gap between them is large. A tree-walking interpreter recursively evaluates the AST directly — trivially simple, and slow because every operation costs a virtual dispatch and pointer chase through a scattered tree. A bytecode VM first compiles the tree into a flat array of compact instructions and then runs a dispatch loop over it — significantly more code, and commonly 10–50× faster because the instruction stream is contiguous, dispatch is a jump table, and operands are indices rather than pointers.

The performance story is mostly about dispatch overhead and memory layout, and understanding that is what makes the difference between an interpreter that's slow and one that's respectably fast.

TL;DR

Tree-walking: recurse over the AST. Simple, portable, slow. Fine for config, DSLs, and learning.
Bytecode VM: compile to a flat instruction array, then run a dispatch loop. 10–50× faster.
Stack machines are easy to compile to; register machines need fewer instructions and are faster.
Dispatch is the hot path — switch, computed goto, or direct threading, in increasing speed.
Call frames hold locals and a return address; closures need captured variables to outlive the frame.
Represent values compactly — NaN boxing or tagged pointers, not a heap-allocated object per integer.
Inline caches speed up property access dramatically in dynamic languages.
Past a certain point, the answer isn't a faster interpreter — it's a JIT.

Quick Example

The same language, both ways:

The tree is gone. What remains is a contiguous byte array the CPU can stream through, with a jump table for dispatch and indices instead of pointers — which is essentially the entire performance difference.

Core Concepts

Stack vs. register machines

Stack machines are trivially easy to compile to — a post-order tree walk emits correct code with no allocation decisions. Register machines execute fewer instructions, which matters because dispatch dominates interpreter cost: Lua's move to a register VM in 5.0 produced a large, well-documented speedup. The tradeoff is that you now need register allocation in the compiler.

WebAssembly chose a stack machine deliberately — it's compact on the wire and easy to validate, and the consumer is a JIT that will convert to registers anyway.

Dispatch

The interpreter's inner loop is fetch instruction → jump to handler → repeat, and the jump is unpredictable, so the CPU's branch predictor does badly.

Further up the ladder: superinstructions fuse common pairs (LOAD; ADD → LOAD_ADD) to cut dispatch count, and subroutine threading compiles the bytecode into a sequence of calls. CPython 3.11+ added an adaptive specializing interpreter that rewrites hot instructions into type-specialized variants — a technique that lives right at the boundary between interpretation and JIT.

Value representation

A naive interpreter heap-allocates an object for every value, which destroys performance. Two standard techniques:

NaN boxing halves value size, which halves stack and heap traffic and roughly doubles how many values fit in cache. It's used by LuaJIT, JavaScriptCore, and SpiderMonkey. Pointer tagging — using the low bits of aligned pointers for a type tag — is the equivalent trick on the object side, used by V8 for small integers ("Smis").

Call frames and closures

Two standard solutions. Upvalues (Lua, and clox in Crafting Interpreters): captured locals start on the stack and are "closed" — copied to the heap — when the frame exits, so the common non-captured case stays fast. Environment chains: every scope is a heap-allocated record, simple but slow because every variable access walks a chain.

A compiler pass that determines at compile time which locals are captured lets you use fast stack slots for everything else, which is a large win.

Inline caches

Dynamic property access is the dominant cost in most dynamic-language programs, and it's mostly repeated identical lookups.

Combined with hidden classes (V8) or shapes (SpiderMonkey) — where objects with the same field layout share a shape descriptor — this turns a hash lookup into a pointer comparison and an array index. It's the single largest performance technique in dynamic language runtimes, and it's why for (const o of objects) sum += o.x is fast when all the objects have the same shape and slow when they don't.

Performance

Where the time actually goes in a bytecode VM:

The order of operations for optimizing an interpreter is fairly consistent: compact value representation first, then computed-goto dispatch, then inline caches, then superinstructions — and then accept that further gains require a JIT.

Best Practices

Start with a tree-walker

Get the language correct and the semantics settled before optimizing the execution strategy. A tree-walking interpreter is a few hundred lines and is the right vehicle for designing a language. Rewrite as a bytecode VM once the semantics stop moving.

Use a compact value representation early

NaN boxing or a tagged union is a foundational choice that's painful to retrofit — it touches every operation in the VM. Decide before writing the interpreter loop.

Make the dispatch loop as small as possible

Everything in the hot loop competes for instruction cache. Keep handlers short, move slow paths into separate non-inlined functions, and avoid anything in the loop body that isn't fetch-decode-execute.

Resolve variables at compile time

Turning a name into a stack slot index during compilation replaces a hash lookup with an array index on every access. This is one of the largest and easiest wins available, and it requires a resolver pass over the AST.

Add inline caches for dynamic lookups

If your language has dynamic property access, this is the highest-value optimization after value representation. Even a monomorphic single-entry cache captures most of the benefit.

Design the bytecode for the VM, not for humans

Fixed-width instructions are simpler to decode; variable-width is more compact. Operand indices should be small enough to fit in a byte where possible, with wide variants for the rare overflow case. Optimize for decode speed rather than readability, and write a disassembler for debugging instead.

Write a disassembler on day one

Printing bytecode with offsets, opcode names, and resolved constants is the primary debugging tool for a VM. Without it, a compiler bug is a mystery; with it, it's obvious.

Benchmark on realistic programs

Microbenchmarks of arithmetic loops mislead badly — they don't exercise property access, allocation, calls, or GC, which is where real programs spend their time. Use a benchmark suite of programs that resemble what people will actually write.

Common Mistakes

Heap-allocating every value

Hash lookups for local variables

A dispatch loop full of extra work

Deep recursion in a tree-walker

Environment chains for every variable

Optimizing before measuring

FAQ

Tree-walking or bytecode?

Tree-walking for a config language, a template engine, a small DSL, or while designing a language. Bytecode once performance matters or the language is general-purpose. The rewrite is substantial but mechanical, and the 10–50× gap is large enough that few serious languages stay tree-walking. Crafting Interpreters deliberately builds both for the same language, which makes the comparison concrete.

Stack or register VM?

Stack for simplicity — code generation is a post-order walk with no allocation decisions, and it's what the JVM, CPython, and WebAssembly use. Register if performance is a priority and you're willing to write register allocation; Lua's switch to a register VM produced a well-documented substantial speedup. For a first VM, stack.

How fast can an interpreter get?

A well-optimized bytecode VM with NaN boxing, computed-goto dispatch, and inline caches lands roughly 20–70× faster than a tree-walker and still 10–50× slower than optimized native code on numeric work. LuaJIT's interpreter (hand-written assembly) is exceptionally fast and still hits a ceiling. Beyond that you need a JIT — there's no interpreter technique that closes the remaining gap.

Why do languages ship an interpreter and a JIT?

Startup time and memory. Compiling everything ahead of time wastes work on code that runs once, and JIT-compiled code uses far more memory than bytecode. The standard architecture is tiered: interpret everything initially, profile, and compile only the hot paths. HotSpot, V8, and SpiderMonkey all work this way, and CPython's recent specializing interpreter is a step along the same path.

Should I write my own VM or target an existing one?

Targeting an existing VM gets you a mature GC, a JIT, tooling, and a library ecosystem for free — Clojure and Kotlin on the JVM, Elixir on BEAM, and anything compiling to WebAssembly or JavaScript. Write your own when your semantics genuinely don't fit (unusual concurrency model, different memory model) or when the VM is the project. For most new languages, targeting is the pragmatic choice.

How does garbage collection fit in?

The interpreter must be able to tell the collector where every live reference is — the value stack, call frames, globals, and any temporaries held in native code during a VM operation. Getting this wrong produces the worst class of bug: an object collected while still reachable, manifesting as corruption much later. Design the GC interface alongside the VM rather than adding it afterward.