Generational GC

also: minor heap, major heap, write barrier, generational hypothesis, promotion

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.

A million-element list, which stays alive and so is all promoted.

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)

ocamlopt 5.5.1, default settings.

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.