"""The demo: compiling this tree removes exactly zero operations. python3 demo.py # all ten sections, about 20s python3 demo.py 2 7 # just those sections Sections 1, 2, 5, 7 and 10 print COUNTS and are byte-identical on every run. Sections 3, 4, 6, 8 and 9 print TIMINGS: min of 21 interleaved trials of 30 executions each, after warm-up, and they move a few percent run to run. """ import dis import platform import random import re import statistics import sys import time from fractions import Fraction from vm import (ADD, BINOP, DIV, LOAD, MUL, NEG, PUSH, SUB, Bin, Neg, Num, Parser, Var, closure_compile, compile_expr, count_nodes, evaluate, fold_constants, parse, vm_run) LEAVES = 2048 TRIALS = 21 REPS = 30 ENV = {"x": 3, "y": 5, "z": 7} VARS = ("x", "y", "z") OPNAME = {PUSH: "PUSH", LOAD: "LOAD", ADD: "ADD", SUB: "SUB", MUL: "MUL", DIV: "DIV", NEG: "NEG"} # ------------------------------------------------------------- the harness 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] def timeit(fn, reps=REPS, trials=TRIALS): return bench([fn], reps, trials)[0] def rule(title): print() print("=" * 70) print(" " + title) print("=" * 70) print() def gen_source(n_leaves, seed=7, const_only=False, ops="+-"): """A deterministic expression with exactly `n_leaves` leaves. `+` and `-` only by default, on purpose: with `*` in the mix a 2048-leaf expression evaluates to a 60-digit bignum and CPython's bignum arithmetic swamps the dispatch difference -- see section 8, where that is the point. """ rng = random.Random(seed) def leaf(): if const_only or rng.random() < 0.5: return str(rng.randint(1, 9)) return rng.choice(VARS) def build(k): if k == 1: return leaf() left = rng.randint(1, k - 1) op = rng.choice(ops) return "(" + build(left) + op + build(k - left) + ")" return build(n_leaves) def disasm(code, consts, names): """The program as text. Note what cannot be recovered from it.""" out = [] for i, (op, arg) in enumerate(code): if op == PUSH: out.append(f"{i:4d} PUSH {consts[arg]!r}") elif op == LOAD: out.append(f"{i:4d} LOAD {names[arg]}") else: out.append(f"{i:4d} {OPNAME[op]}") return "\n".join(out) # ---------------------------------------------------- counted copies (§2) def evaluate_counted(node, env, box): box[0] += 1 if isinstance(node, Num): return node.value if isinstance(node, Var): return env[node.name] if isinstance(node, Neg): return -evaluate_counted(node.operand, env, box) left = evaluate_counted(node.left, env, box) right = evaluate_counted(node.right, env, box) return {"+": left + right, "-": left - right, "*": left * right, "/": left / right if right else None}[node.op] def vm_run_counted(code, consts, names, env): """vm_run with a step counter and the leftover stack depth returned.""" stack, pc, steps = [], 0, 0 while pc < len(code): op, arg = code[pc] pc += 1 steps += 1 if op == PUSH: stack.append(consts[arg]) elif op == LOAD: stack.append(env[names[arg]]) elif op == NEG: stack.append(-stack.pop()) else: b = stack.pop() a = stack.pop() stack.append({ADD: a + b, SUB: a - b, MUL: a * b, DIV: a / b if b else None}[op]) return stack[-1], steps, len(stack) # ------------------------------------------- rival back ends, for §3's grid _OPS = {"+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b, "/": lambda a, b: a / b} def tw_dict(node, env): """The tree-walker's best form: dispatch on type through a dict instead of an isinstance chain. Not a strawman is the whole point of §3.""" return _T[type(node)](node, env) _T = { Num: lambda n, env: n.value, Var: lambda n, env: env[n.name], Neg: lambda n, env: -tw_dict(n.operand, env), Bin: lambda n, env: _OPS[n.op](tw_dict(n.left, env), tw_dict(n.right, env)), } def _h_push(s, a, c, n, e): s.append(c[a]) def _h_load(s, a, c, n, e): s.append(e[n[a]]) def _h_neg(s, a, c, n, e): s.append(-s.pop()) def _h_add(s, a, c, n, e): b = s.pop() s.append(s.pop() + b) def _h_sub(s, a, c, n, e): b = s.pop() s.append(s.pop() - b) def _h_mul(s, a, c, n, e): b = s.pop() s.append(s.pop() * b) def _h_div(s, a, c, n, e): b = s.pop() s.append(s.pop() / b) _H = {PUSH: _h_push, LOAD: _h_load, NEG: _h_neg, ADD: _h_add, SUB: _h_sub, MUL: _h_mul, DIV: _h_div} def vm_run_dict(code, consts, names, env): """Dispatch through a dict of handlers rather than an if/elif chain.""" stack = [] for op, arg in code: _H[op](stack, arg, consts, names, env) return stack[-1] def vm_run_slots(code, consts, regs): """LOAD by slot index instead of by name: locals-are-an-array, applied to the identical instruction stream.""" stack = [] push, pop = stack.append, 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(regs[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()) return stack[-1] # ------------------------------------------------ the two buggy compilers def _pools(): code, consts, names, seen = [], [], [], {} def intern(pool, key, value): if key not in seen: seen[key] = len(pool) pool.append(value) return seen[key] return code, consts, names, intern def compile_swapped(node): """vm.compile_expr with ONE line moved: `emit(node.right)` before `emit(node.left)`. Same length, same opcode histogram, wrong number.""" code, consts, names, intern = _pools() 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.right) # <-- THE SWAP emit(node.left) code.append((BINOP[node.op], 0)) emit(node) return code, consts, names def compile_onepass_fold(node): """The obvious one-pass constant folder: fold and emit in one recursion, materialising a folded operand where you discover it. This is not hypothetical -- it is what the prototype for this toy did, and only a diff against the tree-walker caught it. When the LEFT operand folds and the right does not, the PUSH of the left constant is appended AFTER the right subtree's code, so the operands reach the VM reversed. """ code, consts, names, intern = _pools() def const(value): return intern(consts, ("const", type(value), value), value) 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 top = emit(node) if top is not None: code.append((PUSH, const(top))) return code, consts, names def convert_tree(node, f): """Rebuild the tree with every literal passed through `f`, so both back ends see the SAME operand types. Without this, section 8 would compare a tree-walker adding ints to Fractions against a VM adding Fractions.""" if isinstance(node, Num): return Num(f(node.value)) if isinstance(node, Var): return Var(node.name) if isinstance(node, Neg): return Neg(convert_tree(node.operand, f)) return Bin(node.op, convert_tree(node.left, f), convert_tree(node.right, f)) # ------------------------------------------------------------- the sections def section1(): rule("1. ONE PROGRAM, TWO BACK ENDS") src = gen_source(LEAVES) tree = parse(src) code, consts, names = compile_expr(tree) print(f" source {len(src)} chars, {LEAVES} leaves") print(f" source (first 72) {src[:72]}...") print(f" AST nodes {count_nodes(tree)}") print(f" bytecode instructions {len(code)}") print(f" distinct constants {len(consts)} names {names}") print() print(" first 8 instructions:") for line in disasm(code, consts, names).splitlines()[:8]: print(" " + line) print() print(f" tree-walk value {evaluate(tree, ENV)}") print(f" bytecode value {vm_run(code, consts, names, ENV)}") print(f" closure value {closure_compile(tree)(ENV)}") def section2(): rule("2. COUNTED WORK: THE HEADLINE") tree = parse(gen_source(LEAVES)) code, consts, names = compile_expr(tree) box = [0] walked = evaluate_counted(tree, ENV, box) ran, steps, depth = vm_run_counted(code, consts, names, ENV) print(f" a binary tree with {LEAVES} leaves has 2 x {LEAVES} - 1 = " f"{2 * LEAVES - 1} nodes") print() print(f" tree-walk evaluate() calls {box[0]:>8,}") print(f" bytecode instructions executed {steps:>8,}") print(f" ratio {box[0] / steps:.4f}") print(f" len(code) {len(code):>8,}") print(f" stack left over at halt {depth} (want 1)") print() print(f" both values {walked}, agree {walked == ran}") print(" compilation moved the work. It removed none of it.") def section3(): rule("3. WALL CLOCK, AND WHAT FAIR MEASUREMENT COSTS") tree = parse(gen_source(LEAVES)) code, consts, names = compile_expr(tree) regs = [ENV[n] for n in names] closure = closure_compile(tree) want = evaluate(tree, ENV) rows = [ ("tree-walk, isinstance+str chain", lambda: evaluate(tree, ENV)), ("tree-walk, dict dispatch", lambda: tw_dict(tree, ENV)), ("bytecode VM, if/elif chain", lambda: vm_run(code, consts, names, ENV)), ("bytecode VM, dict of handlers", lambda: vm_run_dict(code, consts, names, ENV)), ("bytecode VM, LOAD by slot", lambda: vm_run_slots(code, consts, regs)), ("closure tree (no dispatch loop)", lambda: closure(ENV)), ] print(f" one tree, {count_nodes(tree)} nodes = {len(code)} instructions," f" every back end returns {want}") print(f" interleaved, min of {TRIALS} trials x {REPS} executions") print() print(f" {'back end':33s} {'us':>9s} {'vs tree-walk':>13s}" f" {'ns/node':>9s} value ok") timings = bench([fn for _, fn in rows]) base = timings[0][0] for (label, fn), (best, _) in zip(rows, timings): print(f" {label:33s} {best * 1e6:9.1f} {base / best:12.3f}x" f" {best / len(code) * 1e9:9.1f} {fn() == want}") print() print(" the last row has no opcodes, no stack and no dispatch loop.") def section4(): rule("4. THE SAME DISPATCH LOOP, WRITTEN IN C") src = gen_source(LEAVES) # every literal becomes a variable, so CPython's peephole optimiser has # nothing to fold and both VMs run the same shape src = re.sub(r"\d+", lambda m: "xyz"[int(m.group()) % 3], src) tree = parse(src) code, consts, names = compile_expr(tree) codeobj = compile(src, "", "eval") cpython_n = len(list(dis.get_instructions(codeobj))) want = evaluate(tree, ENV) got = eval(codeobj, {"__builtins__": {}}, dict(ENV)) print(f" expression: {len(src)} chars, {count_nodes(tree)} AST nodes") print(f" our bytecode {len(code):6d} instructions") print(f" CPython bytecode {cpython_n:6d} instructions") print(f" our value {want} CPython value {got} agree {want == got}") print() env2 = dict(ENV) (t_tree, _), (t_vm, _), (t_c, _) = bench([ lambda: evaluate(tree, ENV), lambda: vm_run(code, consts, names, ENV), lambda: eval(codeobj, {"__builtins__": {}}, env2)]) print(f" {'back end':38s} {'us':>9s} {'vs tree-walk':>13s} {'ns/instr':>9s}") for label, t, n in (("tree-walk (Python)", t_tree, len(code)), ("our bytecode VM (Python loop)", t_vm, len(code)), ("CPython bytecode VM (C loop)", t_c, cpython_n)): print(f" {label:38s} {t * 1e6:9.1f} {t_tree / t:12.2f}x" f" {t / n * 1e9:9.1f}") print() print(f" the C loop is {t_vm / t_c:.1f}x the identical loop in Python.") def section5(): rule("5. CONSTANT FOLDING: THE ONLY EDIT THAT REMOVES OPERATIONS") src = gen_source(LEAVES, const_only=True) tree = parse(src) plain = compile_expr(tree) folded = compile_expr(tree, fold=True) print(f" a {LEAVES}-leaf expression with no variables, {len(src)} chars") print(f" AST nodes {count_nodes(tree):>8,}") print(f" AST nodes after folding {count_nodes(fold_constants(tree)):>8,}") print(f" instructions, no folding {len(plain[0]):>8,}") print(f" instructions, folding on {len(folded[0]):>8,}") print(f" removed {len(plain[0]) - len(folded[0]):>8,}" f" ({(1 - len(folded[0]) / len(plain[0])) * 100:.2f}%)") print() print(" the whole program, folded:") print(" " + disasm(*folded)) print() code, consts, names = folded print(f" tree-walk value {evaluate(tree, ENV)} " f"folded VM value {vm_run(code, consts, names, ENV)}") (t_tree, _), (t_fold, _) = bench([ lambda: evaluate(tree, ENV), lambda: vm_run(code, consts, names, ENV)]) print(f" tree-walk {t_tree * 1e6:.1f} us folded VM {t_fold * 1e6:.4f} us" f" {t_tree / t_fold:.0f}x") print(" (that ratio divides by a sub-microsecond number: order 1000x,") print(" and as noise-dominated as section 9's three-instruction row.)") print() one_var = src.replace("9", "x", 1) partly = compile_expr(parse(one_var), fold=True) print(" substitute ONE variable into the same expression:") print(f" instructions, folding on {len(partly[0]):>8,}") print(f" value {vm_run(*partly, ENV):>8}" f" tree-walk {evaluate(parse(one_var), ENV)}") def section6(): rule("6. COMPILE ONCE, RUN MANY: WHERE THE CROSSOVER IS") print(" parse is paid by BOTH back ends, so it cancels; only the compile") print(" step is the bytecode path's debt. The saving is a DIFFERENCE, so") print(" it is measured as one: 41 interleaved trials, subtracted WITHIN") print(" each trial, median of the differences.") print() for leaves in (64, 256, 2048): src = gen_source(leaves) tree = parse(src) code, consts, names = compile_expr(tree) (t_parse, _), (t_comp, _) = bench([lambda: parse(src), lambda: compile_expr(tree)], reps=5) walk, loop = bench([lambda: evaluate(tree, ENV), lambda: vm_run(code, consts, names, ENV)], trials=41, raw=True) saving = statistics.median(a - b for a, b in zip(walk, loop)) n = t_comp / saving if saving > 0 else float("inf") print(f" {leaves:5d} leaves {len(code):6d} instrs " f"parse {t_parse * 1e6:8.1f}us compile {t_comp * 1e6:7.1f}us " f"saving/run {saving * 1e6:7.3f}us crossover N = {n:6.1f}") print() print(" this is the noisiest number on the page: read it as ORDER 10-20") print(" executions, not as an integer.") def section7(): rule("7. THE LOAD-BEARING LINE: emit(left) BEFORE emit(right)") print(" swap those two lines in vm.compile_expr:") print() for src in ("2-3-4", "8-(0-3)", "x-y-z"): tree = parse(src) good = vm_run(*compile_expr(tree), ENV) swapped = vm_run(*compile_swapped(tree), ENV) print(f" {src:10s} correct {good:>4} operands swapped {swapped:>4}" f" {'DIFFER' if good != swapped else 'same'}") tree = parse(gen_source(LEAVES)) good = vm_run(*compile_expr(tree), ENV) swapped = vm_run(*compile_swapped(tree), ENV) print() print(f" {LEAVES}-leaf expr correct {good} swapped {swapped}" f" equal {good == swapped}") print(f" instructions: correct {len(compile_expr(tree)[0])}" f" swapped {len(compile_swapped(tree)[0])}") print() print(" the same bug, as it actually shipped: a ONE-PASS constant folder") print(" emits a folded left operand after the right subtree's code.") print() for src in ("2-x", "5-x-1", "(1+2)-y"): tree = parse(src) walk = evaluate(tree, ENV) two = vm_run(*compile_expr(tree, fold=True), ENV) one = vm_run(*compile_onepass_fold(tree), ENV) print(f" {src:10s} tree-walk {walk:>4} two-pass {two:>4}" f" one-pass {one:>4} {'WRONG' if one != walk else 'ok'}") print() print(" the whole program `2-x`, with x = 3:") tree = parse("2-x") left = disasm(*compile_expr(tree, fold=True)).splitlines() right = disasm(*compile_onepass_fold(tree)).splitlines() print(f" {'two-pass':22s} one-pass") for a, b in zip(left, right): print(f" {a:22s} {b}") print() wrong_two = wrong_one = crashed = 0 for seed in range(400): tree = parse(gen_source(12, seed=seed, ops="+-*")) want = evaluate(tree, ENV) if vm_run(*compile_expr(tree, fold=True), ENV) != want: wrong_two += 1 try: if vm_run(*compile_onepass_fold(tree), ENV) != want: wrong_one += 1 except Exception: crashed += 1 print(" differential sweep, 400 random programs against the tree-walker:") print(f" two-pass folder wrong on {wrong_two:3d} / 400") print(f" one-pass folder wrong on {wrong_one:3d} / 400") print(f" one-pass folder CRASHED on {crashed:3d} / 400") print() print(" every program the buggy compiler emits is stack-balanced and") print(" well-formed. It is just not the program you wrote.") def section8(): rule("8. BOUNDARY 1: MAKE ONE OPERATION EXPENSIVE") base = parse(gen_source(LEAVES)) cases = [("machine ints (< 2^63)", lambda v: v, dict(ENV))] for digits in (100, 1000, 10000, 100000): big = 10 ** digits cases.append((f"{digits}-digit bignums", (lambda b: (lambda v: v + b))(big), {"x": big + 3, "y": big + 5, "z": big + 7})) cases.append(("Fractions", Fraction, {"x": Fraction(3, 7), "y": Fraction(5, 11), "z": Fraction(7, 13)})) trials = 21 print(f" min of {trials} interleaved trials, and the SAME ratio computed") print(" from the medians beside it, because this table is noisy exactly") print(" where the operations are slowest.") print() print(f" {'operand type':22s} {'instrs':>6s} {'tree us':>10s}" f" {'vm us':>10s} {'min':>8s} {'median':>8s} agree") for label, convert, env in cases: tree = convert_tree(base, convert) code, consts, names = compile_expr(tree) reps = 30 if getattr(env["x"], "bit_length", lambda: 0)() < 7000 else 3 (t_tree, m_tree), (t_vm, m_vm) = bench([ lambda: evaluate(tree, env), lambda: vm_run(code, consts, names, env)], reps, trials) ok = evaluate(tree, env) == vm_run(code, consts, names, env) print(f" {label:22s} {len(code):6d} {t_tree * 1e6:10.1f}" f" {t_vm * 1e6:10.1f} {t_tree / t_vm:7.3f}x" f" {m_tree / m_vm:7.3f}x {ok}") print() print(" the instruction count is identical in every row; only the cost of") print(" ONE operation changed. The dispatch saving is a fixed ~35us over") print(" a growing total, so it is gone by the first bignum row -- and the") print(" rows below that are NOT a decreasing sequence, they are a ratio") print(" smaller than this table's own run-to-run spread. Do not read a") print(" trend into them; read them as 1.0.") def section9(): rule("9. BOUNDARY 2: MAKE THE PROGRAM TINY") print(f" {'leaves':>7s} {'instrs':>7s} {'tree us':>10s} {'vm us':>10s}" f" {'speedup':>9s} {'ns/node':>9s} {'ns/instr':>9s}") for leaves in (2, 8, 32, 128, 512, 2048, 8192): tree = parse(gen_source(leaves)) code, consts, names = compile_expr(tree) n = len(code) reps = max(1, 60000 // n) (t_tree, _), (t_vm, _) = bench([ lambda: evaluate(tree, ENV), lambda: vm_run(code, consts, names, ENV)], reps) print(f" {leaves:7d} {n:7d} {t_tree * 1e6:10.2f} {t_vm * 1e6:10.2f}" f" {t_tree / t_vm:8.3f}x {t_tree / n * 1e9:9.1f}" f" {t_vm / n * 1e9:9.1f}") print() print(" at 3 instructions the VM LOSES: building the stack list and") print(" binding push/pop is not amortised over three opcodes.") def section10(): rule("10. DIFFERENTIAL CORRECTNESS, AND THE IDENTITY OVER 2000 PROGRAMS") disagreements = worst = 0 for seed in range(2000): tree = parse(gen_source(10, seed=seed, ops="+-*")) want = evaluate(tree, ENV) for got in (vm_run(*compile_expr(tree), ENV), vm_run(*compile_expr(tree, fold=True), ENV), closure_compile(tree)(ENV), tw_dict(tree, ENV)): disagreements += got != want code, _, _ = compile_expr(tree) worst = max(worst, abs(len(code) - count_nodes(tree))) print(" 2000 random programs x 4 back ends = 8000 checks") print(f" disagreements with the tree-walker: {disagreements}") print(f" max |len(code) - count_nodes(tree)|: {worst}") SECTIONS = {1: section1, 2: section2, 3: section3, 4: section4, 5: section5, 6: section6, 7: section7, 8: section8, 9: section9, 10: section10} if __name__ == "__main__": print(f"python {sys.version.split()[0]} {platform.platform()}" f" {platform.machine()}") for k in ([int(a) for a in sys.argv[1:]] or sorted(SECTIONS)): SECTIONS[k]()