Memory management and runtime systems

A language definition says what programs mean; a runtime system is the machinery that makes that meaning happen on real hardware. Two of its jobs dominate language design. The first is memory management: deciding when storage for a value can be reused, either explicitly as in C, automatically by a garbage collector as in Java, Python, Go and JavaScript, or through compile-time ownership rules as in Rust. The second is execution: running code by interpreting an abstract syntax tree, by interpreting compact bytecode on a virtual machine, by compiling ahead of time to machine code, or by compiling just in time while the program runs. This lesson implements the classic garbage collection algorithms on a simulated heap, measures the real collectors in Python and Go, compiles to and runs a small stack machine, and examines Rust's ownership as an alternative. The machine-level view of stacks and heaps belongs to CMPUT-379 and code generation to CMPUT-415; here the focus is on the language-level contract.

Lifetimes and the three storage classes

Every value has a lifetime. Static storage lasts for the whole run (global variables, string literals). Stack storage lasts for the activation of the function that created it, so it is freed automatically and cheaply on return, but cannot outlive that call. Heap storage has a lifetime not tied to any one call, which is needed for values that escape their creator: closures that capture variables (lesson 4), objects returned from functions, and data structures that grow. The whole problem of memory management is deciding when a heap value is dead.

Reachability is the practical stand-in for liveness. A value is live if the program will use it again, which is undecidable in general (it would solve the halting problem, a theme of CMPUT-474). A collector instead keeps everything reachable from the roots: global variables, the registers and the stack frames of every thread. Anything unreachable can never be used again, so it is certainly garbage. Some reachable values are also garbage, which is why programs with automatic memory management can still leak memory, for instance through a cache that is never cleared.

Mark and sweep

John McCarthy invented garbage collection for Lisp in 1959, with the mark and sweep algorithm. Marking traverses the object graph from the roots and sets a mark on each object reached; sweeping scans the whole heap and frees every unmarked object. Mark and sweep handles cycles naturally, because a cycle that is unreachable is simply never marked.

# A tiny simulated heap: objects are numbered cells with lists of outgoing pointers.
class Heap:
    def __init__(self): self.cells, self.next = {}, 0
    def alloc(self, *refs):
        self.next += 1; self.cells[self.next] = list(refs); return self.next

def mark_sweep(heap, roots):
    marked, stack = set(), list(roots)
    while stack:                                   # mark: everything reachable from roots
        a = stack.pop()
        if a in marked: continue
        marked.add(a); stack.extend(heap.cells[a])
    garbage = sorted(set(heap.cells) - marked)     # sweep: free everything unmarked
    for a in garbage: del heap.cells[a]
    return marked, garbage

h = Heap()
leaf1, leaf2 = h.alloc(), h.alloc()
tree = h.alloc(leaf1, leaf2)                       # 3 -> 1, 2
lone = h.alloc()                                   # 4: nothing points to it
c1 = h.alloc(); c2 = h.alloc(c1); h.cells[c1].append(c2)   # 5 <-> 6: an unreachable cycle
shared = h.alloc(tree)                             # 7 -> 3
roots = [shared]
live, freed = mark_sweep(h, roots)
print("live :", sorted(live))
print("freed:", freed)

live : [1, 2, 3, 7]
freed: [4, 5, 6]

Mark and sweep has two drawbacks. Sweeping takes time proportional to the whole heap, not just the live data, and the freed cells are scattered, so the heap becomes fragmented and allocation must search free lists. Mark-compact collectors fix fragmentation by sliding live objects together after marking, at the price of updating every pointer.

Reference counting

Reference counting, introduced by George Collins in 1960, keeps a count of pointers to each object and frees the object the moment its count drops to zero. That gives prompt, incremental reclamation and predictable timing, which is why CPython, Swift and Objective-C use it. Its weaknesses are the overhead of updating counts on every pointer assignment (atomically, in multithreaded programs) and cycles: objects that point to each other keep each other's counts above zero forever. CPython therefore adds a tracing cycle collector, and Swift asks programmers to break cycles with weak references.

# Reference counting frees most objects immediately, but not cycles.
import gc, sys, weakref

class Node:
    def __init__(self, name): self.name, self.other = name, None
    def __del__(self): print(f"  freed {self.name}")

gc.disable()                       # use only reference counting for now
print("acyclic:")
a = Node("a"); r = weakref.ref(a)
print("  refcount of a (getrefcount adds one):", sys.getrefcount(a))
del a                              # count drops to zero: freed at once

print("cycle:")
x, y = Node("x"), Node("y")
x.other, y.other = y, x            # x and y point at each other
del x, y                           # counts stay at 1: nothing printed
print("  after del, before collection")
print("  cycle collector found", gc.collect(), "unreachable objects")
gc.enable()

acyclic:
  refcount of a (getrefcount adds one): 2
  freed a
cycle:
  after del, before collection
  freed x
  freed y
  cycle collector found 9 unreachable objects

Copying collection

A copying collector divides the heap into two halves. Allocation takes memory from one half, from-space, by simply bumping a pointer, which is as cheap as stack allocation. When from-space fills, the collector copies every reachable object into the other half, to-space, leaving a forwarding address behind so that shared objects are copied once, and then the halves swap roles. C. J. Cheney's 1970 algorithm does this breadth-first using to-space itself as the queue. The work is proportional to the live data only; garbage is never even looked at. The cost is that half the memory is idle at any time.

# Cheney's copying collector (1970): copy live objects to to-space breadth-first.
def cheney(from_space, roots):
    to_space, forward = [], {}                     # forward: from-address -> to-address
    def copy(a):
        if a not in forward:
            forward[a] = len(to_space)
            to_space.append(list(from_space[a]))   # copy the cell (pointers still old)
        return forward[a]
    new_roots = [copy(r) for r in roots]
    scan = 0
    while scan < len(to_space):                    # to_space doubles as the work queue
        to_space[scan] = [copy(p) for p in to_space[scan]]
        scan += 1
    return to_space, new_roots, forward

# from-space: 0 and 3 are garbage; 1 -> 4 -> 2, 2 -> 1 (a live cycle)
from_space = [[3], [4], [1], [0], [2], []]
to_space, roots, fwd = cheney(from_space, roots=[1])
print("forwarding:", fwd)
print("to-space  :", to_space, " roots:", roots)
print(f"copied {len(to_space)} of {len(from_space)} cells; garbage never touched")

forwarding: {1: 0, 4: 1, 2: 2}
to-space  : [[1], [2], [0]]  roots: [0]
copied 3 of 6 cells; garbage never touched

Generational and concurrent collection

The generational hypothesis, observed by Henry Lieberman and Carl Hewitt (1983) and David Ungar (1984), says that most objects die young. A generational collector allocates new objects in a small nursery and collects it often with a fast copying collection; the few survivors are promoted to an older generation that is collected rarely. Because the nursery is mostly garbage, each minor collection copies very little. A write barrier records pointers from old objects to young ones, so that a minor collection need not scan the old generation.

# Why generational collection works: most objects die young.
import random
rng = random.Random(325)
lifetimes = [int(rng.expovariate(1 / 3)) if rng.random() < 0.9 else rng.randint(50, 500)
             for _ in range(100_000)]              # 90% short-lived, 10% long-lived
for limit in (1, 5, 10, 50):
    dead = sum(1 for t in lifetimes if t < limit)
    print(f"dead before {limit:3} allocations' time: {100 * dead / len(lifetimes):5.1f}%")

dead before   1 allocations' time:  25.5%
dead before   5 allocations' time:  73.2%
dead before  10 allocations' time:  86.9%
dead before  50 allocations' time:  90.1%

import gc
print("generations:", len(gc.get_threshold()), "thresholds:", gc.get_threshold())
gc.collect()
junk = [[i] for i in range(10_000)]               # many small container objects
print("objects in generation 0 after allocating:", gc.get_count()[0] > 0)

generations: 3 thresholds: (2000, 10, 10)
objects in generation 0 after allocating: True

Modern collectors also run concurrently with the program to keep pauses short. Edsger Dijkstra and colleagues described tri-color marking in 1978: objects are white (not yet seen), gray (seen, children not yet scanned) or black (done), and a barrier preserves the invariant that no black object points to a white one while the program keeps mutating the graph. Go's collector is a concurrent tri-color mark and sweep tuned for sub-millisecond pauses; Java offers several, including G1 (the default since Java 9), ZGC and Shenandoah, which keep pauses in the low milliseconds even on very large heaps.

package main

import (
	"fmt"
	"runtime"
)

type point struct{ x, y int }

func newPoint(x, y int) *point { return &point{x, y} } // escapes: must live on the heap

func main() {
	var before, after runtime.MemStats
	runtime.GC()
	runtime.ReadMemStats(&before)
	keep := make([]*point, 0, 100000)
	for i := 0; i < 100000; i++ {
		keep = append(keep, newPoint(i, i))
	}
	runtime.ReadMemStats(&after)
	fmt.Println("points kept:", len(keep))
	fmt.Println("heap objects allocated >= 100000:", after.Mallocs-before.Mallocs >= 100000)
	keep = nil
	runtime.GC()
	var done runtime.MemStats
	runtime.ReadMemStats(&done)
	fmt.Println("collections ran since start:", done.NumGC > before.NumGC)
}

points kept: 100000
heap objects allocated >= 100000: true
collections ran since start: true

Ownership: memory safety without a collector

Rust takes a third path. Every value has exactly one owner; when the owner goes out of scope, the value is dropped and its memory freed, deterministically, as with C++ destructors (the idiom called resource acquisition is initialization, or RAII). Assigning or passing a value moves ownership, after which the old name may not be used. Code that only needs to look at a value borrows it through a reference, and the borrow checker ensures that references never outlive their referent and that a value is never mutated while shared. The result is memory safety with no garbage collector and no run-time cost, at the price of a more demanding type system. Its theory draws on linear and affine type systems, in which a value must be used exactly once or at most once.

fn total(v: Vec<i32>) -> i32 { v.iter().sum() }     // takes ownership of v

fn main() {
    let v = vec![1, 2, 3];
    let t = total(v);                // v is moved into total and freed when total returns
    println!("total = {}", t);
    println!("first = {}", v[0]);    // use after move: rejected at compile time
}

error[E0382]: borrow of moved value: `v`
 --> main.rs:7:28
  |
4 |     let v = vec![1, 2, 3];
  |         - move occurs because `v` has type `Vec<i32>`, which does not implement the `Copy` trait
5 |     let t = total(v);                // v is moved into total and freed when total returns
  |                   - value moved here
6 |     println!("total = {}", t);
7 |     println!("first = {}", v[0]);    // use after move: rejected at compile time
  |                            ^ value borrowed here after move
  |
note: consider changing this parameter type in function `total` to borrow instead if owning the value isn't necessary
 --> main.rs:1:13
  |
1 | fn total(v: Vec<i32>) -> i32 { v.iter().sum() }     // takes ownership of v
  |    -----    ^^^^^^^^ this parameter takes ownership of the value
  |    |
  |    in this function
help: consider cloning the value if the performance cost is acceptable
  |
5 |     let t = total(v.clone());                // v is moved into total and freed when total returns
  |                    ++++++++
error: aborting due to 1 previous error
For more information about this error, try `rustc --explain E0382`.

struct Buffer { name: String }
impl Drop for Buffer {
    fn drop(&mut self) { println!("dropping {}", self.name); }   // runs deterministically
}

fn length(b: &Buffer) -> usize { b.name.len() }              // borrows, does not own

fn main() {
    let a = Buffer { name: String::from("outer") };
    {
        let b = Buffer { name: String::from("inner") };
        println!("lengths {} {}", length(&a), length(&b));
    }                                                          // b dropped here
    let c = a;                                                 // ownership moves to c
    println!("moved, now using {}", c.name);
}                                                              // c dropped here

lengths 5 5
dropping inner
moved, now using outer
dropping outer

The output shows destruction happening at precise points: inner is dropped at the end of its block, before outer, and outer, moved into c, is dropped when c's scope ends. In a garbage-collected language the same program would free both buffers at some unspecified later time, which is why Java and Python need try-with-resources and with statements for files and locks.

Executing programs: interpreters, bytecode and virtual machines

The simplest implementation is a tree-walking interpreter, like those of lessons 3 and 5, which evaluates the abstract syntax tree directly. It is easy to write but slow, because every step chases pointers and dispatches on node types. Most dynamic languages instead compile to bytecode, a compact instruction set for a virtual machine, and interpret that. CPython compiles each function to stack-based bytecode, which the dis module displays.

import dis

def poly(x):
    return 3 * x * x + 2 * x + 1

dis.dis(poly)
print(poly.__code__.co_consts, poly(4))

  3           RESUME                   0

  4           LOAD_CONST               1 (3)
              LOAD_FAST                0 (x)
              BINARY_OP                5 (*)
              LOAD_FAST                0 (x)
              BINARY_OP                5 (*)
              LOAD_CONST               2 (2)
              LOAD_FAST                0 (x)
              BINARY_OP                5 (*)
              BINARY_OP                0 (+)
              LOAD_CONST               3 (1)
              BINARY_OP                0 (+)
              RETURN_VALUE
(None, 3, 2, 1) 57

Below we write our own compiler from expression trees to stack bytecode, with a conditional jump, and a virtual machine to run it. The same design, scaled up, underlies the Java virtual machine, the .NET common language runtime, CPython, and the WebAssembly standard, which is a stack machine designed in 2017 as a portable, sandboxed compilation target for browsers and now runs outside them too.

# A stack-based virtual machine and a compiler from expression trees to its bytecode.
def compile_expr(e, code):
    if isinstance(e, (int, float)): code.append(("PUSH", e))
    elif isinstance(e, str):        code.append(("LOAD", e))
    elif e[0] == "if0":                                    # ("if0", test, then, else)
        compile_expr(e[1], code); jz = len(code); code.append(None)
        compile_expr(e[3], code); jmp = len(code); code.append(None)
        code[jz] = ("JZ", len(code)); compile_expr(e[2], code)
        code[jmp] = ("JMP", len(code))
    else:
        op, a, b = e
        compile_expr(a, code); compile_expr(b, code); code.append((op,))
    return code

def run(code, env):
    stack, pc, steps = [], 0, 0
    ops = {"ADD": lambda a, b: a + b, "SUB": lambda a, b: a - b, "MUL": lambda a, b: a * b}
    while pc < len(code):
        ins = code[pc]; pc += 1; steps += 1
        if ins[0] == "PUSH": stack.append(ins[1])
        elif ins[0] == "LOAD": stack.append(env[ins[1]])
        elif ins[0] == "JZ":
            if stack.pop() == 0: pc = ins[1]
        elif ins[0] == "JMP": pc = ins[1]
        else: b, a = stack.pop(), stack.pop(); stack.append(ops[ins[0]](a, b))
    return stack.pop(), steps

expr = ("if0", ("SUB", "x", 4), ("MUL", 100, "x"), ("ADD", ("MUL", 3, ("MUL", "x", "x")), 1))
code = compile_expr(expr, [])
for i, ins in enumerate(code): print(f"{i:2} {' '.join(map(str, ins))}")
for x in (4, 5):
    print(f"x = {x}: result {run(code, {'x': x})[0]} in {run(code, {'x': x})[1]} instructions")

 0 LOAD x
 1 PUSH 4
 2 SUB
 3 JZ 12
 4 PUSH 3
 5 LOAD x
 6 LOAD x
 7 MUL
 8 MUL
 9 PUSH 1
10 ADD
11 JMP 15
12 PUSH 100
13 LOAD x
14 MUL
x = 4: result 400 in 7 instructions
x = 5: result 76 in 12 instructions

A just-in-time (JIT) compiler starts by interpreting and counts how often each function or loop runs. Hot code is compiled to machine code using what the runtime has observed, for example that a variable has always held a small integer, protected by cheap guards; if a guard fails, the code is deoptimized back to the interpreter. This is how V8 makes JavaScript fast despite dynamic typing, and how the HotSpot JVM inlines virtual calls (lesson 9). Futamura's projections (1971) give a striking theoretical link: specializing an interpreter to a fixed program yields a compiled version of that program, an idea that the GraalVM Truffle framework uses in practice. The details of code generation are the subject of CMPUT-415.

Worked examples