Interpreters, Virtual Machines and Garbage Collection

So far, every program we've run was turned into the processor's own machine code before it started. That gives the fastest code, but it has costs. The program must be compiled again for every kind of processor, every type must be known in advance, and the programmer must manage memory by hand. Many popular languages make a different trade: a little less speed in exchange for portability, flexibility and safety.

Interpreters

An interpreter is a program that runs another program by reading it and doing what it says, step by step, instead of translating it into machine code first. The simplest interpreter walks the syntax tree of Chapter 23: to work out a + b * c, it works out b * c, then adds a. You can change the program and run it again at once, with no compiling and linking, and the same program runs anywhere the interpreter does.

Walking a tree is slow, though, so most interpreters first compile the program into bytecode: compact instructions for an imaginary processor, called a virtual machine (VM). The VM is a program, usually written in C, and it works exactly like the real processors of Chapter 6: fetch the next instruction, decode it, execute it, and repeat. It's a processor made of software.

Bytecode: a processor made of software

Python's virtual machine is a stack machine. It has no registers. Instead, instructions push values onto a stack (the idea from Chapter 22) and pop them off again: to add two numbers, push both, then BINARY_OP pops two values and pushes their sum. Stack machines make bytecode short and simple to generate. Here's a real Python function and its real bytecode, as produced by Python 3.12 on the computer this book was written on:

Each Python bytecode instruction is two bytes, an opcode and an argument, sometimes followed by spare space the interpreter uses as a cache. Look at BINARY_OP: it doesn't know whether it's adding two whole numbers, two decimals, two pieces of text or two lists. It has to check the types every single time it runs. That checking, plus the fetch-decode-execute loop itself, is why each bytecode instruction costs many real machine instructions.

Java's virtual machine (the JVM) and WebAssembly are stack machines too. The Lua language uses a register-based VM instead, which needs fewer instructions but longer ones, a little like RISC-V versus a stack.

Just-in-time compilers

How can an interpreted language be fast? A just-in-time (JIT) compiler compiles the program into real machine code while it's running. The VM starts by interpreting, and counts how often each function runs. When a function gets "hot", the JIT compiles it.

A JIT has a big advantage over an ahead-of-time compiler: it can watch the program first. If sumTo(n) has been called a thousand times and n was always a small whole number, the JIT speculates that it always will be, and compiles the loop into a few machine instructions, plus a quick check, called a guard. If the guard ever fails, the engine throws the fast code away, deoptimises back to the interpreter, and may compile again later with what it has learned.

Modern engines have several tiers: a quick compiler that makes decent code fast, and an optimising compiler for the hottest code. Java's HotSpot uses an interpreter and two compilers, C1 and C2. Chrome's V8 JavaScript engine uses an interpreter called Ignition, and three compilers: Sparkplug, Maglev and TurboFan. This demo measures the real thing, in your own browser:

Garbage collection

Programs constantly create objects: a list here, a piece of text there. They live in a big area of memory called the heap. In C, the programmer asks for heap memory with malloc and must give it back with free. Forget to free it, and the program slowly fills up memory: a memory leak. Free it too early, or twice, and the program may crash or, worse, become open to attack. These are among the commonest and most dangerous bugs there are.

Most modern languages free memory automatically, using a garbage collector. An object is garbage when the program can no longer reach it, by following references from its variables. There are two main ways to find it:

• Reference counting (Python, Swift): every object counts the references pointing at it. When the count drops to zero, the object is freed at once.
• Tracing (Java, JavaScript, Go, C#): every so often, the collector starts from the variables, follows every reference it can, and marks what it reaches. Everything unmarked is garbage, and is swept away.

Reference counting is simple and frees memory the moment it's unused, but it can't free cycles of objects that point at each other. Python solves this by running a tracing cycle collector as well, now and then. Tracing collectors handle cycles naturally, but the program has to pause, at least briefly, while they work.

Tracing collectors rely on a useful observation: most objects die young. A temporary list, used once and dropped, is far more common than an object that lives for the whole run. So a generational collector puts new objects in a small "young" area and scans it often. Scanning is cheap because almost everything there is already dead: only the few survivors need copying out. Rust takes a third path, with no collector at all: its compiler works out exactly where each object stops being used, and inserts the frees itself.

Meanwhile, inside a real CPU

Python's dis module shows a function's bytecode. Here's the start of the listing for our sum_to, and the raw bytes behind it, two per instruction:

>>> dis.dis(sum_to)                                (trimmed)
  2           0 RESUME                   0
  3           2 LOAD_CONST               1 (0)
              4 STORE_FAST               1 (total)
  4           6 LOAD_CONST               2 (1)
              8 STORE_FAST               2 (i)
  5          10 LOAD_FAST                2 (i)
             12 LOAD_FAST                0 (n)
             14 COMPARE_OP              26 (<=)
             18 POP_JUMP_IF_FALSE       16 (to 52)
…
>>> sum_to.__code__.co_code.hex(" ")
'97 00 64 01 7d 01 64 02 7d 02 7c 02 7c 00 6b 1a 00 00 72 10 …'

Timed on the same computer, adding up the numbers from 1 to 10 million:

Python 3.12 (interpreter):        0.255 s    ← about 25 ns per trip round the loop
C, GCC -O1 (Chapter 23):          0.002 s    ← about 0.2 ns per trip

Java shows the JIT's effect directly. The same loop in Java, adding up to 100 million, with HotSpot's JIT and then with -Xint, which forces the interpreter only:

$ java Sum.java 100000000                     (first round)
round 1: 5000000050000000 in 0.0233 s     ← JIT: as fast as C
$ java -Xint Sum.java 100000000
round 1: 5000000050000000 in 0.4349 s     ← interpreter only: almost 20 times slower

Asking HotSpot to report its compilations shows the tiers at work. The % marks on-stack replacement: switching a loop to compiled code while it's still running. Tier 3 is the quick C1 compiler and tier 4 the optimising C2. "Made not entrant" means older code was retired in favour of better code:

$ java -XX:+PrintCompilation Sum.java 100000000 | grep sumTo     (trimmed)
253 1360 %     3       Sum::sumTo @ 5 (28 bytes)
253 1361       3       Sum::sumTo (28 bytes)
254 1362 %     4       Sum::sumTo @ 5 (28 bytes)
254 1360 %     3       Sum::sumTo @ 5 (28 bytes)   made not entrant
282 1402       4       Sum::sumTo (28 bytes)

Python's own garbage collector, catching a cycle that reference counting alone would leak:

import gc, sys
gc.collect()                     # start with a clean slate
class Page: pass
a = Page(); b = Page()
a.next = b; b.prev = a           # a cycle: a -> b -> a
print("references to a:", sys.getrefcount(a) - 1)
del a, b                         # nothing outside points at them now
print("found by the cycle collector:", gc.collect())

references to a: 2                ← the variable a, and b.prev
found by the cycle collector: 2

Finally, a Java program that makes 50 million small temporary arrays, about 4 GB in total, and keeps none of them. The garbage collector's log shows the young area filling up with hundreds of megabytes, and each collection shrinking it to 3 MB in about one and a half milliseconds, because almost everything in it was already dead:

$ java -Xlog:gc Garbage.java                                     (trimmed)
[0.326s][info][gc] GC(2) Pause Young (Normal) (G1 Evacuation Pause) 299M->3M(504M) 1.511ms
[0.356s][info][gc] GC(3) Pause Young (Normal) (G1 Evacuation Pause) 299M->3M(504M) 1.081ms
[0.536s][info][gc] GC(6) Pause Young (Normal) (G1 Evacuation Pause) 455M->3M(760M) 1.701ms

Try it yourself

1. Write stack-machine instructions for a * (b + c), using LOAD, ADD and MUL. How deep does the stack get?
   Show answer

   LOAD a, LOAD b, LOAD c, ADD, MUL. After the third LOAD, the stack holds a, b and c: 3 values deep. ADD replaces b and c with b + c, then MUL leaves just the answer.
2. In the bytecode demo, how many bytecode instructions does each trip round the loop take?
   Show answer

   13: from offset 20 (LOAD_FAST total) to 50 (JUMP_BACKWARD). Two lines of Python become 13 instructions, each of which costs many machine instructions.
3. Python took about 25 ns per trip round the loop. At roughly 4.9 GHz, how many clock cycles is each of those 13 bytecode instructions?
   Show answer

   25 ns ÷ 13 ≈ 1.9 ns per instruction. At 4.9 GHz, a clock cycle lasts about 0.2 ns, so that's around 9 or 10 cycles per bytecode instruction, compared with a fraction of a cycle for each machine instruction in the compiled C loop.
4. Why can't a JIT compile total += i into a single machine add before the program has run?
   Show answer

   In Python or JavaScript, total and i could be numbers, text, lists or anything else, and + means something different for each. Only by watching the running program can the JIT learn which types actually turn up, and even then it needs a guard in case they change.
5. In Python, an object does self.me = self, then the last variable pointing to it is deleted. What happens?
   Show answer

   Its reference count can never drop below 1, because it points to itself: a cycle of one. Reference counting alone would leak it forever. Python's cycle collector finds it the next time it runs, because nothing reachable from the program's variables points to it.

What we learned

• An interpreter runs a program directly; most compile it first into bytecode for a software virtual machine, which repeats fetch, decode, execute.
• Python's VM is a stack machine, and must check types at run time, so each bytecode costs many machine instructions.
• A JIT compiler watches the running program, compiles hot code to machine code based on what it saw, and deoptimises if its guesses fail.
• Garbage collectors free unreachable objects automatically, by reference counting or by tracing (mark and sweep).
• Since most objects die young, generational collectors scan new objects often and cheaply.

That completes Part VIII, and the climb from a single switch to the languages programmers use every day. In Part IX we look inside the modern machine, starting with the tricks that let one processor core run several instructions at once: pipelines and speculation.