Bytecode virtual machines and garbage collection

The first chapter of this level introduced the three ways to run a program: compile it, interpret it, or compile it just in time. This one opens the interpreter. Languages like Java, Python, JavaScript and C# run on a runtime, a program that provides two things C leaves to you: a virtual machine that executes bytecode, and a garbage collector that frees memory automatically. Both are ordinary programs, and both fit in a few dozen lines of C at their simplest.

A virtual machine on one page of C

A bytecode VM is a loop: fetch the next bytecode instruction, decode it, execute it, repeat — the fetch-decode-execute cycle of a real CPU, done in software. Here is one, with its own operand stack and local variables, running a program in real JVM bytecode. The instructions come from the subset Tanenbaum calls IJVM, with the same opcode numbers as the Java Virtual Machine: 0x10 is BIPUSH, 0x60 is IADD, 0xA7 is GOTO.

The bytecode, assembled by hand, computes the same function as the first chapter's demo: s = 0; for (i = 0; i != n; i++) s += i * 2; return s;, with i * 2 written as i + i, since IJVM has no multiply.

Press Continue to run it: it returns 20, the same answer as the compiled version. Step through a few iterations of the while loop and watch pc, sp, stack and local in the Variables panel: the VM has its own program counter, stack pointer and registers, kept in ordinary memory. The real CPU is running the interpreter; the interpreter is running the bytecode.

Everything here mirrors the hardware. Branch offsets are signed 16-bit numbers relative to the branch instruction itself, so GOTO -19 at address 27 jumps back to 8, and (short)(hi << 8 | lo) decodes them big-endian, as the JVM specifies. Tanenbaum's Mic-1 microarchitecture interprets exactly this instruction set, in microcode instead of C: the microprogramming chapter shows how it dispatches on the opcode byte in a single step, where this switch needs a chain of compares.

What interpretation costs

The bytecode program executes 64 bytecode instructions. The simulated CPU, running the interpreter, executes about 3,100 machine instructions to get there — close to 50 machine instructions per bytecode, here with an unoptimized compiler. The same total(5) compiled directly to machine code took 81 instructions in the first chapter.

The overhead comes from work the compiled version never does: fetching each opcode from memory, decoding it through the switch, keeping stack, local, sp and pc in memory instead of registers, and jumping back to the top of the loop. Real interpreters are written much more carefully than this one, and compiled with optimizations, so the ratio shrinks a lot. But it never reaches zero, which is why the gap between CPython and C in the first chapter was about 20×, and why JIT compilers exist.

Stack machines and register machines

This VM is a stack machine: IADD takes no operands, because they're always the top two stack entries. The JVM, CPython, WebAssembly and .NET all work this way. The bytecode is compact and simple to generate, but it needs many instructions, since every value must be pushed before use.

A register machine names its operands instead, like a real CPU: Lua 5 and Android's Dalvik VM use instructions like ADD r1, r2, r3, and V8's Ignition is a register machine with an accumulator (Ldar, Star in the first chapter's listing). Each instruction is bigger, but there are fewer of them, and fewer dispatches. For an interpreter, dispatch is the dominant cost.

Dispatch

The switch in this VM has nine cases spread from 0x10 to 0xAC, too sparse for a jump table, so the compiler emits a chain of up to nine compares for each bytecode: the control-flow chapter showed why. Real VMs use dense opcode numbers, 0 to about 200, so their switch becomes a jump table: one indirect jump per bytecode.

The next step is threaded code: instead of jumping back to a single switch at the top of the loop, each instruction's handler ends with its own indirect jump to the next handler. CPython does this when the compiler supports "computed goto" (a GCC extension, also in clang). One indirect jump per handler, instead of one shared jump for all of them, gives the branch predictor much better odds: it can learn that ILOAD is often followed by another ILOAD. CPython 3.14 added an optional interpreter built on tail calls between handlers, for the same reason.

Garbage collection

The heap chapter ended with the bugs of manual free: leaks, use-after-free, double free. A garbage collector removes them by making freeing automatic: the runtime frees an object once the program can no longer reach it. There are two families of approach.

Reference counting

Each object keeps a count of the references pointing to it. Every assignment updates the counts, and when a count drops to zero, the object is freed immediately. CPython works this way, and you can see the count:

>>> a = Node()
>>> sys.getrefcount(a)     # a, plus getrefcount's own argument
2
>>> b = a
>>> sys.getrefcount(b)
3

Reference counting frees memory as early as possible, and predictably. But it costs work on every assignment, and it has a blind spot: cycles. If x points to y and y points back to x, both counts stay at 1 even after the program drops them, and they're never freed. CPython therefore also runs a separate cycle collector: after x.other = y; y.other = x; del x, y, a call to gc.collect() reports 2 unreachable objects found and freed. Swift and C++'s shared_ptr use reference counting too, and leave cycles to the programmer, through weak references.

Tracing: mark and sweep

A tracing collector takes the opposite view. It doesn't track assignments at all. From time to time, it starts from the roots — global variables, and the variables on every thread's stack — and follows every pointer, marking each object it reaches. Anything unmarked is garbage, however it's connected, cycles included. Then it sweeps: walks the whole heap and frees the unmarked objects.

Here is a complete mark-and-sweep collector over a heap of eight objects. The program builds A → B → C, plus two objects D and E that point to each other, then drops its references to C, D and E:

It returns 3: C, D and E are freed. Marking starts at root, reaches A and B, and stops, so the D ↔ E cycle is never marked — which reference counting could never have concluded. Watch the used and marked fields of the heap array in the Globals panel as mark and sweep run. mark is recursive, so it's also a good place to watch the call stack.

Real collectors

Production collectors add three ideas to this skeleton:

• Moving and compacting. Instead of leaving holes, a copying collector moves every live object into a fresh region, packed together, and updates every pointer to it. Allocation then becomes a pointer increment, as fast as a stack.
• Generations. Most objects die young: temporary strings, iterator objects, intermediate results. Generational collectors allocate new objects in a small young area and collect it often and cheaply, and only occasionally collect the old generation. V8 shows it with node --trace-gc: a loop that allocates 2 million short-lived objects triggers 41 Scavenge collections of the young generation, each taking 0.1 to 0.5 ms, and no full Mark-Compact of the whole heap at all.
• Concurrency. Stopping every thread while the heap is traced gives pause times proportional to the heap. Modern collectors do most of the marking concurrently with the program. The JVM's default collector, G1, targets pauses of a few hundred milliseconds or less, and ZGC keeps them under a millisecond, even on heaps of many gigabytes.

The trade-off is the same as everywhere in this level: garbage collection costs CPU time and memory headroom, and in exchange the program can't leak a forgotten object or use one after it's freed.

Takeaways

• A bytecode VM is a fetch-decode-execute loop in software, with its own program counter, stack and locals. The demo runs real JVM (IJVM) opcodes and returns the same 20 as the compiled code.
• Interpreting costs dozens of machine instructions per bytecode — about 50 here — for fetching, decoding, dispatch and keeping VM state in memory. JITs exist to remove that overhead.
• Stack VMs (JVM, CPython, WebAssembly) have compact bytecode; register VMs (Lua, Dalvik, V8's Ignition) execute fewer instructions. Dispatch is optimized with jump tables and threaded code.
• Reference counting frees objects as soon as their count hits zero, but can't free cycles on its own.
• Tracing collectors mark everything reachable from the roots and sweep the rest, cycles included.
• Real collectors compact, split objects into generations, and run concurrently to keep pauses short.