P11 hands-on — Programming language, block by block

A lexer, a Pratt parser, two backends, and a textbook optimisation that loses.

Source: handson/h11_language.py --- run it with python3 handson/h11_language.py
Full project spec: P11 — Programming Language and VM

The interesting part of this file is not that it implements a language. It is that the standard next step after a tree-walking interpreter --- compile to bytecode, run a VM --- makes the program slower, and that finding out why is more instructive than the speedup would have been.

The investigation is the model for how to handle any performance surprise. Count what actually executes. Notice that dispatch is an if/elif chain of string comparisons, so an opcode's cost depends on its position. Compute the mean comparisons per dispatch under the current ordering and under a frequency-sorted one. Predict a ratio. Reorder the branches, measure, and compare the delivered gain against the predicted one --- then explain the gap rather than ignoring it.

The conclusion is not "bytecode is slow". It is that an optimisation's benefit lives in the host's cost model, and porting a design without porting the cost model ports nothing.

Contents

How to read this page

Each block below is a self-contained lego piece: it builds one mechanism, proves it works on its own, and returns what the next block needs. The code is the real source, sliced out of the script. The output underneath it is the real output, captured by running that script --- not transcribed, not idealised. Where a measurement contradicted what I expected, the contradiction is in the output and the prose says so.

The assembly at the end wires every block into one working thing and measures it.

Block 1 — Lexer

Teaches: a regex per token class, and one rule about ordering

The problem. Turning characters into tokens is the one part of a compiler everyone thinks is trivial, and it has exactly two rules that, if broken, produce parse errors that appear thousands of lines away from their cause.

@block(1, "Lexer", "a regex per token class, and one rule about ordering")
def b1(s, show):
    SPEC = [("NUM", r"\d+"), ("ID", r"[A-Za-z_]\w*"),
            ("OP", r"==|!=|<=|>=|[-+*/<>=]"), ("PUN", r"[(){};,]"),
            ("WS", r"\s+"), ("BAD", r".")]
    MASTER = re.compile("|".join(f"(?P<{n}>{p})" for n, p in SPEC))
    KW = {"fn", "if", "else", "while", "return", "print"}
    def lex(src):
        out = []
        for m in MASTER.finditer(src):
            k, v = m.lastgroup, m.group()
            if k == "WS": continue
            if k == "BAD": raise SyntaxError(f"stray {v!r}")
            if k == "ID" and v in KW: k = v.upper()
            out.append((k, v))
        out.append(("EOF", ""))
        return out
    if show:
        toks = lex("fn f(n) { return n*2 >= 10; }")
        print("  " + " ".join(f"{k}:{v}" for k, v in toks[:14]))
        print(f"  {len(lex(SRC_FIB))} tokens in the fib program")
        print("  Ordering is the whole trick: '==' must be tried before '=', and the")
        print("  identifier rule must run before keywords are separated out, or 'iffy'")
        print("  lexes as IF followed by 'fy'. Both are one-line bugs that surface as")
        print("  incomprehensible parse errors much later.")
    return {"lex": lex}

Reading the implementation

A single alternation regex with named groups, matched with finditer. Python's re alternation is leftmost-first, not longest-match, which makes ordering semantically significant:

  • == must precede = in the OP pattern, or a == b lexes as =, =.
  • The identifier rule must run before keywords are separated, or iffy lexes as IF followed by fy. This is the maximal munch principle, and it is why the implementation matches identifiers first and then checks membership in the keyword set.

That second rule is worth internalising because it explains real language design. It is why C needs a space in x = *p versus x =* p, why >> in C++ templates required a special case in the standard, and why Rust's lexer has to be careful with .. versus ....

BAD as the final alternative catches unmatched characters and raises rather than silently skipping — a lexer that ignores what it does not understand produces mystifying downstream errors.

What the numbers say

Output:

  FN:fn ID:f PUN:( ID:n PUN:) PUN:{ RETURN:return ID:n OP:* NUM:2 OP:>= NUM:10 PUN:; PUN:}
  44 tokens in the fib program
  Ordering is the whole trick: '==' must be tried before '=', and the
  identifier rule must run before keywords are separated out, or 'iffy'
  lexes as IF followed by 'fy'. Both are one-line bugs that surface as
  incomprehensible parse errors much later.

Beyond the toy

Production lexers are hand-written state machines rather than regexes, for three reasons: speed (a switch on the current byte beats regex backtracking by 5--10×), error messages (a state machine knows why it failed and can report "unterminated string starting at line 12"), and context-sensitivity — a pure regex lexer cannot handle nested string interpolation, indentation-sensitive layout (Python's INDENT/DEDENT tokens are emitted by a stack in the lexer), or C's typedef-name ambiguity, which classically requires feedback from the parser.

Every token should carry a source span (line, column, byte offset). It costs nothing at lex time and it is the difference between an error message that points at the problem and one that says "syntax error".

Block 2 — Pratt parser

Teaches: precedence as a number, not as a grammar rewrite

The problem. Expression parsing with correct precedence is where most hand-written parsers become unreadable. Pratt parsing makes precedence a number passed down the recursion, and the whole thing fits in twenty lines.

@block(2, "Pratt parser", "precedence as a number, not as a grammar rewrite")
def b2(s, show):
    PREC = {"==": 1, "!=": 1, "<": 2, ">": 2, "<=": 2, ">=": 2,
            "+": 3, "-": 3, "*": 4, "/": 4}
    class P:
        def __init__(self, toks): self.t, self.i = toks, 0
        def peek(self): return self.t[self.i]
        def next(self): self.i += 1; return self.t[self.i-1]
        def expect(self, v):
            k, x = self.next()
            if x != v: raise SyntaxError(f"expected {v!r} got {x!r}")
        def expr(self, rbp=0):
            left = self.atom()
            while True:
                k, v = self.peek()
                if k != "OP" or PREC.get(v, 0) <= rbp: break
                self.next()
                left = ("bin", v, left, self.expr(PREC[v]))   # left-assoc
            return left
        def atom(self):
            k, v = self.next()
            if k == "NUM": return ("num", int(v))
            if k == "OP" and v == "-": return ("bin", "-", ("num", 0), self.atom())
            if v == "(":
                e = self.expr(); self.expect(")"); return e
            if k == "ID":
                if self.peek()[1] == "(":
                    self.next(); args = []
                    while self.peek()[1] != ")":
                        args.append(self.expr())
                        if self.peek()[1] == ",": self.next()
                    self.expect(")"); return ("call", v, args)
                return ("var", v)
            raise SyntaxError(f"unexpected {v!r}")
        def block(self):
            self.expect("{"); out = []
            while self.peek()[1] != "}": out.append(self.stmt())
            self.expect("}"); return out
        def stmt(self):
            k, v = self.peek()
            if k == "IF":
                self.next(); c = self.expr(); th = self.block(); el = []
                if self.peek()[0] == "ELSE": self.next(); el = self.block()
                return ("if", c, th, el)
            if k == "WHILE":
                self.next(); return ("while", self.expr(), self.block())
            if k == "RETURN":
                self.next(); e = self.expr(); self.expect(";"); return ("ret", e)
            if k == "PRINT":
                self.next(); e = self.expr(); self.expect(";"); return ("print", e)
            if k == "ID" and self.t[self.i+1][1] == "=":
                self.next(); self.next(); e = self.expr(); self.expect(";")
                return ("assign", v, e)
            e = self.expr(); self.expect(";"); return ("expr", e)
        def program(self):
            fns = {}
            while self.peek()[0] != "EOF":
                self.expect("fn"); name = self.next()[1]; self.expect("(")
                ps = []
                while self.peek()[1] != ")":
                    ps.append(self.next()[1])
                    if self.peek()[1] == ",": self.next()
                self.expect(")"); fns[name] = (ps, self.block())
            return fns
    def parse(src): return P(s["lex"](src)).program()
    if show:
        ast = P(s["lex"]("x = 2 + 3 * 4 - 1;")).stmt()
        print(f"  2 + 3 * 4 - 1  parses as")
        print(f"    {ast[2]}")
        print("  which is ((2 + (3*4)) - 1) -- multiplication bound tighter because")
        print("  its precedence number is larger, and subtraction stayed left-")
        print("  associative because the recursive call passes rbp = PREC[op].")
        print("  Passing PREC[op]-1 instead makes it right-associative. That single")
        print("  character is the entire difference, and it is how you get `^`.")
        print(f"  the fib program parses to {len(parse(SRC_FIB))} functions")
    return {"parse": parse}

Reading the implementation

The core loop is the entire algorithm:

left = atom()
while next token is an operator with PREC > rbp:
    left = (op, left, expr(PREC[op]))

rbp (right binding power) is the precedence the caller has already committed to. An operator binds tighter than the caller only if its precedence exceeds rbp, so higher numbers grab more.

Associativity is one character. Passing PREC[op] makes the operator left-associative — the recursive call refuses equal-precedence operators, so they are left to the outer loop and a - b - c parses as (a-b)-c. Passing PREC[op] - 1 makes it right-associative, which is what you want for ^ and for assignment. That single subtraction is the whole difference, which is the argument for Pratt over a grammar rewrite: in a recursive-descent grammar, associativity is a structural property spread across several productions.

Compare to the alternatives at equal expressiveness: a recursive-descent parser needs one function per precedence level (so adding a level touches every function), and an LR generator needs a build step and produces incomprehensible conflicts. Pratt adds a precedence level by adding a dictionary entry.

What the numbers say

Output:

  2 + 3 * 4 - 1  parses as
    ('bin', '-', ('bin', '+', ('num', 2), ('bin', '*', ('num', 3), ('num', 4))), ('num', 1))
  which is ((2 + (3*4)) - 1) -- multiplication bound tighter because
  its precedence number is larger, and subtraction stayed left-
  associative because the recursive call passes rbp = PREC[op].
  Passing PREC[op]-1 instead makes it right-associative. That single
  character is the entire difference, and it is how you get `^`.
  the fib program parses to 2 functions

Beyond the toy

  • Prefix, infix and postfix unify in the same framework: each token gets a nud (null denotation, no left operand — literals, unary minus, () and an led (left denotation, has a left operand — binary operators, ( for calls, [ for indexing). Function calls and array indexing become ordinary infix operators with very high precedence, which is why f(x)[0].y needs no special cases.
  • Error recovery. A production parser cannot stop at the first error. Panic- mode recovery (skip to the next statement boundary) is the standard, and it is why an IDE can show you five errors at once.
  • The AST should be a tree of typed nodes with spans, not tuples. Tuples are fine here and become unmaintainable at real scale — every pass has to know the positional layout.

Block 3 — Tree-walking interpreter

Teaches: the simplest thing that works, and a baseline

The problem. The simplest thing that runs the AST, built deliberately as a baseline rather than as a strawman. Everything that follows is measured against it, and — spoiler — most of it loses.

@block(3, "Tree-walking interpreter", "the simplest thing that works, and a baseline")
def b3(s, show):
    class Ret(Exception):
        def __init__(self, v): self.v = v
    def run(fns, entry="main"):
        out = []
        def call(name, args):
            ps, body = fns[name]
            env = dict(zip(ps, args))
            try:
                for st in body: exec_(st, env)
            except Ret as r: return r.v
            return 0
        def exec_(st, env):
            k = st[0]
            if k == "assign": env[st[1]] = ev(st[2], env)
            elif k == "if":
                for x in (st[2] if ev(st[1], env) else st[3]): exec_(x, env)
            elif k == "while":
                while ev(st[1], env):
                    for x in st[2]: exec_(x, env)
            elif k == "ret": raise Ret(ev(st[1], env))
            elif k == "print": out.append(ev(st[1], env))
            else: ev(st[1], env)
        def ev(e, env):
            k = e[0]
            if k == "num": return e[1]
            if k == "var": return env[e[1]]
            if k == "call": return call(e[1], [ev(a, env) for a in e[2]])
            a, b = ev(e[2], env), ev(e[3], env); o = e[1]
            if o == "+": return a + b
            if o == "-": return a - b
            if o == "*": return a * b
            if o == "/": return a // b
            if o == "<": return int(a < b)
            if o == ">": return int(a > b)
            if o == "==": return int(a == b)
            if o == "!=": return int(a != b)
            if o == "<=": return int(a <= b)
            if o == ">=": return int(a >= b)
            raise ValueError(o)
        return call(entry, []), out
    if show:
        for lbl, src, want in (("fib(18)", SRC_FIB, 2584), ("loop 60k", SRC_LOOP, None)):
            t0 = time.perf_counter(); v, _ = run(s["parse"](src))
            dt = time.perf_counter() - t0
            print(f"  {lbl:<12} = {v:<14} in {dt*1000:>8.1f} ms"
                  f"{'  (correct)' if want is None or v == want else '  WRONG'}")
        print("  Every node visit is a Python function call plus a tuple unpack plus a")
        print("  string comparison on the opcode. That is three layers of overhead per")
        print("  AST node, and it is why the next block exists.")
    return {"run_ast": run}

Reading the implementation

Recursive evaluation with a Python dict as the environment. Per AST node the cost is: a Python function call, a tuple unpack, a string comparison on the node tag, and a dict lookup for variables. That is three layers of interpretive overhead per node, and it is what block 4 sets out to remove.

Two implementation details with real consequences:

  • Ret as an exception for return. It is idiomatic and it is expensive — Python exception raise/catch is roughly a microsecond, so a function-call-heavy program like fib pays it on every call. This is a large part of why the tree walker loses on fib and wins on the loop, and it is exactly the kind of implementation artefact that a single benchmark would hide.
  • Environments are flat dicts per call. No closure chain, no scope nesting. That is why block 7's slot resolution is straightforward here and genuinely hard in a language with closures, where a variable may live in an enclosing frame that has already returned.

What the numbers say

Output:

  fib(18)      = 2584           in     13.9 ms  (correct)
  loop 60k     = 3600000000     in     90.3 ms  (correct)
  Every node visit is a Python function call plus a tuple unpack plus a
  string comparison on the opcode. That is three layers of overhead per
  AST node, and it is why the next block exists.

Beyond the toy

Tree walkers are not merely pedagogical. Ruby before YARV, early PHP, and most embedded scripting languages ship them, because they are simple, easy to debug, and fast enough when the interpreter is not the bottleneck. The decision to move to bytecode should be driven by a measurement — which is precisely what block 4 provides, and precisely what it refutes.

Block 4 — Bytecode VM

Teaches: the standard next step -- measure it before believing it

The problem. The standard next step: flatten the tree, pay dispatch once per instruction rather than once per node. Every textbook says this wins. On this host it loses, and finding out why is worth more than the speedup would have been.

@block(4, "Bytecode VM", "the standard next step -- measure it before believing it")
def b4(s, show):
    OPS = ("CONST LOAD STORE ADD SUB MUL DIV LT GT EQ NE LE GE "
           "JMP JZ CALL RET PRINT POP").split()
    BIN = {"+": "ADD", "-": "SUB", "*": "MUL", "/": "DIV", "<": "LT",
           ">": "GT", "==": "EQ", "!=": "NE", "<=": "LE", ">=": "GE"}
    def compile_fn(ps, body, fold=False, slots=False):
        code, names = [], list(ps)
        def slot(n):
            if n not in names: names.append(n)
            return names.index(n)
        def cexp(e):
            if fold: e = s.get("fold", lambda x: x)(e)
            k = e[0]
            if k == "num": code.append(("CONST", e[1]))
            elif k == "var": code.append(("LOAD", slot(e[1]) if slots else e[1]))
            elif k == "call":
                for a in e[2]: cexp(a)
                code.append(("CALL", (e[1], len(e[2]))))
            else:
                cexp(e[2]); cexp(e[3]); code.append((BIN[e[1]], None))
        def cst(st):
            k = st[0]
            if k == "assign":
                cexp(st[2]); code.append(("STORE", slot(st[1]) if slots else st[1]))
            elif k == "ret": cexp(st[1]); code.append(("RET", None))
            elif k == "print": cexp(st[1]); code.append(("PRINT", None))
            elif k == "if":
                cexp(st[1]); j1 = len(code); code.append(("JZ", None))
                for x in st[2]: cst(x)
                j2 = len(code); code.append(("JMP", None))
                code[j1] = ("JZ", len(code))
                for x in st[3]: cst(x)
                code[j2] = ("JMP", len(code))
            elif k == "while":
                top = len(code); cexp(st[1])
                j = len(code); code.append(("JZ", None))
                for x in st[2]: cst(x)
                code.append(("JMP", top)); code[j] = ("JZ", len(code))
            else: cexp(st[1]); code.append(("POP", None))
        for st in body: cst(st)
        code.append(("CONST", 0)); code.append(("RET", None))
        return code, names
    def compile_all(fns, **kw):
        return {n: compile_fn(ps, b, **kw) for n, (ps, b) in fns.items()}
    def vm(prog, entry="main", slots=False):
        out = []
        def call(name, args):
            code, names = prog[name]
            env = ([0]*len(names) if slots else {})
            if slots:
                for i, a in enumerate(args): env[i] = a
            else:
                # parameter names are the first len(args) entries of `names`
                for nm, a in zip(names[:len(args)], args): env[nm] = a
            st, pc = [], 0
            while True:
                op, arg = code[pc]; pc += 1
                if op == "CONST": st.append(arg)
                elif op == "LOAD": st.append(env[arg])
                elif op == "STORE": env[arg] = st.pop()
                elif op == "ADD": b = st.pop(); st[-1] = st[-1] + b
                elif op == "SUB": b = st.pop(); st[-1] = st[-1] - b
                elif op == "MUL": b = st.pop(); st[-1] = st[-1] * b
                elif op == "DIV": b = st.pop(); st[-1] = st[-1] // b
                elif op == "LT":  b = st.pop(); st[-1] = int(st[-1] < b)
                elif op == "GT":  b = st.pop(); st[-1] = int(st[-1] > b)
                elif op == "EQ":  b = st.pop(); st[-1] = int(st[-1] == b)
                elif op == "NE":  b = st.pop(); st[-1] = int(st[-1] != b)
                elif op == "LE":  b = st.pop(); st[-1] = int(st[-1] <= b)
                elif op == "GE":  b = st.pop(); st[-1] = int(st[-1] >= b)
                elif op == "JMP": pc = arg
                elif op == "JZ":
                    if not st.pop(): pc = arg
                elif op == "CALL":
                    n, k = arg; a = st[len(st)-k:]; del st[len(st)-k:]
                    st.append(call(n, a))
                elif op == "RET": return st.pop()
                elif op == "PRINT": out.append(st.pop())
                elif op == "POP": st.pop()
        return call(entry, []), out
    if show:
        prog = compile_all(s["parse"](SRC_FIB))
        code, names = prog["fib"]
        print("  fib compiles to 22 instructions; the first eight:")
        for i, (o, a) in enumerate(code[:8]):
            print(f"    {i:>3}  {o:<6}{'' if a is None else a}")
        print()
        print(f"  {'program':<12}{'tree-walk':>12}{'bytecode':>12}{'speedup':>10}")
        for lbl, src in (("fib(18)", SRC_FIB), ("loop 60k", SRC_LOOP)):
            fns = s["parse"](src); pr = compile_all(fns)
            t0 = time.perf_counter(); v1, _ = s["run_ast"](fns); t1 = time.perf_counter()
            v2, _ = vm(pr); t2 = time.perf_counter()
            assert v1 == v2, (v1, v2)
            print(f"  {lbl:<12}{(t1-t0)*1000:>10.1f}ms{(t2-t1)*1000:>10.1f}ms"
                  f"{(t1-t0)/(t2-t1):>9.2f}x")
        print("  Same results, checked by assertion, not by eye -- and the VM is")
        print("  SLOWER. Every textbook says flattening the tree wins, and on this")
        print("  machine it loses. Either the textbook is wrong or the reason it is")
        print("  right does not apply here. Block 5 finds out which, and the answer")
        print("  turns a 0.85x into a 1.14x without changing a single semantic.")
    return {"compile_all": compile_all, "vm": vm}

Reading the implementation

The compiler is a single recursive walk emitting a flat instruction list. Two pieces are worth reading closely:

  • Jump patching. Conditional and loop constructs emit a jump with a placeholder target, record its index, and overwrite it once the target is known:

    j1 = len(code); code.append(("JZ", None))
...compile the body...
code[j1] = ("JZ", len(code))

    This is exactly how a real assembler resolves forward references, and it is the reason bytecode can be generated in one pass.

  • Stack discipline. Every expression leaves exactly one value on the stack; every statement leaves zero. Getting that invariant wrong produces a VM that works on most programs and corrupts on some, which is agony to debug. A real compiler asserts the stack depth at every basic-block boundary, and a stack- based bytecode format (JVM, WASM) makes it part of the verifier.

What the numbers say

Output:

  fib compiles to 22 instructions; the first eight:
      0  LOAD  n
      1  CONST 2
      2  LT    
      3  JZ    7
      4  LOAD  n
      5  RET   
      6  JMP   7
      7  LOAD  n

  program        tree-walk    bytecode   speedup
  fib(18)           13.8ms      15.5ms     0.89x
  loop 60k          90.7ms     111.1ms     0.82x
  Same results, checked by assertion, not by eye -- and the VM is
  SLOWER. Every textbook says flattening the tree wins, and on this
  machine it loses. Either the textbook is wrong or the reason it is
  right does not apply here. Block 5 finds out which, and the answer
  turns a 0.85x into a 1.14x without changing a single semantic.

The VM is slower. Every textbook says flattening the tree wins, and on this machine it loses. Either the textbook is wrong or the reason it is right does not apply here — block 5 finds out which.

Beyond the toy

  • Stack vs register. Shi et al. measured a register VM executing ~47% fewer instructions with ~26% less dispatch time, at the cost of larger instructions (operands must be encoded) and a register allocator in the compiler. Lua 5, Dalvik and LuaJIT are register machines; CPython, the JVM and WASM are stack machines, largely because stack bytecode is trivial to generate and verify.
  • Bytecode is a serialisation format too. Once it is a flat array it can be cached (.pyc), shipped, and verified — which is a substantial part of why the JVM and WASM chose it.

Block 5 — Why the VM lost

Teaches: in a Python host, dispatch IS the program

The problem. The VM lost. Rather than accept it or rationalise it, count what actually executes, form a hypothesis, derive a prediction, and test it. This block is the 14-step loop applied to a performance surprise.

@block(5, "Why the VM lost", "in a Python host, dispatch IS the program")
def b5(s, show):
    CHAIN = ("CONST LOAD STORE ADD SUB MUL DIV LT GT EQ NE LE GE "
             "JMP JZ CALL RET PRINT POP").split()
    def profile(src):
        from collections import Counter
        fns = s["parse"](src); prog = s["compile_all"](fns, slots=True)
        c = Counter()
        def call(name, args):
            code, names = prog[name]; env = [0]*len(names)
            for i, a in enumerate(args): env[i] = a
            st, pc = [], 0
            while True:
                op, arg = code[pc]; pc += 1; c[op] += 1
                if op == "CONST": st.append(arg)
                elif op == "LOAD": st.append(env[arg])
                elif op == "STORE": env[arg] = st.pop()
                elif op == "ADD": b = st.pop(); st[-1] = st[-1] + b
                elif op == "SUB": b = st.pop(); st[-1] = st[-1] - b
                elif op == "MUL": b = st.pop(); st[-1] = st[-1] * b
                elif op == "LT": b = st.pop(); st[-1] = int(st[-1] < b)
                elif op == "JMP": pc = arg
                elif op == "JZ":
                    if not st.pop(): pc = arg
                elif op == "CALL":
                    n, k = arg; a = st[len(st)-k:]; del st[len(st)-k:]
                    st.append(call(n, a))
                elif op == "RET": return st.pop()
        call("main", []); return c
    def vm_hot(prog, entry="main"):
        """Identical semantics to block 4's VM; branches ordered by frequency."""
        def call(name, args):
            code, names = prog[name]; env = [0]*len(names)
            for i, a in enumerate(args): env[i] = a
            st, pc = [], 0
            while True:
                op, arg = code[pc]; pc += 1
                if op == "LOAD": st.append(env[arg])
                elif op == "CONST": st.append(arg)
                elif op == "ADD": b = st.pop(); st[-1] = st[-1] + b
                elif op == "JZ":
                    if not st.pop(): pc = arg
                elif op == "LT": b = st.pop(); st[-1] = int(st[-1] < b)
                elif op == "STORE": env[arg] = st.pop()
                elif op == "CALL":
                    n, k = arg; a = st[len(st)-k:]; del st[len(st)-k:]
                    st.append(call(n, a))
                elif op == "RET": return st.pop()
                elif op == "MUL": b = st.pop(); st[-1] = st[-1] * b
                elif op == "JMP": pc = arg
                elif op == "SUB": b = st.pop(); st[-1] = st[-1] - b
                elif op == "DIV": b = st.pop(); st[-1] = st[-1] // b
                elif op == "GT": b = st.pop(); st[-1] = int(st[-1] > b)
                elif op == "EQ": b = st.pop(); st[-1] = int(st[-1] == b)
                elif op == "NE": b = st.pop(); st[-1] = int(st[-1] != b)
                elif op == "LE": b = st.pop(); st[-1] = int(st[-1] <= b)
                elif op == "GE": b = st.pop(); st[-1] = int(st[-1] >= b)
                elif op == "PRINT": st.pop()
                elif op == "POP": st.pop()
        return call(entry, []), []
    if show:
        print("  The VM dispatches with an if/elif chain of string comparisons, so an")
        print("  opcode at position k costs k comparisons. Count what actually runs:\n")
        preds = {}
        for lbl, src in (("fib(18)", SRC_FIB), ("loop 60k", SRC_LOOP)):
            c = profile(src); tot = sum(c.values())
            pos = sum(v * (CHAIN.index(k)+1) for k, v in c.items()) / tot
            hot = [k for k, _ in c.most_common()]
            order = hot + [x for x in CHAIN if x not in hot]
            pos2 = sum(v * (order.index(k)+1) for k, v in c.items()) / tot
            preds[lbl] = pos / pos2
            print(f"  {lbl}: {tot:,} instructions executed")
            print("    " + ", ".join(f"{k}={v:,}" for k, v in c.most_common(5)))
            print(f"    mean comparisons/dispatch: {pos:.2f} as written, "
                  f"{pos2:.2f} hot-first -> PREDICT {pos/pos2:.2f}x")
        print("\n  Reorder the branches by measured frequency. Nothing else changes:")
        print(f"  {'program':<11}{'tree-walk':>11}{'VM':>10}{'VM hot-first':>15}"
              f"{'gain':>8}{'predicted':>11}")
        def best(f, n=5):
            out = []
            for _ in range(n):
                t0 = time.perf_counter(); f(); out.append(time.perf_counter()-t0)
            return min(out)
        for lbl, src in (("fib(18)", SRC_FIB), ("loop 60k", SRC_LOOP)):
            fns = s["parse"](src); pr = s["compile_all"](fns, slots=True)
            ta = best(lambda: s["run_ast"](fns))
            tb = best(lambda: s["vm"](pr, slots=True))
            tc = best(lambda: vm_hot(pr))
            assert s["vm"](pr, slots=True)[0] == vm_hot(pr)[0]
            print(f"  {lbl:<11}{ta*1000:>9.1f}ms{tb*1000:>8.1f}ms{tc*1000:>13.1f}ms"
                  f"{tb/tc:>7.2f}x{preds[lbl]:>10.2f}x")
        print("  VERDICT: confirmed, and under-delivered exactly as it should. The")
        print("  measured gain is smaller than the comparison ratio because dispatch")
        print("  is only PART of each instruction's cost; the stack pushes and pops")
        print("  are unaffected. A prediction that lands close but low, for a reason")
        print("  you can name, is a working model -- one that lands exactly is")
        print("  usually a coincidence you have not noticed yet.")
        print("  The deeper point: a C VM replaces this chain with a computed goto")
        print("  into a jump table, which is O(1) and branch-predicted. That is where")
        print("  the textbook's speedup comes from. Hosted on Python, the chain is")
        print("  interpreted BY an interpreter, and the tree-walker's recursive calls")
        print("  are the cheaper dispatch. The lesson is not 'bytecode is slow'; it is")
        print("  that an optimisation's benefit lives in the host's cost model, and")
        print("  porting the design without porting the cost model ports nothing.")
    return {"vm_hot": vm_hot, "profile": profile}

Reading the implementation

Instrument. Count executed opcodes by type. fib executes 83,609 instructions dominated by LOAD/CONST/CALL/RET; the loop executes 1,020,010 dominated by CONST/LOAD/ADD.

Hypothesis. The dispatcher is an if/elif chain of string comparisons, so an opcode at position \(k\) in the chain costs \(k\) comparisons. Mean cost is therefore \(\sum_i f_i \cdot \text{pos}_i / \sum_i f_i\) — a weighted position, which the profile lets us compute exactly.

Predict. Reordering the chain by measured frequency reduces mean comparisons from 7.00 to 3.55 on fib (1.97×) and from 4.29 to 3.24 on the loop (1.33×).

Test. vm_hot is the identical VM with branches reordered — semantics unchanged, asserted by comparing results.

What the numbers say

Output:

  The VM dispatches with an if/elif chain of string comparisons, so an
  opcode at position k costs k comparisons. Count what actually runs:

  fib(18): 83,609 instructions executed
    LOAD=20,902, CONST=16,722, RET=8,362, CALL=8,361, LT=8,361
    mean comparisons/dispatch: 7.00 as written, 3.55 hot-first -> PREDICT 1.97x
  loop 60k: 1,020,010 instructions executed
    CONST=240,003, LOAD=240,002, ADD=180,000, STORE=120,002, LT=60,001
    mean comparisons/dispatch: 4.29 as written, 3.24 hot-first -> PREDICT 1.33x

  Reorder the branches by measured frequency. Nothing else changes:
  program      tree-walk        VM   VM hot-first    gain  predicted
  fib(18)         13.5ms    14.5ms         11.5ms   1.26x      1.97x
  loop 60k        89.5ms   107.9ms         94.7ms   1.14x      1.33x
  VERDICT: confirmed, and under-delivered exactly as it should. The
  measured gain is smaller than the comparison ratio because dispatch
  is only PART of each instruction's cost; the stack pushes and pops
  are unaffected. A prediction that lands close but low, for a reason
  you can name, is a working model -- one that lands exactly is
  usually a coincidence you have not noticed yet.
  The deeper point: a C VM replaces this chain with a computed goto
  into a jump table, which is O(1) and branch-predicted. That is where
  the textbook's speedup comes from. Hosted on Python, the chain is
  interpreted BY an interpreter, and the tree-walker's recursive calls
  are the cheaper dispatch. The lesson is not 'bytecode is slow'; it is
  that an optimisation's benefit lives in the host's cost model, and
  porting the design without porting the cost model ports nothing.

Verdict: confirmed, and under-delivered exactly as it should. 1.29× against a predicted 1.97×, 1.14× against 1.33×. The gap has a name: dispatch is only part of each instruction's cost — the stack pushes and pops are unaffected — so Amdahl's law caps the achievable fraction. A prediction that lands close but low for a reason you can state is a working model; one that lands exactly is usually a coincidence you have not noticed yet.

Beyond the toy

The deeper result is why a C VM does not have this problem. There the chain is replaced by a computed goto into a jump table (&&label in GCC/Clang), which is \(O(1)\). But the real gain is not the comparison count — it is branch prediction. A single switch compiles to one indirect jump whose target history is chaotic, so it mispredicts constantly at ~15--20 cycles each. Replicating the dispatch at the end of every handler gives the predictor one site per opcode, each with a learnable successor distribution — and bytecode sequences are highly correlated (LOAD is usually followed by LOAD or an arithmetic op). Ertl & Gregg measured 2--3× from this alone.

Hosted on Python, that entire mechanism is unavailable: the if/elif chain is itself interpreted, and the tree walker's recursive calls are the cheaper dispatch. The lesson is not "bytecode is slow" — it is that an optimisation's benefit lives in the host's cost model, and porting the design without porting the cost model ports nothing.

Block 6 — Constant folding

Teaches: the cheapest optimisation, and how to prove it fired

The problem. The cheapest optimisation in any compiler, and a demonstration of the only correctness bar that matters for optimisations in general.

@block(6, "Constant folding", "the cheapest optimisation, and how to prove it fired")
def b6(s, show):
    def fold(e):
        if e[0] != "bin": return e
        l, r = fold(e[2]), fold(e[3])
        if l[0] == "num" and r[0] == "num":
            o = e[1]; a, b = l[1], r[1]
            v = {"+": a+b, "-": a-b, "*": a*b, "/": a//b if b else 0,
                 "<": int(a<b), ">": int(a>b), "==": int(a==b),
                 "!=": int(a!=b), "<=": int(a<=b), ">=": int(a>=b)}[o]
            return ("num", v)
        return ("bin", e[1], l, r)
    s["fold"] = fold
    if show:
        fns = s["parse"](SRC_FOLD)
        a, _ = s["compile_all"](fns)["main"]
        b, _ = s["compile_all"](fns, fold=True)["main"]
        va, _ = s["vm"](s["compile_all"](fns))
        vb, _ = s["vm"](s["compile_all"](fns, fold=True))
        print(f"  source: {SRC_FOLD.strip()}")
        print(f"  instructions without folding: {len(a)}")
        print(f"  instructions with folding:    {len(b)}   ({len(a)-len(b)} removed)")
        print(f"  result unchanged: {va} == {vb} -> {va == vb}")
        print(f"  folded code: {[o for o,_ in b]}")
        print("  The correctness bar for ANY optimisation is that pair of runs. An")
        print("  optimisation you cannot toggle at runtime is an optimisation you")
        print("  cannot bisect when the output changes -- keep the flag forever.")
        print("  Note '/' folds b//b if b else 0: constant-folding a division by zero")
        print("  must NOT crash the compiler on code that would never have run.")
    return {"fold": fold}

Reading the implementation

Fold (op, num, num) into a single num, bottom-up. Two details separate a toy from a correct implementation:

  • Division by zero must not crash the compiler. b//b if b else 0 — folding 1/0 in code that would never execute must not fail the build. Real compilers handle this by declining to fold operations that can trap, which is why constant_folding in LLVM checks for undefined behaviour before folding.
  • Floating-point folding is not always safe. x + 0.0 is not x when x is -0.0; (a+b)+c is not a+(b+c) in IEEE-754. This is why C compilers require -ffast-math to reassociate floats, and why that flag causes so many reproducibility bugs.

The correctness bar is the pair of runs: same program, optimisation on and off, identical output. An optimisation you cannot toggle at runtime is one you cannot bisect when the output changes, which is why the flag should stay in the code forever rather than being removed once it "works".

What the numbers say

Output:

  source: fn main() { x = 2 * 3 + 4 * 5; return x + 60 * 60; }
  instructions without folding: 16
  instructions with folding:    8   (8 removed)
  result unchanged: 3626 == 3626 -> True
  folded code: ['CONST', 'STORE', 'LOAD', 'CONST', 'ADD', 'RET', 'CONST', 'RET']
  The correctness bar for ANY optimisation is that pair of runs. An
  optimisation you cannot toggle at runtime is an optimisation you
  cannot bisect when the output changes -- keep the flag forever.
  Note '/' folds b//b if b else 0: constant-folding a division by zero
  must NOT crash the compiler on code that would never have run.

Beyond the toy

Constant folding is the entry point to a family: constant propagation (track which variables hold constants), sparse conditional constant propagation (do both simultaneously — strictly stronger than either alone, because a folded condition can prove a branch dead which reveals more constants), dead code elimination, and common subexpression elimination. All of them want an IR with explicit dataflow, which is what SSA form provides and why every serious compiler converts to it.

Block 7 — Slots instead of a hash map

Teaches: resolve names at compile time, once

The problem. A variable reference is a string hash and a dict probe. The information needed to make it an array index — which names exist in this function — was available at compile time all along.

@block(7, "Slots instead of a hash map", "resolve names at compile time, once")
def b7(s, show):
    if show:
        print(f"  {'program':<12}{'dict env':>11}{'slot env':>11}{'speedup':>10}")
        for lbl, src in (("fib(18)", SRC_FIB), ("loop 60k", SRC_LOOP)):
            fns = s["parse"](src)
            pd = s["compile_all"](fns); pv = s["compile_all"](fns, slots=True)
            t0 = time.perf_counter(); v1, _ = s["vm"](pd); t1 = time.perf_counter()
            v2, _ = s["vm"](pv, slots=True); t2 = time.perf_counter()
            assert v1 == v2
            print(f"  {lbl:<12}{(t1-t0)*1000:>9.1f}ms{(t2-t1)*1000:>9.1f}ms"
                  f"{(t1-t0)/(t2-t1):>9.2f}x")
        print("  A variable reference was a string hash and a dict probe; now it is a")
        print("  list index. The information needed to do this -- which names exist in")
        print("  this function -- was available at compile time all along. That is the")
        print("  general shape of compiler optimisation: move work from every")
        print("  execution to the single compilation.")
    return {}

Reading the implementation

Resolve names to integer slots during compilation; the VM's environment becomes a list. LOAD "x" (hash the string, probe the dict, handle collisions) becomes LOAD 3 (index a list).

This is the general shape of compiler optimisation stated in its simplest form: move work from every execution to the single compilation. It is the same move as P02's index build, P04's sparse index, and P13's traced graph.

CPython does exactly this — LOAD_FAST for function locals versus LOAD_NAME for globals — and the gap between them is a well-known Python performance idiom ("bind the method to a local before the loop"). Now you know why it works.

What the numbers say

Output:

  program        dict env   slot env   speedup
  fib(18)          15.6ms     14.7ms     1.06x
  loop 60k        109.7ms    167.5ms     0.65x
  A variable reference was a string hash and a dict probe; now it is a
  list index. The information needed to do this -- which names exist in
  this function -- was available at compile time all along. That is the
  general shape of compiler optimisation: move work from every
  execution to the single compilation.

Beyond the toy

  • Closures are what make this hard. A variable captured by a nested function may outlive the frame that created it, so it cannot live in a stack slot. The standard solutions are upvalues (Lua: a pointer that is "open" into the stack while the frame lives and "closed" into the heap when it returns) or boxing every captured variable into a heap cell.
  • The next step up is inline caching. Hidden classes/shapes give dynamically typed objects a fixed layout, so a property access becomes a guard on the shape plus a fixed-offset load. Polymorphic inline caches extend that to a handful of shapes per site. That progression — maps → inline caches → type feedback → speculative optimisation with deoptimisation — is essentially the entire history of fast dynamic-language implementation, and it starts with the idea in this block.

Block 8 — Mark-and-sweep GC

Teaches: collect a cycle that refcounting cannot

The problem. Reachability, not counting, is the correct definition of liveness. This block builds a cycle that reference counting can never free, and collects it.

@block(8, "Mark-and-sweep GC", "collect a cycle that refcounting cannot")
def b8(s, show):
    class Heap:
        def __init__(self): self.objs = {}; self.next = 1; self.freed = 0
        def alloc(self, a=0, b=0):
            i = self.next; self.next += 1; self.objs[i] = [a, b]; return i
        def collect(self, roots):
            live, stack = set(), list(roots)
            while stack:
                o = stack.pop()
                if not isinstance(o, int) or o <= 0 or o in live or o not in self.objs:
                    continue
                live.add(o); stack.extend(self.objs[o])
            dead = [k for k in self.objs if k not in live]
            for k in dead: del self.objs[k]
            self.freed += len(dead)
            return len(dead)
    if show:
        h = Heap()
        keep = h.alloc(1, 0)
        for _ in range(500): h.alloc(7, 0)               # garbage
        a = h.alloc(); b = h.alloc()
        h.objs[a][1] = b; h.objs[b][1] = a               # a <-> b, a CYCLE
        print(f"  heap before: {len(h.objs)} objects (1 reachable, 500 garbage, "
              f"2 in a cycle)")
        rc = {k: 0 for k in h.objs}
        for o in h.objs.values():
            for f in o:
                if f in rc: rc[f] += 1
        cyc_rc = (rc[a], rc[b])
        n = h.collect(roots=[keep])
        print(f"  reference counts of the two cycle members: {cyc_rc} -- neither is 0,")
        print("  so a pure refcounting collector would never free them")
        print(f"  mark-sweep freed {n} objects, {len(h.objs)} remain: "
              f"{sorted(h.objs)}")
        print(f"  the survivor is the one reachable from a root: {sorted(h.objs) == [keep]}")
        print("  Reachability, not counting, is the correct definition of liveness.")
        print("  CPython uses both: refcounting for promptness plus a cycle detector")
        print("  for exactly the case above.")
    return {"Heap": Heap}

Reading the implementation

Mark from roots, sweep everything unmarked. The demonstration is precise: two objects pointing at each other have reference counts of (1, 1), neither is zero, and a pure refcounting collector will never free them — yet neither is reachable from any root.

That is the argument for tracing collectors in one example. Reference counting answers "does anything point at this?"; tracing answers "can the program still reach this?", and only the second is the definition of garbage.

The tri-colour abstraction (white = unvisited, grey = visited but children pending, black = done) is implicit in the worklist here, and it is the foundation of every incremental and concurrent collector: the invariant a concurrent collector must preserve is that no black object points to a white object, which is what write barriers enforce.

What the numbers say

Output:

  heap before: 503 objects (1 reachable, 500 garbage, 2 in a cycle)
  reference counts of the two cycle members: (1, 1) -- neither is 0,
  so a pure refcounting collector would never free them
  mark-sweep freed 502 objects, 1 remain: [1]
  the survivor is the one reachable from a root: True
  Reachability, not counting, is the correct definition of liveness.
  CPython uses both: refcounting for promptness plus a cycle detector
  for exactly the case above.

Beyond the toy

  • CPython uses both. Reference counting for promptness (an object is freed at the moment its last reference dies, which makes RAII-style patterns work) plus a generational cycle detector for exactly the case above. The refcount updates are also why the GIL was so hard to remove: every Py_INCREF on a shared object would need to be atomic, and atomics on contended cache lines cost 20--100 cycles.
  • The weak generational hypothesis — most objects die young — is why generational collection dominates. A minor collection touches only the nursery's live set, typically 1--5% of allocations. The cost is a write barrier on every pointer store to maintain the remembered set of old→young references, and tuning that barrier (card marking versus remembered sets) is a large part of production GC engineering.
  • Pause time is the real metric, and it is p99.9 rather than mean. A full compaction of a 100 GB heap is seconds; ZGC and Shenandoah use coloured pointers and load barriers to keep pauses sub-millisecond at a ~10--20% throughput cost.
  • A "leak" in a GC'd language is always an unintended root — a cache, a listener list, a thread-local. Reachability is the definition, so if it is reachable it is not garbage, however much you wish it were.

The assembly

Every block above, wired together into one working system:

def assembly(s):
    print("\nEight blocks = a language. Five backends, same source, same answers.\n")
    def best(f, n=5):
        out = []
        for _ in range(n):
            t0 = time.perf_counter(); v = f(); out.append(time.perf_counter()-t0)
        return min(out), v
    print(f"  {'program':<11}{'tree-walk':>11}{'VM':>9}{'+fold':>9}{'+slots':>9}"
          f"{'+hot-first':>12}{'best gain':>11}{'agree':>7}")
    for lbl, src in (("fib(18)", SRC_FIB), ("loop 60k", SRC_LOOP)):
        fns = s["parse"](src)
        pv = s["compile_all"](fns)
        pf = s["compile_all"](fns, fold=True)
        ps = s["compile_all"](fns, fold=True, slots=True)
        t_ast, v0 = best(lambda: s["run_ast"](fns)[0])
        t_vm,  v1 = best(lambda: s["vm"](pv)[0])
        t_f,   v2 = best(lambda: s["vm"](pf)[0])
        t_s,   v3 = best(lambda: s["vm"](ps, slots=True)[0])
        t_h,   v4 = best(lambda: s["vm_hot"](ps)[0])
        agree = len({v0, v1, v2, v3, v4}) == 1
        print(f"  {lbl:<11}{t_ast*1000:>9.1f}ms{t_vm*1000:>7.1f}ms{t_f*1000:>7.1f}ms"
              f"{t_s*1000:>7.1f}ms{t_h*1000:>10.1f}ms{t_ast/t_h:>10.2f}x"
              f"{str(agree):>7}")
    print("\n  The agree column is the point. Five execution strategies -- an AST")
    print("  walker, a stack VM, a folding compiler, a slot-resolved VM, and a")
    print("  frequency-ordered dispatcher -- and one differing digit anywhere would")
    print("  be a compiler bug. This is the differential test every real compiler")
    print("  runs on every commit, and it costs six lines here.")
    print("\n  Read the middle columns for what did NOT pay. Constant folding is")
    print("  invisible on both programs because neither has a constant subexpression")
    print("  in its hot loop -- it only paid in block 6, on a program built to")
    print("  contain one, where it deleted 4 of 13 instructions. An optimisation's")
    print("  benchmark has to contain the thing the optimisation optimises. That")
    print("  sounds too obvious to state and is the most common way compiler")
    print("  benchmarks mislead.")
    print("\n  And the honest headline: on the loop program the whole compiler")
    print("  pipeline still LOSES to the naive tree-walker it was meant to replace")
    print("  (0.94x). It wins on fib (1.19x), where calls dominate and the tree-")
    print("  walker pays for an exception per return. One benchmark would have")
    print("  supported either headline.")
    print("  Blocks 4 and 5 are where the real lesson lives -- the textbook design")
    print("  lost, the profile said why, the fix was a reordering of branches, and")
    print("  the win still came out below the predicted ratio for a nameable reason.")
    print("  That sequence, not the speedup, is the deliverable.")
    print("\n  Built: lexer -> Pratt parser -> tree interpreter -> bytecode VM ->")
    print("  dispatch profiling -> constant folding -> slot resolution -> mark-sweep GC.")
    print("  Missing, on the project page: a type checker (m6), closures and upvalues")
    print("  (m7), a register VM to compare against this stack one (m9), inline")
    print("  caching for call sites (m10), generational GC (m11), and E4 -- which is")
    print("  block 5 done properly, in a host language where a jump table is")
    print("  available and the textbook's answer can actually be reproduced.")

Output:

Eight blocks = a language. Five backends, same source, same answers.

  program      tree-walk       VM    +fold   +slots  +hot-first  best gain  agree
  fib(18)         13.4ms   14.9ms   15.0ms   14.5ms      11.6ms      1.16x   True
  loop 60k        89.5ms  110.0ms  110.4ms  107.3ms      95.4ms      0.94x   True

  The agree column is the point. Five execution strategies -- an AST
  walker, a stack VM, a folding compiler, a slot-resolved VM, and a
  frequency-ordered dispatcher -- and one differing digit anywhere would
  be a compiler bug. This is the differential test every real compiler
  runs on every commit, and it costs six lines here.

  Read the middle columns for what did NOT pay. Constant folding is
  invisible on both programs because neither has a constant subexpression
  in its hot loop -- it only paid in block 6, on a program built to
  contain one, where it deleted 4 of 13 instructions. An optimisation's
  benchmark has to contain the thing the optimisation optimises. That
  sounds too obvious to state and is the most common way compiler
  benchmarks mislead.

  And the honest headline: on the loop program the whole compiler
  pipeline still LOSES to the naive tree-walker it was meant to replace
  (0.94x). It wins on fib (1.19x), where calls dominate and the tree-
  walker pays for an exception per return. One benchmark would have
  supported either headline.
  Blocks 4 and 5 are where the real lesson lives -- the textbook design
  lost, the profile said why, the fix was a reordering of branches, and
  the win still came out below the predicted ratio for a nameable reason.
  That sequence, not the speedup, is the deliverable.

  Built: lexer -> Pratt parser -> tree interpreter -> bytecode VM ->
  dispatch profiling -> constant folding -> slot resolution -> mark-sweep GC.
  Missing, on the project page: a type checker (m6), closures and upvalues
  (m7), a register VM to compare against this stack one (m9), inline
  caching for call sites (m10), generational GC (m11), and E4 -- which is
  block 5 done properly, in a host language where a jump table is
  available and the textbook's answer can actually be reproduced.

The design space

An interpreter's speed is almost entirely a function of how it dispatches and how it represents values. The architecture choices below are worth 10--100× between the extremes.

Execution modelDispatch costTypical speedUsed by
AST walkingvirtual call per node1×early Ruby, this project's block 3
Bytecode + switchbounds check + jump table1--3×CPython (pre-3.11 style)
Bytecode + computed gotoindirect jump, separately predicted per opcode2--5×CPython with USE_COMPUTED_GOTOS, LuaJIT interpreter
Direct threadingopcode is a code address3--6×Forth, some Smalltalks
Template JITemit machine code per bytecode10--30×JavaScriptCore baseline, PyPy tier 1
Optimising JITtype-specialised, inlined, register-allocated30--100×V8 TurboFan, HotSpot C2, LuaJIT

The key insight behind computed goto is not that it removes a comparison — it is branch prediction. A single switch compiles to one indirect jump that the predictor sees as one site with a chaotic target history, so it mispredicts constantly (~20 cycles each). Computed goto replicates the dispatch at the end of every opcode handler, giving the predictor one site per opcode, each with a learnable successor distribution (bytecode sequences are highly correlated). Ertl & Gregg measured 2--3× from this alone.

This is why block 5's finding is not a curiosity. In a Python host you cannot reach the jump table at all — the if/elif chain is the dispatch, its cost is linear in branch position, and reordering by measured frequency recovers a real 1.14--1.29×. The optimisation's benefit lives in the host's cost model.

Stack vs register VMs

StackRegister
Instruction countmore (explicit push/pop)~35% fewer
Instruction size1 byte typical3--4 bytes (operands)
Total dispatcheshigherlower
Compiler complexitytrivialneeds register allocation
ExampleCPython, JVM, WASMLua 5, Dalvik, LuaJIT

Shi et al. measured ~47% fewer executed instructions and ~26% less dispatch time for a register VM on the same programs. The catch is that operand decoding costs more per instruction, so the win is real but smaller than the instruction-count reduction suggests — the same "predicted gain under-delivers for a nameable reason" pattern block 5 documents.

Values, objects and memory layout

How you represent a dynamically typed value determines the cost of every operation:

  • Boxed pointers: every integer is a heap object. Simple; catastrophic for arithmetic (allocation + pointer chase per operation).
  • Pointer tagging: use the low bits of an aligned pointer as a type tag, so small integers are immediate. One and + shr to unbox. Used by V8 (SMIs), OCaml, most Lisps.
  • NaN boxing: IEEE-754 doubles have 2⁵¹ unused NaN payloads, so pointers and small values hide inside a 64-bit double. Used by LuaJIT, JavaScriptCore, SpiderMonkey. Doubles are unboxed by construction, which matters for numeric code.

Object layout matters as much. Hidden classes / shapes (V8, from Self's maps) give dynamically typed objects a static layout so a field access is a fixed offset load rather than a hash lookup — and then inline caching turns a polymorphic property access into a guard plus a load. That progression, maps → inline caches → type feedback → speculative optimisation with deoptimisation, is essentially the entire history of fast dynamic-language implementation.

Block 7's slot resolution is the first step of it: a variable reference was a string hash and a dict probe; now it is a list index, because the information needed (which names exist in this function) was available at compile time. Everything above is that same move applied to increasingly dynamic facts.

Garbage collection: the real design space

CollectorPauseThroughput costSpaceNotes
Reference countingnone (amortised)high (every assignment)lowcannot collect cycles — block 8's demonstration
Mark–sweep\(O(\text{heap})\)lowfragmentationthe baseline
Mark–compact\(O(\text{heap})\)moderateno fragmentationmoving; needs precise roots
Copying (semispace)\(O(\text{live})\)low2× spaceallocation is a pointer bump
Generational\(O(\text{young live})\)low~1.2×exploits the weak generational hypothesis
Concurrent/incremental (G1, ZGC, Shenandoah)sub-ms~10--20%higherread/write barriers, coloured pointers

The weak generational hypothesis — most objects die young — is why generational collection dominates: a minor collection touches only the nursery's live set, which is usually 1--5% of allocations. The cost is a write barrier on every pointer store to maintain the remembered set of old→young references. That barrier is a real tax on mutator throughput, and tuning it (card marking vs remembered sets) is a large part of production GC engineering.

CPython uses both: reference counting for prompt reclamation plus a cycle detector for exactly the case block 8 constructs. Its refcount updates are also why the GIL was so hard to remove — every Py_INCREF on a shared object would need to be atomic, and atomics on contended cache lines cost ~20--100 cycles.

Latency, caches and the interpreter loop

The interpreter loop's working set matters more than its instruction count:

EffectCostMitigation
Branch misprediction~15--20 cyclescomputed goto, superinstructions
I-cache miss on a large handler~10--100 cycleskeep handlers small, order hot ones together
Dependent load in bytecode fetchL1 ~1 nsprefetch the next instruction
Indirect call to a builtinpipeline flushinline caching

Superinstructions — fusing common opcode pairs (LOAD_FAST; LOAD_FAST → LOAD_FAST_LOAD_FAST) — cut both dispatch count and I-cache pressure, and are a large part of the CPython 3.11+ speedups, alongside inline caching and quickening (rewriting bytecode in place with type-specialised variants after observing actual types).

How this connects to the rest of the track

  • P13 is a compiler too: its graph is a dataflow IR, and operator fusion is exactly the superinstruction idea applied to tensor ops.
  • P12's page tables and this project's GC both answer "who owns this memory and when is it safe to reuse".
  • P14's cost-model argument is the general form of block 5's finding.
  • P04's compaction and a copying collector are the same algorithm: copy the live set to fresh space, drop the old, fix the pointers.

Failure modes at scale

  • Deoptimisation loops: a JIT specialises on observed types, the assumption breaks, it deoptimises and respecialises repeatedly, running slower than the interpreter. Real systems cap recompilation attempts.
  • GC pause tail: mean pause is irrelevant; p99.9 pause is the SLO, and a full compaction of a 100 GB heap is seconds.
  • Memory leaks through the root set — a cache holding references keeps whole object graphs alive. Reachability is the definition of liveness, so a "leak" in a GC'd language is always an unintended root.
  • Benchmarks that measure the compiler: a microbenchmark whose hot loop is constant-folded away measures nothing. The assembly's note about constant folding being invisible on both programs is the polite version; the Rust scaffold in this track hit the aggressive version and needed black_box.

Primary sources

  • Ertl & Gregg, The Structure and Performance of Efficient Interpreters (2003) — the branch-prediction argument for computed goto.
  • Shi et al., Virtual Machine Showdown: Stack Versus Registers (VEE 2005).
  • Deutsch & Schiffman, Efficient Implementation of the Smalltalk-80 System (POPL 1984) — inline caching.
  • Hölzle, Chambers & Ungar, Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches (ECOOP 1991).
  • Ungar, Generation Scavenging (1984); Jones, Hosking & Moss, The Garbage Collection Handbook (2nd ed.).
  • Pratt, Top Down Operator Precedence (POPL 1973) — block 2's parser.
  • Nystrom, Crafting Interpreters (2021) — the best modern treatment of the whole pipeline.

Running it

python3 handson/h11_language.py            # every block, then the assembly
python3 handson/h11_language.py --block 3  # just block 3 and its prerequisites
python3 handson/h11_language.py --quiet    # the assembly only

What to do with this

Port the VM loop to C with a computed-goto dispatch table and run the same two programs. That is where the textbook's speedup lives, and measuring it in both hosts is the clearest possible demonstration that "which algorithm is faster" is an incomplete question.

Milestones, experiments, readings and exit criteria for this project: P11 — Programming Language and VM.