Tree-Walking Interpretation and the Cost of Re-Deciding at Every Node

An interpreter that walks the syntax tree decides, for every node it visits, what kind of node it is and what to do about it. That decision is made afresh on each visit, even though the shape of the tree cannot change between runs. The cost of that repeated decision, together with the pointer chasing it requires, is the defining performance characteristic of tree-walking interpreters, and it explains most of the distance between them and bytecode machines.

A dispatch that happens once per node visit

The core of a tree-walker is a function that takes a node and an environment and returns a value. In C the node carries a tag, and the evaluator switches on it:

typedef enum { N_INT, N_VAR, N_ADD, N_LET, N_CALL } Tag;

typedef struct Node {
    Tag tag;
    union {
        long value;                                  /* N_INT */
        struct { const char *name; } var;            /* N_VAR */
        struct { struct Node *lhs, *rhs; } bin;      /* N_ADD */
        struct { const char *name; struct Node *init, *body; } let;
        struct { struct Node *callee; struct Node **args; int argc; } call;
    };
} Node;

static Value eval(const Node *n, Env *env) {
    switch (n->tag) {
    case N_INT: return int_value(n->value);
    case N_VAR: return env_lookup(env, n->var.name);
    case N_ADD: {
        Value a = eval(n->bin.lhs, env);   /* recursive call: a and b must be spilled */
        Value b = eval(n->bin.rhs, env);
        return add(a, b);
    }
    /* ... */
    }
}

Three costs appear in those few lines. The switch is an indirect branch whose target depends on data loaded from memory, so the branch predictor has to learn a pattern that the tree layout does not make regular. Every subexpression is a real function call, which means the arguments to add live in memory rather than in registers, and the callee cannot be inlined because its target is not known until the tag is read. And the value returned by every recursive call is a boxed Value, even when both operands were machine integers, because the evaluator’s type is uniform across all node kinds.

A modern out-of-order core mispredicts a data-dependent indirect branch often enough that the penalty, tens of cycles, dominates the arithmetic being performed. The useful work in 1 + 2 is one add. The work the interpreter actually does is load a tag, branch, recurse twice, re-check two tags, spill two values, call add, and box the result. The ratio of overhead to payload is why a naive tree-walker runs an order of magnitude or more slower than compiled code on arithmetic-heavy loops, and the exact ratio depends heavily on how often the branch predictor guesses correctly.

Name lookup is the second, larger cost

Variable access in a tree-walker usually goes through the environment. The simplest environment is a linked list of frames, each holding name/value pairs, and lookup walks the list comparing strings. That is a pointer chase plus a string comparison per scope level, per variable use, inside the innermost loop of the program being interpreted.

Interpreters that care about speed resolve names before evaluation. The resolver annotates each variable reference with a lexical depth and a slot index, which turns lookup into a bounded walk of frame pointers followed by an array index:

typedef struct Frame {
    struct Frame *parent;
    Value slots[];                 /* fixed size, known from the resolver */
} Frame;

static inline Value slot_get(Frame *f, int depth, int index) {
    while (depth-- > 0) f = f->parent;   /* bounded by static nesting depth */
    return f->slots[index];
}

The depth is a compile-time constant, so the loop trip count is fixed and the frames can be allocated contiguously. What remains is one dependent load per scope level. For code that uses only locals of the current function, depth is zero and the access is a single indexed load, which is as cheap as a local variable access in compiled code.

Globals are the exception, because their set is not known statically and their values can be redefined at any time. A dictionary lookup per global reference is expensive enough that production interpreters cache the result. CPython, for example, keeps a per-instruction cache for global and attribute loads and invalidates the cached entry when the globals dictionary or the receiver’s type changes version; the caching machinery is described in PEP 659. The general shape is the same everywhere: assume the binding seen last time is still valid, verify cheaply, fall back to the general lookup when the check fails.

Flattening the tree into a linear instruction stream

Compiling to bytecode removes the per-node decision by moving it out of the running program. The instruction stream is a linear array of small operations, each with a fixed operand format, and the interpreter’s dispatch loop is one indirect jump shared by every instruction. The “what to do” is encoded in the opcode that was already fetched, and the operands are read from the same cache line in the common case.

The trade is not free in either direction. A bytecode program executes more dispatches than the tree has nodes, because a single arithmetic node becomes several instructions: fetch a local, fetch another local, add, store. But each dispatch is cheaper than a node visit. There is no argument plumbing, no host call per subexpression, and the interpreter’s working set is a compact code array rather than a graph of separately allocated nodes, so the instruction fetch stream stays in cache. The operand stack replaces recursion, which removes the host stack frame per subexpression and lets the interpreter keep intermediate values in a small contiguous array.

The quantity that matters is not dispatches per second but cache misses per operation. A tree node allocated by a parser is typically several dozen bytes, scattered across the heap in allocation order that reflects parse order rather than execution order. Following the tree is a pointer-chasing walk with poor spatial locality. A bytecode array is contiguous and executed in order, which is exactly what the prefetcher is built to handle. This locality difference, more than dispatch count, accounts for the gap between a tree-walker and a stack machine on the same source program. The stack bytecode loop covers the other half of that comparison.

What the tree keeps that bytecode discards

Flattening throws away structure that some tools need. Error messages from a tree-walker can name the subexpression that failed, because the subexpression is still an object with a source range. Debuggers can single-step at expression granularity. Macro systems in the Lisp tradition operate on the tree directly, which is why they can introduce bindings that the parser would otherwise reject; a bytecode-only compiler has to reconstruct or preserve that structure separately.

Bytecode implementations pay for this with side tables. Every instruction offset maps back to a source position through a table the compiler emits alongside the code, and the debugger reads that table rather than the code. CPython stores line numbers in a compact table attached to the code object, and newer versions store column ranges as well. The information survives, but it is reconstructed on demand rather than being intrinsic to the representation.

Startup cost is the other axis. A tree-walker begins executing as soon as the parser finishes, with no separate compilation pass. That is why small-language implementations, configuration evaluators, and template engines are usually tree-walkers: the programs they run are short-lived, so compile time is a large fraction of total time, and the steady-state throughput advantage of bytecode never gets amortized. The crossover is a function of how many times each node is executed. A loop body executed a thousand times amortizes compilation easily; a script executed once does not.

Where the model breaks

Deeply nested source becomes deep host recursion. An expression nested d levels requires d simultaneous evaluator frames, each holding locals, saved registers, and a return address; a few thousand levels fit in a default thread stack, and tens of thousands do not. The failure is a host stack overflow, which arrives as a signal or an unrecoverable fault rather than as an exception the language can catch. Bytecode compilers avoid the runtime version of this problem by rejecting excessive nesting during compilation, converting it into a diagnostic at a point where the program can still report it.

Tail calls expose a second structural weakness. A tree-walker written in a language without proper tail calls consumes host stack for every source-level call, including the tail calls that a Scheme program relies on for iteration. Implementations work around this with a trampoline, where the evaluator returns a description of the next call instead of making it, or with an explicit continuation representation. Both add a dispatch per call, which is the same cost the tree-walker was already paying, now paid twice.

Mutation semantics depend on where environments live. If the evaluator copies values into a frame on entry, a closure that outlives the frame sees a stale copy; if it stores a pointer to a heap frame, the closure and the frame share mutations. The difference is invisible in the interpreter’s code and visible in the language’s semantics, and it is the reason closure conversion is a separate design decision from evaluation order. Value boxing interacts with both: a uniform Value type makes the evaluator simple and makes every arithmetic operation allocate or at least widen, which is why implementations that start as tree-walkers eventually confront the representation choices described in tagged values and NaN boxing.

Tree-walking remains the right design when the program is short, the language is small, or the tree is the interface. It is the wrong design when the same code runs many times, because the decision that the tree forces at every node is a decision that a compiler could have made once.