Interpreters and Virtual Machines

A checked syntax tree is still only a description of a search. Something has to run it: fetch the records by Le Guin, fetch the records after 1970 and intersect the two. There are two ways to do that. Walk the tree directly, doing each node's work as you reach it, or first flatten the tree into a list of simple instructions and run them on a small virtual machine.

CPython runs every Python program the second way. Lantern should run its queries the first way. What each approach costs depends less on the machinery than on how many times the same code runs, and on how much work each step does compared with the cost of deciding what the step is.

Walking the Tree

A tree-walking interpreter is one recursive function. A field-match node returns the postings list for its term, from the hash-table index of Chapter 5. A comparison node returns the records whose year passes. An AND node evaluates both children and intersects the two sorted lists, the walk Chapter 7 describes. OR takes the union, and NOT takes everything in the catalogue that its child did not return.

def evaluate(node, index):
    match node:
        case Match(field, value):
            return index.lookup(field, value)
        case Compare(field, op, value):
            return index.years(op, int(value))
        case And(left, right):
            return intersect(evaluate(left, index), evaluate(right, index))
        case Or(left, right):
            return union(evaluate(left, index), evaluate(right, index))
        case Not(child):
            return sorted(set(index.all_ids) - set(evaluate(child, index)))

Each case in the excerpt matches one kind of node and returns a sorted list of record ids. The leaves ask the index; the operators call evaluate on their children and combine the lists. For a small language that runs each tree once, this shape is natural, short and correct, and it is the right one for Lantern.

What the Walk Costs Lantern

The interpreter's own overhead for the canonical query is a handful of function calls. The real cost is the data. The author match returns a few dozen records. The year comparison returns most of the 2 million, and a naive walker builds that whole list before intersecting it with the few dozen. A query that is a bare NOT is worse, since it returns nearly the whole catalogue.

On the scale of the catalogue, the author list and the answer are slivers, and the year list crosses most of the figure. That is where a search spends its time. Interpretation overhead matters in proportion to how many times the code runs against how much work each step does: Lantern runs each tree once per search and each step touches thousands of records, while a loop body in a Python program can run a million times doing one addition each time.

Compiling to Bytecode

The alternative flattens the tree first. Emit each node after its children, a post-order traversal from Chapter 6, and the result is a list of instructions for a stack machine. For the canonical query Lantern's compiler emits three: MATCH author "le guin", COMPARE year greater than 1970, and AND.

A dispatch loop runs the list: read one instruction, perform it on an operand stack, move to the next. MATCH pushes Le Guin's records. COMPARE pushes the records after 1970. AND pops both lists and pushes their intersection, which is the answer. This is the fetch, decode and execute cycle of Chapter 3, running in software.

This operand stack is not the call stack from Chapter 3. The call stack holds one frame per active function. In CPython each frame carries its own small operand stack, where the instructions of that one function push and pop their values.

Why Bytecode Beats a Tree

A bytecode interpreter runs faster than a tree walker for code that repeats. The instructions sit in one contiguous array, friendly to the caches of Chapter 4. The work of deciding what each node means was done once, at compile time, instead of again on every run by matching on the node. There is no recursive call per node, and no pointer to chase from a parent to its children.

Bytecode costs a compile step and a second representation to keep correct. Stack machines, such as CPython, the Java virtual machine and WebAssembly, use small, simple instructions that take their operands from the stack. Register machines, such as Lua since version 5.0 and Android's original Dalvik, use fewer, larger instructions that name their operands, so they run fewer instructions for the same work.

CPython's Bytecode

Every Python program is compiled before it runs: source to tokens, tokens to a tree, the tree to bytecode in a code object. The bytecode is cached in a __pycache__ directory as a .pyc file, so the next import skips the whole front end. The standard library's dis module prints bytecode, and it is the one tool this chapter names.

LOAD_GLOBAL              0 (count)
LOAD_SMALL_INT           1
BINARY_OP               13 (+=)
STORE_GLOBAL             0 (count)

On Python 3.15 the line compiles to four instructions: load the global count, load the small integer 1, add in place and store the result back into the global. That is the read, the add and the write from the race conditions topic in Chapter 11, with the constant loaded on its own. The instruction set changes between Python versions, and 3.15 has instructions that 3.12 did not, which is why every .pyc file begins with a version stamp and a .pyc from another version is recompiled from source.

The Interpretation Tax

Each bytecode instruction pays for dispatch and for checking its operands' types before doing its work. One Python-level addition therefore costs dozens to hundreds of machine instructions where compiled code would spend one. A Python loop pays that price on every step, which explains a measurable gap. On Python 3.15, summing a list of a million integers with the built-in sum ran about eight times faster than a hand-written loop over the same list, because the loop inside sum runs in C and pays one dispatch per call instead of several per element.

The same tax is why numeric libraries such as NumPy exist: they move whole loops out of the interpreter. The next two topics are the two general ways to cut it: compile to machine code before the program runs, or while it runs.