Capstone: Benchmarking Wisp — Tree-Walking vs. Bytecode VM
Writing a Compiler/Interpreter: Advanced
Chapter 10 · Capstone: Benchmarking Wisp — Tree-Walking vs. Bytecode VM
Course 1 finished with a working tree-walking interpreter and one deliberate, unresolved promise: "the language stays the same. How it runs changes completely." This course spent nine chapters keeping that promise — a compiler, a stack-based VM, call frames, closures, garbage collection, classes. This capstone runs Course 1's own capstone program, unchanged, through everything Course 2 built, confirms it produces identical output, and then finally does the one thing Chapter 1 could only forward-reference: a real, honest, measured answer to whether the bytecode VM this course spent nine chapters building is actually faster.
Two Small, Honest Gaps — Closed Right Where They're Needed
Course 1's own capstone program uses >= (checking a task's priority against a threshold) and != (checking a linked-list node against nil). Neither exists in this course's own VM — Chapter 5 only ever built <, >, and ==, because nothing before now needed the other two. Two more comparison opcodes, OP_GREATER_EQUAL and OP_NOT_EQUAL, close both gaps — the same pattern this course has followed throughout: build what's needed when something concrete needs it, not before.
The Same Program, Verified Byte-for-Byte Identical
Course 1's own Task/UrgentTask/TaskNode/TaskQueue program — a linked-list task queue built entirely from classes, single inheritance overriding describe(), a closure factory (makeUrgencyChecker) capturing a threshold, and a higher-order function (countMatching) taking a callback — compiled here exactly as written, no changes, through this course's own Chapters 2-9 pipeline.
All tasks: / 4 / - URGENT: Fix the leak / - Read a book / - URGENT: Submit tax filing / - Water the plants / Critical tasks: / 2 / Priority >= 2: / 3 — matching Course 1's own published capstone output exactly. A freshly-built, faithful tree-walking interpreter, implementing Course 1's own Environment, WispFunction.bind(), and WispClass.find_method() exactly as documented and run against the identical AST, produces the identical output too. Three independent builds of the same language — Course 1's own original, a fresh from-scratch tree-walker built for this comparison, and this course's own bytecode VM — agree completely.
The Real Comparison: Scaling Up
Course 1's own capstone program runs once, on four tasks — too small to measure anything meaningful. A scaled version — 2,000 tasks, alternating Task and UrgentTask instances, then one countMatching pass using a real closure — exercises class instantiation, inheritance, property access, and closures at a scale actually worth timing.
Not Every Workload Behaves the Same Way
Chapter 1 of this course measured the opposite result — a single, deeply-nested arithmetic expression (201+ nodes), evaluated repeatedly, ran roughly 1.7× faster under the bytecode VM than under tree-walking. That finding and this chapter's own 0.49× result aren't in conflict — they're measuring genuinely different things.
sum = sum + i; i = i + 1;, repeated 4,000 times — runs to 0.0096s under tree-walking and 0.0207s under bytecode: a ratio of 0.465×, the tree-walker still faster. Chapter 1's own crossover was specifically about expression-nesting depth within a single evaluation — the tree-walker's own recursive dispatch cost compounding with how deep one expression tree goes. Repeating a shallow expression many times, in a loop, never triggers that same compounding; each iteration's own dispatch stays cheap regardless of how many times the loop runs.
| Workload shape | Result | Why |
|---|---|---|
| One deeply-nested expression (Chapter 1, 201+ nodes) | Bytecode ~1.7× faster | Tree-walking recursion depth compounds with nesting depth; the VM's flat instruction loop doesn't |
| A shallow loop body, repeated 4,000 times | Tree-walk ~2.1× faster | No nesting depth to compound against — each iteration's dispatch stays cheap either way, and the VM pays extra per-opcode overhead the tree-walker doesn't |
| 2,000 classes/closures/method calls (this chapter) | Tree-walk ~2.0× faster | Every property access and method call costs several bytecode instructions (OP_GET_PROPERTY, OP_CALL, frame setup) where the tree-walker needs one direct Python method call |
The honest conclusion isn't "bytecode is faster" or "bytecode is slower" — it's that performance in a Python-hosted VM depends on the specific shape of the work, and only one of the three shapes this course actually measured favors the design it spent nine chapters building. That's not a disappointing result to report; it's the same rigor this course applied to every other performance claim, from Chapter 1's own first honest finding onward, held to at the very end instead of quietly abandoned for a triumphant close.
Where Every Piece Came From
| Capstone component | Chapter |
|---|---|
| Reusing Course 1's own lexer, parser, and AST unchanged | Chapter 1 — "nothing about the front end needs to be rewritten" |
| Chunks, opcodes, the fetch-decode-execute loop | Chapter 2 |
| The single-pass compiler walking the same AST | Chapter 3 |
TaskQueue's own fields, this.head/this.count | Chapter 4 (globals/locals) — extended by Chapter 9 for instance fields |
The while loop walking the linked list; >=/!= closed here | Chapter 5 |
countMatching and makeUrgencyChecker's own recursive-safe calls | Chapter 6 |
tally's closure over count and checker | Chapter 7 |
Every Closure/Upvalue this program allocates | Chapter 8 (tracked; nothing here was ever actually swept, since the whole program stays reachable throughout) |
Task/UrgentTask/TaskNode/TaskQueue, inheritance, this, bound methods | Chapter 9 |
What This Course Doesn't Cover
Course 2's own VM inherits every scope boundary Course 1 already documented (no arrays, no string formatting, no super.method(), no break/continue, no static members, no standard library beyond print) and adds a few of its own: no line-numbered error reporting or multi-frame stack traces (Course 1's own Chapter 9 was never rebuilt at the bytecode level — a runtime error here is a plain Python exception, with none of Course 1's own [line N] attribution or call-stack trace), no automatic GC triggering (Chapter 8's own collector runs only when explicitly called, never on an allocation threshold the way a real VM would), and no bytecode-level optimizations a production VM would add (constant folding, inline caching, or clox's own OP_INVOKE fast path for method calls, which Chapter 9 named directly and chose not to implement). None of these are oversights — each is a deliberate line drawn so the course stayed teachable rather than becoming a production language runtime.
Closing Both Courses Together
Twenty chapters, two courses, one language. Course 1 built a real interpreter and measured its real limits — 163 levels of recursion, a visitor pattern that beat isinstance chains, a division-by-zero bug caught by actually testing it. Course 2 rebuilt the same language's runtime from the ground up and measured its own real limits in turn — 50,000 levels of recursion where Course 1 found 163, a genuine memory leak in the collector's own bookkeeping, a lightweight method-binding design 2.27× cheaper than the alternative, and, at the very end, an honest admission that the faster design isn't uniformly faster. Nothing in either course was asserted without being run first.
Course 2 Complete — Advanced Quick Reference
- Ch.1: naive same-language bytecode is slower at small scale, faster past ~200 nodes of deep nesting; double-dispatch tree-walking costs ~2× the recursion depth of a single function
- Ch.2: a real
Chunk(bytearray + constant pool + line array), 1.56× more compact than a tuple sketch; a verified 256-constant ceiling - Ch.3: a real compiler over Course 1's own AST — the compiler trusts the tree; precedence correctness is the parser's job alone
- Ch.4: globals (name-keyed, runtime) vs. locals (slot-indexed, compile-time) — a real but modest ~5% speed advantage for locals in Python
- Ch.5: backpatched jumps for
if/while; a verified 79/80-statement crossover proving 2-byte jump offsets are necessary, not cautious - Ch.6: explicit
CallFrames replace Python's own call stack — 50,000 levels of real recursion, resolving Course 1's own 163-level ceiling - Ch.7:
Upvalues that open (live) then close (a private copy) — reproducing, faithfully, the classic loop-closure bug real JavaScript has too - Ch.8: a real mark-and-sweep collector whose own bookkeeping list turned out to be the actual memory leak it exists to fix
- Ch.9: classes and methods via a lightweight
BoundMethodpair, structurally immune to Course 1's own found over-mutation bug - Ch.10: the same program, byte-for-byte identical across three implementations — and an honest answer, not the expected one, on which is faster