Chapter 9: Why tree-walking isn't enough

This chapter:

Write two small, deliberately CPU-bound Muspel programs.
Measure how long the Chapter 8 tree-walker takes to run them, for real, on real hardware.
Explain why those numbers are what they are, in terms of what the tree-walker is actually doing at each step, not received wisdom about interpreters being slow.
Set honest expectations for what a bytecode VM buys, and what it doesn't.

Where we left off: musc run correctly executes every example program so far, including recursion and functions passed as values. Correctness is settled. Speed is not.

9.1 Two benchmarks

examples/bench_fib.mus stresses function-call overhead specifically: naive, deliberately exponential recursive Fibonacci, so a single top-level call fans out into hundreds of thousands of nested ones.

func fib(n) {
    if (n < 2) {
        return n
    }
    return fib(n - 1) + fib(n - 2)
}
print(fib(28))

examples/bench_loop.mus stresses variable-access overhead specifically, with no function calls at all: a single while loop reading and writing one local variable five million times.

var total = 0
var i = 0
while (i < 5000000) {
    total = total + i
    i = i + 1
}
print(total)

Two different programs on purpose, stressing two different costs: bench_fib's hundreds of thousands of calls stress per-call allocation, bench_loop's five million loop iterations stress whatever it costs to read and write the same two variables that many times. Section 9.3 traces both costs to specific lines of Chapter 8's own code, not to a general reputation "interpreters are slow" carries.

9.2 Measuring it

musc grows a fifth subcommand, bench, that runs the same lex-parse-resolve pipeline run does, then times only the execution itself: lexing, parsing and resolving are a one-time cost paid once per file, not what this chapter is measuring.

cmd_bench :: proc(src: string) {
	// ... lex, parse, resolve, same as cmd_run ...

	interp := muspel.interp_init()
	start := time.now()
	muspel.exec_program(&interp, stmts)
	elapsed := time.since(start)
	fmt.printfln("tree-walk: %v", elapsed)
}

Gotcha: ./run.sh is the wrong tool for this chapter. Every earlier chapter reached for ./run.sh, which wraps odin run, an unoptimised debug build, because correctness doesn't care about optimisation level and rebuilding on every invocation is convenient. A benchmark cares about exactly the opposite. Timing bench_fib.mus through ./run.sh measured 463ms; the same file through ./build.sh's -o:speed binary measured 137ms, over three times faster, with not one line of Muspel or the tree-walker's own code any different. From here on, benchmark numbers come from the built binary, never ./run.sh.

Run against both benchmarks, on the machine this book is written on:

./build.sh
./musc bench examples/bench_fib.mus

317811
tree-walk: 137ms

./musc bench examples/bench_loop.mus

1.24999975e+13
tree-walk: 452ms

(fib(28) really is 317811; the loop's total really is 12499997500000, %v's scientific notation for a number that size, not a bug. Your own numbers will differ from these by machine, load, and Odin compiler version, but the shape, both taking a clearly-perceptible fraction of a second for work a native loop would finish in single-digit milliseconds, should hold everywhere.)

9.3 Why it's slow, concretely

It would be easy to wave a hand and say "tree-walking interpreters are slow, everyone knows that." Chapter 8's own code makes the reasons nameable instead.

Every AST node is a separate heap allocation, reached through a pointer. Look back at how the parser builds one: new(Expr_Binary, allocator), one heap allocation per node, scattered wherever the allocator happened to place it. Evaluating fib(n - 1) + fib(n - 2) means eval_expr chasing pointers through an Expr_Binary, to its two Expr_Call children, to their children, none of them adjacent in memory, none of them predictable to prefetch. A CPU that would happily stream through a flat array of instructions is instead playing pointer-chasing hopscotch across however the heap allocator felt like laying things out.

Every function call allocates a fresh Environment, on the heap, that never gets freed. call_function calls env_new, which calls new(Environment, allocator) and make([dynamic]Value, allocator), twice per call, for the lifetime of the process. bench_fib makes roughly 832,000 calls to compute fib(28) (one call per node in Fibonacci's own well-known binary call tree), which is roughly 832,000 small heap allocations that this chapter's tree-walker has no mechanism to ever reclaim. This is a real, honest violation of the no-per-frame-allocation discipline the rest of this book's house style otherwise holds to, and it's a deliberate one: a stepping stone built to validate semantics, not to be fast, doesn't need a bump allocator or a reuse pool. Chapter 13's VM fixes exactly this, with a fixed-capacity value stack and call-frame array allocated once, reused for every call, freeing nothing because it never allocated per call to begin with.

bench_loop's own loop body re-allocates an Environment every single iteration, too. total and i are declared at the top level, so reading or writing either one, both in the loop's own condition and inside its body, never touches an Environment at all: Chapter 7's resolver marks a top-level var depth == -1, and eval_expr's Expr_Ident case sends anything with depth == -1 straight to interp.globals[node.name], a map[string]Value lookup by name, not a chain hop. What does still cost something on every iteration is the loop body itself: it's parsed as a Stmt_Block (Chapter 4), and exec_stmt's ^Stmt_Block case allocates a brand new Environment (env_new, the same two heap allocations named above) every time it runs, which for a while loop is every single iteration, five million fresh, empty, immediately-discarded Environments over the life of this one benchmark, on top of five million-plus interp.globals map lookups (one for the condition, several more inside the body) that a flat, array-indexed local slot would have skipped entirely. Two different costs, both real, both paid by this one small program, and worth telling apart precisely because Chapter 13 doesn't remove them by the same mechanism: a bytecode VM's while compiles to a backward jump with no allocation whatsoever (section 11.3), but bench_loop's variables are still globals once compiled, and a bytecode Get_Global/Set_Global still costs exactly the same map lookup the tree-walker's interp.globals[node.name] does. Chapter 13 revisits this precise distinction with real numbers once both interpreters can actually be timed against each other.

There's no locality between "the code" and "the state that's currently running." A real running program's data (which instruction is next, which locals are live) doesn't need to look anything like the shape of the source text that produced it. A tree-walker never separates those two concerns: the AST is the only representation of the program that exists, so "what to do next" and "what the program looks like" are permanently the same tree, walked the same way, every single time a loop iterates or a function is called again.

9.4 What a bytecode VM buys, and what it doesn't

Every cost named above has the same shape: it's the cost of using the AST itself, unchanged, as the thing that gets executed, over and over, node by node. A bytecode VM's entire premise (Part III-IV) is to pay a translation cost exactly once, ahead of time, compiling the AST down into a flat, cache-friendly instruction stream with array-indexed local slots, and then run that instead, as many times as the program needs, with no AST pointer-chasing and no per-call heap allocation left anywhere in the hot path.

It's worth being honest about the limits of that claim before Part III oversells itself. Bytecode dispatch, even a well-written switch-based loop, is still not "as fast as compiled native code": there's no register allocation happening, no inlining across Muspel function boundaries, no branch-predictor-friendly machine code generated specifically for this program. A JIT (compiling hot bytecode down to actual machine code at run time) is the next real step past where this book stops, and it's a substantial undertaking of its own, one this book's scope deliberately doesn't take on (see the preface's own list of "where to go next"). What a bytecode VM honestly buys, for the cost of one compilation pass, is "fast enough for game-logic scripting, dramatically faster than tree-walking," not "indistinguishable from native code." Chapter 13 closes this chapter's loop with real numbers once that VM exists, run against these exact same two files.

Checkpoint

musc bench reports real, reproducible wall-clock timings for bench_fib.mus and bench_loop.mus against the Chapter 8 tree-walker, and this chapter names, in terms of this book's own code, exactly which parts of the tree-walker's design each number is paying for.

Exercises

Run musc bench on both benchmark files on your own machine and record your own numbers. They won't match this chapter's exactly; that's expected. Note which of the two benchmarks is proportionally slower relative to the other, on your hardware, and whether that matches this chapter's framing of what each one stresses.
bench_fib.mus uses fib(28). Change it to fib(30) (roughly 2.6x the calls of fib(28), following the Fibonacci call tree's own growth rate) and confirm the wall-clock time grows by roughly the same factor. This is the tree-walker behaving exactly as section 9.3 predicts: cost proportional to call count, with no per-call cost shrinking as the count grows.
Temporarily comment out call_function's two env_new allocations (you'll need to stub in a fixed, singly-reused Environment to make this compile, which will produce wrong answers for recursive calls, since every call would now share one frame) just to observe, with a profiler or even just wall-clock time, how much of bench_fib's total cost was allocation versus dispatch and pointer-chasing. Revert it afterwards: this exercise is about seeing the cost split, not about keeping a broken interpreter around.
Section 9.3 says bench_fib makes "roughly 832,000 calls" for fib(28). Derive that number yourself from the recurrence a naive Fibonacci's call count actually follows, and check it against your own instrumented count (a global counter incremented once per call_function call is enough).