Generational GC

A garbage collector that splits the heap by age, because most objects die young: new objects go to a small nursery collected often by copying, and survivors are promoted to a larger heap collected rarely. A write barrier records old-to-young pointers so that a minor collection need not scan the old heap.

OCaml allocates into a minor heap, 256k words by default, by bumping a pointer. When it fills, a minor collection copies whatever is still reachable into the major heap and resets the pointer. Objects that died in the meantime cost nothing to collect, because a copying collector only touches the live ones.

let () =
  let s0 = Gc.quick_stat () in
  let xs = List.init 1_000_000 (fun i -> i) in
  let s1 = Gc.quick_stat () in
  Printf.printf "minor collections: %d\npromoted words: %.0f\nlist length: %d\n"
    (s1.minor_collections - s0.minor_collections)
    (s1.promoted_words -. s0.promoted_words)
    (List.length xs)

minor collections: 25
promoted words: 5781602
list length: 1000000

A minor collection finds live young objects from the roots and from the remembered set: every field of an old object that has been made to point at a young one. Mutation keeps that set up to date through the write barrier, which is why C stubs must write fields with Store_field or caml_modify rather than a plain assignment, and why mutating old objects is slower than allocating new ones.

• Weak referenceA weak reference is a pointer the garbage collector ignores when deciding reachability, so a cache or registry can refer to a value without keeping it alive; once nothing else refers to the value, it may be collected and the weak reference then reads as empty. Weak references alone do not make a memo table safe, because a cached value that mentions its key keeps the key alive through the table. An ephemeron fixes this: it holds a key weakly and a value that is retained only while the key is reachable from elsewhere.
• Space leakMemory a program holds longer than it needs to. In a lazy language the usual cause is a chain of unevaluated thunks: a lazy left fold over a list builds one suspended addition per element and only performs them at the end. A heap profile by closure type shows it as a growing THUNK band.
• BoxingBoxing is storing a value in a separately allocated heap block and handling it through a pointer to that block. Polymorphic languages box values so that every value fits in one machine word and generic code can copy and pass any value the same way; OCaml boxes floats, tuples and other structured values but keeps small integers and constant constructors unboxed as tagged words. The cost is an allocation and an indirection per value, which compilers avoid where they can by unboxing values whose type is known.
• Chase–Lev dequeThe Chase–Lev deque is the lock-free double-ended queue used by work-stealing schedulers. Its owner thread pushes and pops tasks at the bottom with plain reads and writes, and other threads steal from the top with a compare-and-swap; the two ends only contend when one element is left, which both sides resolve with the same compare-and-swap on the top index. The buffer is a circular array that grows when full. Correctness depends on a store-load ordering in pop that weak memory models require a fence to provide.
• Cheney's algorithmCheney's algorithm is a copying garbage collector that moves every live object from one half of the heap, from-space, to the other, to-space, in breadth-first order, using the copied objects themselves as the queue: a scan pointer follows the free pointer through to-space, copying whatever the scanned objects point to. It needs no stack or extra memory, leaves a forwarding address in each moved object so shared and cyclic structures are copied once, compacts the live data, and costs time proportional to the live data, not the heap. It is the basis of the young-generation collectors of most language runtimes.
• ClosureA closure is a function value together with the environment in which it was created: the bindings of the free variables its body refers to. Closures are what make functions first-class values in a lexically scoped language. Compilers implement them by closure conversion, which turns each function into a code pointer paired with a record of captured values.

1. [1]H. Lieberman, C. Hewitt, “A real-time garbage collector based on the lifetimes of objects”, Communications of the ACM 26 (1983).
2. [2]D. Ungar, “Generation scavenging: a non-disruptive high performance storage reclamation algorithm”, ACM Software Engineering Symposium on Practical Software Development Environments (1984).
3. [3]D. Doligez, X. Leroy, “A concurrent, generational garbage collector for a multithreaded implementation of ML”, POPL (1993).

last updated 25 September 2026