Commentary: bytecode-vm

One expression tree, three back ends. 4,095 AST nodes compile to 4,095 instructions and nothing gets faster — while a back end with no opcodes, no stack and no dispatch loop beats every bytecode variant on the page. A study guide for vm.py.

cd bytecode-vm
python3 demo.py            # all ten sections (§6) -- about 20s
python3 demo.py 2 7        # just the headline count and the load-bearing line
python3 test_vm.py         # 18 tests, 50 assertions, <1s

1. Orientation

This toy takes one expression tree and runs it three ways:

• evaluate(tree, env) — walk the tree, one Python call per node.
• compile_expr(tree) → a flat array of opcodes, run by vm_run — the classic dispatch loop over postfix bytecode.
• closure_compile(tree) — the same tree compiled to nested closures: no opcodes, no stack, no dispatch loop at all.

Nothing else differs. The tokenizer is shared, the parser is shared, the tree object is the same object, both variable lookups go through the same dict. When two back ends disagree about anything, there is exactly one place the disagreement can have come from.

The backlog entry for this toy promised "the same program, now runs as a dispatch loop over opcodes instead of walking a tree." That is a restatement of the definition, and it turns out to be worth almost nothing:

By the end you should be able to:

• say precisely what compiling to bytecode does and does not remove, and why the answer is "nothing" for a straight-line expression (§6.1);
• point at the one line in the compiler whose swap produces a program of identical length, identical opcode histogram and a wrong answer — and say why nothing downstream can catch it (§6.6);
• name the two sizes at which the dispatch loop stops being worth anything: operations too expensive (§6.7) and programs too small (§6.8);
• give the three reasons compilers really emit an instruction stream, none of which is the dispatch loop (§6.4, §6.5, §8).

The measurement contract, up front, because half this page is numbers. Counts (4,095, 203 / 400, PUSH -533) are exact, come from a seeded generator, and are byte-identical on every run — test_vm.py asserts them. Timings are secondary: minimum of 21 interleaved trials of 30 executions, quoted with their run-to-run range. Where a ratio moves more than the effect it is measuring, this page says so and prints the scatter rather than the tidiest row (§6.7).

2. The problem this mechanism exists to solve

You have a tree. Something has to consume it.

The obvious consumer is a recursive function, and it works: evaluate is 18 lines and needs no other machinery. But a tree is a graph of heap objects, so walking it means chasing a pointer per node, making a Python call per node, and asking "what kind of node is this?" every single time — the same question, re-asked on every execution of the same program, for the lifetime of the program.

Compiling is the bet that you can ask those questions once and keep the answers in a form that is cheaper to consume. Every real language runtime takes that bet, and it buys four different things that get bundled under one word:

• Dispatch that is cheaper per operation. The tree's isinstance chain becomes an integer compared against a small set of constants. This is the one everybody names, and (§6.2) it is the smallest of the four.
• An intermediate representation you can transform. A flat array (or the tree just before it) is a data structure an optimiser can rewrite. This is where operations actually disappear — §6.5 turns 4,095 instructions into 1.
• A form you can ship. .pyc, .class, .beam: an instruction stream is serialisable in a way that a graph of closures or a parse tree is not. The toy does not do this, and §8 says what it costs.
• A loop small enough to write in another language. The interpreter of a flat opcode array is one function with one switch. That function can be C — §6.4 hands our exact program to CPython's own VM and it runs 13.7× faster than our Python loop over the same 4,095 instructions.

The competing goals that make more than one design defensible:

• Speed of the loop versus portability of the loop. The fastest dispatch techniques (computed goto, direct threading) are not portable C. Lua's authors chose the slow, portable one on purpose: "Lua cannot use several tricks commonly used by interpreters, such as direct threaded code. Instead, it uses a standard while–switch dispatch loop."
• Fewer, fatter instructions versus more, simpler ones. A stack machine needs no register allocator and has tiny instructions; a register machine needs both and executes far fewer of them (§7.4 quotes Lua's 11 → 4).
• A structure that names its parts versus a structure that is a flat array. This is the trade this toy is really about. Bin has fields called left and right; postfix code has "the value two pushes ago". The names are what the checker would have checked, and once they're gone, an operand order bug is a plausible wrong number rather than an error (§6.6).

3. Background you need

The two starred rows carry the result. Postfix order is the property the compiler must get right and nothing downstream can verify — it is where §6.6's 203 wrong answers come from. Dispatch is the thing compiling is supposed to make cheap, and measuring it honestly is what turns the recorded aha inside out.

4. The mental model

One tree, three consumers. The tree is the fixed point of the whole page:

The flattening, in one picture. Postfix means operands first, operator last, and the stack is what remembers the operands between the two:

And the identity that the headline rests on, which is visible from the shape of the compiler rather than from any measurement:

A full binary tree with L leaves has L − 1 internal nodes, so 2 × L − 1 nodes altogether. With L = 2,048 that is 4,095 — 2,048 PUSH/LOAD and 2,047 arithmetic instructions. The tree-walk makes 4,095 calls. The VM executes 4,095 instructions. Nothing was removed; the work was re-packaged.

5. Reading the source

5.1 The compiler is a post-order walk that appends

def compile_expr(node, fold=False):
    """AST -> (code, consts, names). One instruction per AST node, always:
    `len(code) == count_nodes(node)` for every tree this can be handed."""
    if fold:
        node = fold_constants(node)
    code, consts, names = [], [], []
    seen = {}

    def intern(pool, key, value):
        """A constant pool and a name table -- CPython's co_consts/co_names.
        The key carries the type, so 1 and Fraction(1) stay two constants."""
        if key not in seen:
            seen[key] = len(pool)
            pool.append(value)
        return seen[key]

    def emit(node):
        if isinstance(node, Num):
            key = ("const", type(node.value), node.value)
            code.append((PUSH, intern(consts, key, node.value)))
        elif isinstance(node, Var):
            code.append((LOAD, intern(names, ("name", node.name), node.name)))
        elif isinstance(node, Neg):
            emit(node.operand)
            code.append((NEG, 0))
        else:
            emit(node.left)     # THE LINE: left before right, and nothing
            emit(node.right)    # downstream can tell if you swap them
            code.append((BINOP[node.op], 0))

    emit(node)
    return code, consts, names

Compare emit with evaluate (vm.py:160–176) and notice that they are the same function. Both recurse into the children first and act on the parent afterwards; the only difference is that one computes a value and the other appends an instruction. That is the whole of compilation for a straight-line expression: a post-order walk whose visit is append instead of apply.

This is also why the count identity is exact rather than approximate. Each of the four branches appends exactly one instruction and recurses into exactly the children that node has, so len(code) == count_nodes(node) is a structural property of the code, not a measurement. §6.1 measures it anyway, over 2,000 programs, because "obviously true from reading the code" is how three wrong claims got into an earlier toy in this repo.

intern is a whole production concept in three lines. Instructions are (opcode, arg) pairs where arg is an index, not a value, so the code array stays uniform and the values live in a side table. That is exactly CPython's co_consts / co_names split, where LOAD_CONST(consti) "pushes co_consts[consti] onto the stack". The key carries type(value) because otherwise 1 and Fraction(1) and 1.0 would collapse into one pool entry — which would quietly change what §6.7 is measuring, since that section runs the identical program with the literals rebuilt as bignums and as Fractions.

fold=True is one line, and it is a tree rewrite, not a code rewrite. The optimiser never sees an instruction. That is §5.3.

5.2 The dispatch loop, and everything it does not check

def vm_run(code, consts, names, env):
    """The dispatch loop. No step counter inside: the code is straight-line,
    so instructions executed is exactly `len(code)` -- which demo.py checks
    with a counted copy rather than assuming."""
    stack = []
    push = stack.append
    pop = stack.pop
    pc, n = 0, len(code)
    while pc < n:
        op, arg = code[pc]
        pc += 1
        if op == PUSH:
            push(consts[arg])
        elif op == LOAD:
            push(env[names[arg]])
        elif op == ADD:
            b = pop()
            push(pop() + b)
        elif op == SUB:
            b = pop()
            push(pop() - b)
        elif op == MUL:
            b = pop()
            push(pop() * b)
        elif op == DIV:
            b = pop()
            push(pop() / b)
        else:
            push(-pop())         # NEG, the one opcode that pops just one
    return stack[-1]

Four decisions worth the ink.

b = pop() then pop() - b. The second operand comes off the stack first, so the subtraction has to be written "backwards" to come out forwards. This is the mirror image of §5.1's emit(node.left) before emit(node.right), and the two have to agree. Nothing enforces the agreement: they are two lines in two functions, and the only thing connecting them is that someone thought about it. §6.6 is what happens when someone doesn't.

push = stack.append outside the loop. Binding the two methods once instead of looking them up 4,095 times is worth having — and it is precisely the fixed cost that makes the VM lose to the tree-walker on a 3-instruction program (§6.8). An optimisation whose setup dominates at n = 3 is a nice small demonstration that "faster" is a statement about a size.

The order of the if/elif chain is itself an optimisation. PUSH and LOAD are tested first, and they are 2,048 of the 4,095 instructions in the demo program — every leaf. Move the four arithmetic cases to the front of the chain and the same program, same instructions, runs 1.05×–1.09× slower across three runs (chain_order.py). Read that against §6.2's headline: merely reordering the comparisons moves about half as much time as compiling to bytecode at all does.

There is no verifier, and there cannot be one here. The loop never asks whether the stack has two values before SUB, never asks whether the value it pops is the operand the compiler meant, and ends with stack[-1] without checking that exactly one value is left. A real stack VM does check: the JVM specification spends its entire §4.10 on verifying class files by type checking and type inference before a method is allowed to run. §6.6 shows why: the failure mode it prevents is not a crash.

5.3 The folder is a separate pass, and it is a compiler containing an interpreter

def fold_constants(node):
    """A pass over the TREE, before any code exists: every subtree with no
    variable in it collapses to one `Num`. The only thing here that changes
    how many operations there are, and a separate pass on purpose -- fold and
    emit in one recursion and a node whose left operand folded appends that
    operand's PUSH *after* the right subtree's code (demo.py, section 7).
    """
    if isinstance(node, (Num, Var)):
        return node
    if isinstance(node, Neg):
        inner = fold_constants(node.operand)
        return Num(-inner.value) if isinstance(inner, Num) else Neg(inner)
    lhs, rhs = fold_constants(node.left), fold_constants(node.right)
    if isinstance(lhs, Num) and isinstance(rhs, Num) and not (
            node.op == "/" and rhs.value == 0):
        return Num(evaluate(Bin(node.op, lhs, rhs), {}))   # a compiler that
    return Bin(node.op, lhs, rhs)                          # contains a walker

It returns a tree, not code. That is the load-bearing structural decision of this file, and it is worth more than it looks. Because folding happens before emit runs, a folded node cannot possibly emit its operands in the wrong order — there is no "half-folded node" for emit to mishandle, only a Num where a subtree used to be. §6.6 measures the alternative: the one-pass version, which is the obvious way to write it and is wrong on 203 of 400 programs.

It also keeps the identity intact rather than breaking it. compile_expr still emits exactly one instruction per node; folding changed the tree, from 4,095 nodes to 1. Nothing special-cases anything.

evaluate(Bin(node.op, lhs, rhs), {}) — the folder computes the constant by building a two-operand tree and handing it to the tree-walking interpreter. This is not a shortcut; it is what constant folding is. Wikipedia's definition — "recognizing and evaluating constant expressions at compile time rather than computing them at runtime" — has an interpreter hiding inside the words "evaluating at compile time". Every optimising compiler contains a small implementation of its own language's semantics, and every disagreement between that copy and the real one is a miscompilation.

The / guard is where an optimiser meets a semantics question. 1/0 must not fold, because folding it would move a run-time ZeroDivisionError to compile time, and this compiler has no way to report one. Real compilers hit the same wall with overflow, with floating-point rounding modes, and with anything that can trap: GCC and LLVM will not fold an operation whose exception behaviour they would have to reproduce. test_vm.py pins it — 1/0 still compiles to three instructions with folding on.

5.4 The back end with no opcodes

def closure_compile(node):
    """The same tree as nested closures: no opcodes, no stack, no dispatch
    loop. The tree's shape is baked into the closures' call graph -- and this
    beats every bytecode variant in the fairness grid (demo.py, section 3)."""
    if isinstance(node, Num):
        value = node.value
        return lambda env: value
    if isinstance(node, Var):
        name = node.name
        return lambda env: env[name]
    if isinstance(node, Neg):
        inner = closure_compile(node.operand)
        return lambda env: -inner(env)
    lhs, rhs = closure_compile(node.left), closure_compile(node.right)
    if node.op == "+":
        return lambda env: lhs(env) + rhs(env)
    if node.op == "-":
        return lambda env: lhs(env) - rhs(env)
    if node.op == "*":
        return lambda env: lhs(env) * rhs(env)
    return lambda env: lhs(env) / rhs(env)

Twenty-one lines, and it is the fastest thing on the page (§6.2). It is the same post-order walk again — third time — but the visit builds a closure instead of appending an instruction or computing a number.

What it removes is not the dispatch chain, it is the fetch and decode. isinstance(node, Num) runs once per node at compile time, and after that the node's kind is encoded in which lambda exists. At run time there is no opcode to look up, no tuple to unpack, no program counter to advance, and no comparison to make: only calls. The family name for this is subroutine threading, "a series of machine-language 'call' instructions" instead of a loop that jumps — Python's version is a series of CALLs instead of a while.

The reason this is in the shipped toy rather than in a footnote is that it is the single most damaging measurement to the naive story. Without it the page says "bytecode is a bit faster"; with it the page says the dispatch loop is the wrong shape in this language, and directs your attention to the three things compiling actually bought.

5.5 The harness, because fairness is the load-bearing methodology

def bench(fns, reps=REPS, trials=TRIALS, raw=False):
    """Time several candidates against each other, INTERLEAVED: every trial
    runs all of them, so a busy neighbour process or a clock-speed change
    lands on all candidates rather than on whichever ran first. Keep each
    candidate's minimum -- noise can only ever make a sample slower.

    `raw=True` returns the per-trial samples instead, so a caller measuring a
    DIFFERENCE between two back ends can subtract within each trial (§6).
    """
    for _ in range(3):
        for fn in fns:
            fn()
    samples = [[] for _ in fns]
    for _ in range(trials):
        for i, fn in enumerate(fns):
            start = time.perf_counter()
            for _ in range(reps):
                fn()
            samples[i].append((time.perf_counter() - start) / reps)
    return samples if raw else [(min(s), statistics.median(s)) for s in samples]

The effect being measured is about 10%. On a machine running other jobs, the noise is bigger than that, and the first version of this harness — time back end A for 11 trials, then time back end B — produced runs in which the bytecode VM came out at 1.155× and runs in which it came out at 0.926×, including one where it lost to the tree-walker. Nothing about the code changed between them.

Three things fix it, and each is a claim the rest of the page depends on:

• Interleave. All candidates are timed inside every trial, so a busy neighbour or a clock-frequency change lands on all of them.
• Take the minimum, not the mean. Noise is one-sided: interference can only make a sample slower, never faster. The minimum is the closest sample to "the machine with nothing else on it".
• Measure a difference as a difference. §6.9's crossover divides by tree − vm, a small number left over from two large ones. Subtracting within each trial and taking the median of the differences moved that number from a range of 12–87 to a range of 17.6–25.2 across runs.

The rest of the fairness argument lives in the demo's other functions and is worth stating explicitly, because the entire aha depends on it:

• The same tree object. Every back end in §6.2 consumes the object returned by one parse().
• The same operand types. convert_tree (demo.py:317–328) rebuilds the literals too when §6.7 swaps in bignums or Fractions. Without it the tree-walker would be adding ints to Fractions while the VM added Fractions to Fractions, and the "boundary" would have been measuring coercion.
• The same variable lookup. evaluate does env[node.name]; vm_run does env[names[arg]]. Both are a dict lookup by string. Resolving names to slots is measured separately, as its own row.
• The generator uses + and - only. With * in the mix, a 2,048-leaf expression evaluates to a 60-digit bignum and the timing becomes a measurement of CPython's bignum arithmetic rather than of either interpreter — which is exactly the effect §6.7 then exploits deliberately.
• The tree-walker gets its best form. §6.2's second row replaces the isinstance chain with dict dispatch on type(node). If a strawman tree-walker were doing the work, that row would show it.
• Every row asserts its value. The value ok column is fn() == want, computed after timing.

5.6 The bug that shipped

    def emit(node):
        if isinstance(node, Num):
            return node.value
        if isinstance(node, Var):
            code.append((LOAD, intern(names, ("name", node.name), node.name)))
            return None
        if isinstance(node, Neg):
            value = emit(node.operand)
            if value is not None:
                return -value
            code.append((NEG, 0))
            return None
        lhs = emit(node.left)
        rhs = emit(node.right)
        if lhs is not None and rhs is not None:
            return _OPS[node.op](lhs, rhs)
        if lhs is not None:
            code.append((PUSH, const(lhs)))
        if rhs is not None:
            code.append((PUSH, const(rhs)))
        code.append((BINOP[node.op], 0))
        return None

This is the one-pass constant folder: fold and emit in a single recursion, returning a value when the subtree was constant and None when it emitted code. It is the obvious design — it saves a pass, it saves an allocation, and it reads fine.

Follow the two if ... is not None appends at the bottom. emit(node.left) is called first, and if the left subtree was constant it emits nothing and returns a value. Then emit(node.right) runs and appends the right subtree's code. Only afterwards does the left operand's PUSH get appended — after the code it was supposed to precede. The operands reach the VM reversed.

This is not a hypothetical. It is what the prototype for this toy actually did, and it was caught only by diffing the VM's answers against the tree-walker's. §6.6 measures it.

6. The demo, and what it proves

python3 demo.py, whole output reproduced across the subsections below, from one run.

6.1 One program, two back ends, and the count that is the point

Where 4,095 comes from. The generator builds an expression with exactly 2,048 leaves. Every internal node of a binary tree has two children, so L leaves imply L − 1 internal nodes and 2 × L − 1 = 4,095 nodes in total. The compiler's opcode histogram confirms the split exactly (derive.py):

1,026 + 1,022 = 2,048 leaves; 1,058 + 989 = 2,047 operators; together 4,095. The tree-walk's 4,095 is one evaluate call per node, counted by an instrumented copy. The VM's 4,095 is counted by an instrumented copy of the loop, and it equals len(code) because the code is straight-line: no jumps, so every instruction runs exactly once.

The identity is not a property of this program. Over 2,000 seeded random programs, max |len(code) − count_nodes(tree)| is 0 (§6.10's transcript), and test_vm.py asserts it.

stack left over at halt: 1. The stack is a scratchpad, and a correct program leaves exactly the answer on it. Its maximum depth over this 4,095 instruction program is 17 (derive.py) — the program's operands, at peak, need seventeen slots, which is the tree's depth expressed as a number the compiler could have written into the code object. (CPython does exactly that: co_stacksize.)

So compiling this tree performed 4,095 operations and produced a program that performs 4,095 operations. That is the whole answer to "what does compiling remove?", and it is nothing.

6.2 The wall clock, and what fairness costs

Across four full runs the ratios were (assembled from four captured transcripts, so this block is a summary rather than one run's stdout):

Read the first two rows before the rest. Giving the tree-walker dict dispatch instead of an isinstance/string chain is worth between −1% and +3% — nothing. The tree-walker is not slow because it was written badly, so the comparison below is not a strawman; it is slow because of what it is.

The bytecode rows: 1.07× to 1.17×. That is the entire cash value of compiling to bytecode here, and §6.1 already told us why it cannot be more — the two back ends do the same 4,095 operations. Per unit of counted work, 91.2 ns per node visit becomes 80.6 ns per instruction: about 10 ns saved per operation, on operations that cost roughly 80. Note also that the two "better" dispatch mechanisms — a dict of handler functions, resolving LOAD to an array slot — buy 2–3% between them, and that §5.2's counterfactual says reordering the same if/elif chain costs 5–8%. The dispatch mechanism is a rounding error dressed up as an architecture.

The last row is what makes this a toy rather than a definition. Compiling the same tree to nested closures — no opcodes, no stack, no program counter, no dispatch — is 2.19–2.41×, roughly twice the best bytecode form. The comparison is like for like: same tree, same env dict, same arithmetic, timed in the same interleaved trials, value asserted equal.

Why? Count what happens per node. The VM does an index (code[pc]), a tuple unpack, an increment, up to seven integer comparisons, and then the operation. The closure does one Python call and then the operation. Replacing the comparison chain with a dict of handlers (row 4) keeps the fetch, the decode and adds a call — and lands within 1% of row 3, which tells you the win in the closure row is not "dict beats chain". It is that there is no instruction to fetch or decode at all: the program counter has been replaced by the CPython call stack, and the opcode by which function object exists.

In a language where you cannot write the dispatch loop in C, compiling to bytecode is not merely a small win — it is the wrong shape.

6.3 The same dispatch loop, written in C

This is the same experiment as §6.2 with a third back end: hand the same expression to CPython's own compiler and run it under CPython's own VM. Every literal is rewritten to a variable first, so CPython's constant folder has nothing to fold and both VMs execute the same shape of program — which is why the instruction counts land two apart.

Where the 2 goes. CPython emits RESUME at entry and RETURN_VALUE at exit; the 4,095 in between are ours exactly. For x+y it emits RESUME, LOAD_NAME, LOAD_NAME, BINARY_OP, RETURN_VALUE where we emit LOAD, LOAD, ADD (derive.py). Same three instructions, same order, same stack discipline, plus a prologue and an epilogue.

7.5 ns per instruction against 91.1. Across four runs the C loop came out 13.22×–13.73× faster than the tree-walker, and 10.9×–12.1× faster than our Python loop running the identical algorithm over the identical program. That factor of ten or so is not a better algorithm. It is the same algorithm with the fetch–decode–dispatch step compiled to machine code instead of interpreted — plus, honestly, everything else CPython has put into that loop since 3.11: inline caching and per-instruction specialisation (PEP 659), which our loop has none of.

This is the first of the three real reasons to emit an instruction stream. A flat array of opcodes is a data structure whose interpreter is one small function — small enough that someone will rewrite it in C, or in assembly, or generate a threaded version of it. A tree-walker's "loop" is spread across your whole AST class hierarchy and cannot be lifted out. Ertl and Gregg's measurements on production interpreters put the stakes: indirect branches are "3.2%–13% of all executed instructions" and "consume more than half of the run-time in a number of configurations". Dispatch matters enormously — once the rest of your interpreter is fast enough for it to matter.

6.4 Constant folding, where operations actually disappear

8,189 characters of source. One instruction. The ratio 4,095 → 1 is exact and reproduces byte-identically; the timing ratio came out 820×–864× across five runs and is quoted as "order 1,000×" because it divides by a sub-microsecond number.

This is where the work actually went away, and note how: fold_constants never touched an instruction. It rewrote the tree from 4,095 nodes to 1 node, and compile_expr then did the same thing it always does — one instruction per node. The optimiser and the code generator never met.

The 25 is the interesting number. Replace one literal in that expression with x and folding leaves 25 instructions instead of 1. The variable is at depth 12 in the folded tree (derive.py), and a variable at depth d leaves exactly 2 × d + 1 nodes: the d ancestors on the path to the root, plus x itself, plus one folded constant sibling for each ancestor. 2 × 12 + 1 = 25, which is what the demo prints. One unknown value defeats 99.4% of the optimisation, and the shape of what survives is a path.

And what is lost. From PUSH -533 there is no way back to the 8,189 characters, to the 2,048 literals, or to the shape of the tree. This is the second real reason to have an IR — it is a thing you can transform — and it comes with the standard price: an optimised program is not the program you wrote, which is why debug builds exist and why every optimising compiler needs a separate mechanism (line tables, DWARF, co_positions) to answer "where in the source am I?"

6.5 The load-bearing line

emit(node.left) before emit(node.right). Swap those two statements and the compiler still produces a program of identical length, with an identical opcode histogram, perfectly stack-balanced, that returns a wrong number.

Derive 2-3-4 → 3. The tree is ((2 − 3) − 4). Correct: PUSH 2, PUSH 3, SUB → −1; PUSH 4, SUB → −5. Swapped, every node emits its right operand first: the outer node emits 4, then the inner node (which also swaps) emits 3, 2, SUB → 1; then the outer SUB computes 4 − 1 = 3.

Those are tiny-interpreter's two numbers. That toy gets −5 and 3 out of 2-3-4 by changing one line in the parser; this toy gets −5 and 3 out of 2-3-4 by changing one line in the compiler, with the tree held fixed. Same two values, same expression, two different stages — which is the cleanest possible statement of why this is a sequel and not a repeat.

They are not the same bug, and there is a witness that separates them (derive.py):

tiny-interpreter §6.7 shows that one pair of parentheses ends the associativity argument: 2-(3-4) evaluates to 3 under both parsers, because the grouping is written down. Against the codegen bug, the parentheses buy nothing — 2-(3-4) still goes wrong, 3 → −1. Grouping is a property of the tree, and the tree is not what broke.

The boundary of this bug, and it is the same shape as the other toy's. Over 400 random 12-leaf programs, the operand swap produces a wrong answer on 367 of 400 with + - in the mix — and on 0 of 400 when the operator set is + and alone (derive.py). Every commutative operator is blind to operand order, exactly as every associative operator is blind to grouping. If your language is all +, *, min, max and and, this entire class of compiler bug is unobservable.

6.6 The same bug, as it actually shipped

The swap in §6.5 is a deliberate edit. This one is a design: §5.6's one-pass folder, the obvious way to write constant folding, wrong on 203 of 400 programs — 50.75% — and crashing on 0.

The smallest witness is three characters and three instructions. 2-x compiles to PUSH 2 / LOAD x / SUB correctly and LOAD x / PUSH 2 / SUB under the one-pass folder. Both programs are three instructions long. Both push exactly two values and pop exactly two. Both leave exactly one value on the stack. One computes 2 − x = −1 and the other computes x − 2 = 1.

Zero crashes is the whole point. There is no stack underflow to catch, no type error, no assertion that could fire. A bytecode verifier of the kind the JVM specification defines in §4.10 — checking that the operand stack is consistent and that every instruction gets operands of the right type — would pass this program without complaint, because it is consistent and the types are right. The only thing wrong with it is that it computes a different function than the source did, and no property of the code array encodes what function the source denoted.

That is the deep version of §4's picture. Bin has a field literally named left. Postfix code has "whatever was pushed two pushes ago". Flattening a tree into a stack program converts a named relationship into a positional convention, and conventions are enforced by whoever remembers them.

What did catch it: a second implementation. The bug was found by running both back ends over the same programs and comparing answers — the same differential test §6.10 runs on every commit, 2,000 programs × 4 back ends. This is why the toy keeps a tree-walker at all after compiling: an interpreter you can trust is the oracle for the compiler you cannot.

6.7 Boundary 1 — make one operation expensive and the effect vanishes

The experiment holds everything fixed except the cost of one addition. Same tree shape, same 4,095 instructions in every row, same variables — only the literals and the environment are rebuilt, through convert_tree, so that both back ends see identical operand types.

Do not read the min column as a decaying sequence. Here is the same six rows across four consecutive full runs of demo.py (extracted from the four captured transcripts; this table is assembled, not a single run's output):

The 10,000-digit row is 1.100× in one run and 0.977× in the next. The 100,000-digit row is 0.963× in one run and 1.049× in another — the sign of the effect is not resolvable. The throwaway prototype this toy was designed from printed 1.063 → 1.047 → 1.029 → 1.016 for these four bignum widths, which reads like a clean monotone decay; an independent re-run of that same prototype gave 1.072 → 1.036 → 1.026 → 1.038, with the widest row coming back up. The tidy sequence was an artefact of one run, which is why this page prints four. What is real and reproducible is the first transition and the arithmetic behind it.

The arithmetic, which is the durable part. The dispatch saving measured in §6.2 is about 10 ns per operation, ~35–40 µs over 4,095 of them, and it does not grow when the operations get more expensive: deciding which operation to run costs the same whether the operation is a machine-word add or a 100,000-digit bignum add. So the ratio is

At 100,000-digit operands the entire dispatch saving is 40 µs out of 21,000 — 0.19% — which is far below the run-to-run noise of the measurement, and the table says so by scattering around 1.0 instead of decaying to it.

This is the boundary a reader can place their own system against. If your interpreter's opcodes do real work — a hash join, a regex match, a syscall, an HTTP request — the dispatch mechanism is irrelevant and compiling to bytecode for speed is cargo cult. Compiling to bytecode buys something exactly when the operations are cheap enough that deciding which one to run is comparable to running it. Every database engine that switched from tree-walking to compiled expressions did it for the per-tuple arithmetic, not for the joins.

6.8 Boundary 2 — make the program small and the VM loses

0.562× at three instructions, and that row is stable: 0.524×–0.568× across five runs. The compiled program is nearly twice as slow as walking the tree.

The arithmetic. At 4,095 instructions the VM costs 78.9 ns per instruction, so three instructions "should" cost 0.237 µs; it costs 0.30 µs. The residual, about 60 ns, is the loop's fixed setup — allocating the stack list, binding stack.append and stack.pop, computing len(code) — paid once per run whether the program is 3 instructions or 16,383. Over 4,095 instructions that 60 ns is 0.02% and invisible. Over 3 it is 20% of the runtime, and it is exactly the optimisation from §5.2 that causes the loss.

Between the two ends the advantage sits in a band around 1.05×–1.25× with no clean trend — the per-instruction cost creeps up with program size (68 ns at 255 instructions, 84 ns at 16,383) as the constant pool, the code array and the running value stop fitting in cache. The effect vanishes at both ends of the size range, and the middle is a 10–25% band, not a speedup you would rewrite an interpreter for.

6.9 Compile once, run many

Both back ends parse, so parsing cancels out of the comparison; the only extra cost the bytecode path carries is compile_expr, which is roughly an eighth of the parse at every size. The crossover is then

— the number of executions after which the compiled program has paid for its own compilation. Across five runs of this section: 10.7–11.4 at 64 leaves, 7.5–12.8 at 256, 17.6–25.2 at 2,048. Read it as order ten to twenty-odd executions, and note that this page will not give you an integer: the saving is a difference of two measurements each ±5%, so a headline of "the VM overtakes at exactly 41" would not survive re-running. (Before §5.5's paired differencing, the same 2,048-leaf number ranged from 12 to 87.)

What the number means in practice. Anything you run once — a config expression evaluated at start-up, a one-shot query filter — should not be compiled; you will spend more time compiling than you save. Anything in a loop crosses over almost immediately. This is the whole reason variables are in this toy's language: without them, "run the same program again" is a question with no point, because the answer cannot change.

6.10 Differential correctness

Two claims on this page are exact rather than approximate, and this is where they are checked over a space rather than on one program. 2,000 seeded programs with + - *, four back ends each (bytecode, folded bytecode, closures, dict tree-walk) against the tree-walker: 0 disagreements. The same 2,000 for the instruction-count identity: max |len(code) − count_nodes(tree)| = 0.

test_vm.py runs both sweeps, plus a table of expressions checked against Python's eval so that the oracle itself is not the toy.

7. Design decisions and roads not taken

7.1 What is actually new versus tiny-interpreter

That toy holds the evaluator fixed and varies the tree: one line in Parser.binary decides whether 2-3-4 is −5 or 3, and 324 of 432 expressions cannot tell. Its evaluator is explicitly the component with "no opinion".

This toy is the mirror-image experiment. The tree is fixed — literally the same object — and what consumes it varies. Three things follow that the earlier toy could not say:

• A second back end over the identical tree turns "the evaluator has no opinion" into a measurement: three consumers, one tree, identical answers, a 2.2× spread in cost.
• Postfix is a calling convention with no checker. tiny-interpreter has no stack. Here, operand order becomes a fact about the output that nothing downstream can recover — §6.5, and the parenthesis witness that separates the two bugs.
• A compile step can be wrong in ways parsing cannot, and an optimiser can change the count of operations — 4,095 → 1, which no parser change can do.

The language gains variables, because "compile once, run many times" is not a question you can ask about an expression whose answer never changes.

7.2 No control flow, no jumps, no backpatching

The obvious next feature is if and while, which brings the genuinely interesting compiler problem: the jump target is unknown when the jump is emitted, so you emit a placeholder and patch it later. It was left out on purpose, for three reasons.

It is a second mechanism — this toy is about the cost and the fragility of dispatch, and backpatching is about neither. It costs about 80 lines, pushing the core past the repo's 300-line ceiling. And, most concretely, it destroys the identity the headline rests on: with a loop, instructions executed is no longer len(code), so "4,095 nodes, 4,095 instructions, ratio 1.0000" stops being a sentence you can write. That is a good sequel toy, and it should be one: the offset is unknown when the jump is emitted.

7.3 Keeping the closure back end

Fifteen lines of vm.py exist only to lose the argument the toy is nominally making. They stay because without them this page reads "compiling to bytecode is 1.1× faster, the end", which is a fact about a benchmark; with them it reads "in this language the dispatch loop is the wrong shape, and here is what bytecode is actually for", which is a fact about compilers. A toy whose measurement only confirms the expected answer is a definition with a transcript.

7.4 A stack machine, not a register machine

The alternative IR names its operands: ADD R2, R0, R1 instead of "pop two, push one". It needs a register allocator, which is more machinery than this toy can hold, and it would break the one-instruction-per-node identity — which is precisely what makes register machines attractive. The Lua authors moved from a stack VM in Lua 4.0 to a register VM in Lua 5.0 and published the comparison: three statements that compile to 11 stack instructions compile to 4 register instructions, and they note "the switch to a register-based virtual machine allowed the generation of much shorter code". Fewer, fatter instructions means fewer trips around the dispatch loop — which is the right optimisation to reach for once you have established (as §6.2 does) that the loop itself is where the overhead lives.

7.5 Tuples of Python ints, not bytes

Real bytecode is bytes: CPython packs each instruction into two, so a code object is a bytes object that memory-maps and hashes and ships. Ours is a list of (int, int) tuples, which costs an object dereference and a tuple unpack per instruction — a real slowdown, and one that inflates the C-versus- Python gap in §6.3 somewhat. Packing to bytes would have bought speed and cost the reader a struct.unpack in the middle of the loop they are trying to read. The toy is optimising for the reader; §8 records the difference.

7.6 A constant pool, not inline operands

(PUSH, 3) could store the value 3 directly instead of an index into consts. Interning costs three lines and buys two things worth having: the code array stays uniform (every argument is a small int, which is what makes packing to bytes possible at all), and the reader meets co_consts/co_names, which is what they will find when they run dis.dis on their own code. It also makes §6.7 possible: the same program with Fraction literals is the same 4,095 instructions with a different pool.

7.7 Min-of-N interleaved, rather than timeit or an average

timeit disables the garbage collector and reports the total for a run; this page compares six back ends whose differences are ~10% on a loaded machine. §5.5 explains the three choices. The reason it belongs in "design decisions" is that the headline result — the closure row — would have been unmeasurable without them: the first harness produced runs where the bytecode VM lost to the tree-walker, purely from scheduling noise.

7.8 The front end is compressed on purpose

The tokenizer is one regex rather than the hand-rolled character loop of tiny-interpreter, and disasm lives in demo.py rather than in vm.py. Both are LOC-budget decisions with the same justification: the front end is not this toy's subject and is fully explained one page over, while a disassembler is presentation rather than mechanism. The core still lands at 291 lines, near the top of this repo's range, and the tokenizer and parser are 83 of them.

7.9 Left-associative only, and machine ints

Associativity is tiny-interpreter's entire subject and re-opening it here would split the aha in two — so Parser folds left at every level, full stop. And unlike that toy, this one uses machine integers rather than Fraction: the whole page is a timing comparison, and Fraction arithmetic is 3× slower than int arithmetic, which would have buried the effect being measured. §6.7 puts Fraction back deliberately, as a boundary condition rather than a default.

8. What's simplified vs. the real thing

No verifier. §6.6's wrong program would pass one, but real VMs still need one, for a different reason: they load code from untrusted sources. The JVM specification devotes §4.10 to verification by type checking and type inference, proving before execution that the operand stack is consistent at every instruction and that every instruction receives operands of the right type — because a hostile .class file that pops an empty stack must not be allowed to read whatever is under it. Our vm_run would happily do so.

No serialisation. The single most practical reason to emit an instruction stream is that you can write it to a file: .pyc, .class, .beam, .luac. A tree of Python objects and a graph of closures both die with the process. That is also the answer to "why not just use §6.2's winning closure back end everywhere": you cannot ship closures, you cannot hash them for a cache key, and you cannot write a C interpreter for them.

No jumps, no calls, no frames. Straight-line code only — no loops, no conditionals, no functions, so no call stack, no frame layout, no return addresses, no exception tables. That is the whole reason instructions executed equals len(code); in any real VM those two numbers have nothing to do with each other, and the hot loop is the only thing that matters.

No superinstructions, no threaded dispatch, no JIT. Production interpreters attack exactly the cost §6.2 measures: computed-goto direct threading, fusing common opcode pairs, and — CPython since 3.11 — quickening plus per-instruction specialisation, PEP 659's "speculatively specializing individual bytecodes". Our loop is the naive while/if-chain, which is what Lua ships for portability, and it is the entire reason the C row in §6.3 is 12× rather than 3×.

No register allocation, and no optimiser beyond folding. Real IRs get constant propagation, common-subexpression elimination, dead code elimination, strength reduction. This toy has the simplest member of that family, chosen because it is the one whose effect is countable (§6.4).

No source positions. After compiling there is no way to say where an error happened; PUSH -533 remembers nothing. Real compilers thread spans through every node and store line tables beside the code (CPython's co_positions, DWARF), which is often larger than the code itself, and which is why "optimised build" and "debuggable build" are different artefacts.

One environment, no scopes. LOAD reads a name from one dict. A real VM distinguishes locals (array slots, resolved at compile time), cells, globals and builtins, and the resolution rules are half the semantics of the language. §6.2's "LOAD by slot" row is a two-line taste of what that machinery buys: about 2%.

Timings are from a shared machine. Every number in §6 was captured while other processes were running. That is realistic rather than ideal, and the mitigation is stated (§5.5) and the spread published — but if you re-run this on an idle machine you should expect slightly larger ratios, not different conclusions.

9. Check yourself

10. Further reading

Every link below was fetched and confirmed live when this was written.

• Crafting Interpreters: A Virtual Machine — the chapter this toy is a 291-line replica of, and the best explanation of why a stack is the right scratch space: temporaries in nested expressions are last-in-first-out, because "whenever a number appears earlier than another, then it will live at least as long as that second one". Read its run() loop beside §5.2's, then read its later chapters for everything this toy leaves out — jumps, calls, closures, garbage collection.
• Ertl & Gregg, The Structure and Performance of Efficient Interpreters (JILP 5, 2003) — the measurement that sets the stakes for §6.3. Efficient interpreters "perform a large number of indirect branches (3.2%–13% of all executed instructions in our benchmarks)" and "these branches consume more than half of the run-time in a number of configurations we simulated". Our Python loop gets 13% from compiling; a real interpreter can lose half its run-time to the dispatch branch alone. That is the gap between a toy VM and a production one, quantified.
• The Implementation of Lua 5.0 (Ierusalimschy, de Figueiredo, Celes) — §7.4's source, and a rare paper that publishes the before-and-after instruction counts: the same three statements are 11 stack-machine instructions in Lua 4.0 and 4 register-machine instructions in Lua 5.0, because "the switch to a register-based virtual machine allowed the generation of much shorter code". It also justifies our naive dispatch: Lua "cannot use several tricks commonly used by interpreters, such as direct threaded code. Instead, it uses a standard while–switch dispatch loop" — for portability, in a shipped, fast language runtime.
• PEP 659: Specializing Adaptive Interpreter — part of what §6.3's C row is actually buying. CPython does not merely run the loop in C, it rewrites instructions at run time into type-specialised forms: "by speculatively specializing individual bytecodes, we can gain significant performance improvements without anything but the most local, and trivial to implement, de-optimizations". Read it as the answer to "what would I do next, if the dispatch loop were where my time went?"
• Python: dis — Disassembler for Python bytecode — the real version of §5.1's constant pool and §6.3's comparison. LOAD_CONST(consti) "pushes co_consts[consti] onto the stack", which is our PUSH with the pool it interns into. Note also the warning that makes §8's serialisation point concrete: "Bytecode is an implementation detail of the CPython interpreter. No guarantees are made that bytecode will not be added, removed, or changed between versions."
• Wikipedia: Threaded code — the family §5.4's closure back end belongs to. Subroutine threading "consists of a series of machine-language 'call' instructions" rather than a dispatch loop that jumps, which is precisely what compiling a tree to nested closures does in Python. Worth reading for how many points there are on the spectrum between "walk the tree" and "emit machine code".
• Wikipedia: Constant folding — §6.4 in one page: "recognizing and evaluating constant expressions at compile time rather than computing them at runtime", plus the distinction from constant propagation that question 3's answer turns on. Its worked examples are the reason fold_constants refuses to touch 1/0.
• The Java Virtual Machine Specification, §4.10: Verification of class Files — the machinery §6.6 shows the limits of. An entire chapter of a language specification exists to prove, before a method runs, that its operand stack is consistent and its instructions receive correctly typed operands. Read it against this toy's 203 wrong answers, all of which would pass: verification guarantees the code is well-formed, never that it is the code you meant.