Cheney's algorithm

Cheney's algorithm is a copying garbage collector. The heap is split into two halves, and allocation takes place in one of them, from-space, by incrementing a pointer. When it is full, the collector copies every object reachable from the program's roots into the other half, to-space, and the two halves swap roles; whatever was not copied is garbage and is reclaimed by doing nothing at all^[1]. The copying proceeds breadth-first, and the queue of objects still to be examined is to-space itself: a scan pointer walks through the copied objects while a free pointer marks where the next copy goes, so the collector needs no stack or auxiliary memory. Its cost is proportional to the amount of live data, not the size of the heap, which is why it is the basis of the young-generation collectors of most generational runtimes^[4].

Copying an object allocates space for it at the free pointer in to-space, copies its words there, and overwrites the original with a forwarding address, the location of the copy. A later attempt to copy the same object finds the forwarding address and returns it, so an object referenced many times, or from a cycle, is copied exactly once and every reference is redirected to the same copy. The collection then runs^[1]:

1. Copy the objects referenced by the roots, and update the roots to the copies.

2. Set the scan pointer to the start of to-space. While scan is behind free, take the object at scan, copy each object its fields point to and replace the field with the copy's address, and advance scan past the object.

3. When scan reaches free, every reachable object has been copied and every field updated. Swap the semispaces; allocation continues at free.

The region between scan and free is exactly the queue of a breadth-first traversal of the object graph, stored in the objects themselves. In the terminology of tri-colour marking, objects before scan are black, those between scan and free grey, and those not yet copied white.

(* A simulated heap of words. An object is a header word holding its
   number of fields, followed by the fields. A field is either an integer
   n, stored as 2n + 1, or a pointer to an object, stored as twice the
   object's address; 0 is the null pointer (address 0 is never used).
   The memory is split into two semispaces; allocation bumps a pointer in
   the current one. *)
let semi = 64
let mem = Array.make ((2 * semi) + 1) 0
let from_base = ref 1 and to_base = ref (semi + 1)
let alloc_ptr = ref 1
 
let int_ n = (2 * n) + 1
let is_ptr v = v <> 0 && v land 1 = 0
let addr v = v / 2
let ptr a = 2 * a
 
exception Full
 
let alloc fields =
  let n = List.length fields in
  if !alloc_ptr + n + 1 > !from_base + semi then raise Full;
  let a = !alloc_ptr in
  mem.(a) <- n;
  List.iteri (fun i f -> mem.(a + 1 + i) <- f) fields;
  alloc_ptr := a + n + 1;
  ptr a
 
let field v i = mem.(addr v + 1 + i)
let set_field v i x = mem.(addr v + 1 + i) <- x
let size v = mem.(addr v)

open Heap
 
(* Cheney's algorithm. A forwarded object has its header overwritten by
   -1 and its first word by the address of its copy. *)
let copied_words = ref 0
 
let collect roots =
  let free = ref !to_base in
  let copy v =
    if not (is_ptr v) then v
    else begin
      let a = addr v in
      if mem.(a) = -1 then ptr mem.(a + 1)          (* already copied *)
      else begin
        let n = mem.(a) and dst = !free in
        Array.blit mem a mem dst (n + 1);
        free := dst + n + 1;
        copied_words := !copied_words + n + 1;
        mem.(a) <- -1; mem.(a + 1) <- dst;          (* leave a forwarding address *)
        ptr dst
      end
    end
  in
  (* Copy what the roots point to, then scan the copies in order: every
     object between scan and free has been copied but its fields still
     point into from-space. The scan catches up with free when everything
     reachable has been copied. *)
  let roots = List.map copy roots in
  let scan = ref !to_base in
  while !scan < !free do
    let n = mem.(!scan) in
    for i = 1 to n do mem.(!scan + i) <- copy mem.(!scan + i) done;
    scan := !scan + n + 1
  done;
  let t = !from_base in
  from_base := !to_base; to_base := t; alloc_ptr := !free;
  roots

before: 44 words in use
after:  20 words in use (20 copied)
list:   1 :: 2 :: 3 :: []
pair:   both fields point to the same copy: true, value 42
cycle:  a.next.next == a: true
to-space layout, in copying order:
  @65  [1; ->74]
  @68  [->77; ->77]
  @71  [7; ->79]
  @74  [2; ->82]
  @77  [42]
  @79  [8; ->71]
  @82  [3; null]

The 44 words in use before the collection include six garbage objects; the 20 words after are exactly the live ones, now contiguous. The two fields of the pair still point to one shared object, and the cycle is intact. The layout shows the breadth-first order: the three objects the roots reference come first, then the objects they reference, and so on. The integers are tagged with a low bit of 1 so that the collector can tell them from pointers without any type information, the same representation OCaml uses^[11].

The collector visits each live object once and each field of each live object once. For a heap whose semispaces hold $H$ words, of which $L$ are live at collection time, a collection costs $O(L)$ and frees $H-L$ words for allocation, so the collection cost per allocated word is

which tends to zero as the heap grows relative to the live data^[4]. Garbage costs nothing: it is never touched. Allocation is a pointer increment and a limit check, as cheap as on a stack. Appel observed that with a large enough heap, copying collection can be cheaper than explicit freeing^[8].

(* A program that allocates a great deal and keeps little: the collector
   only ever touches the live objects. *)
open Heap

allocated 300000 words in 5555 collections of a 64-word semispace
words copied by the collector: 49995 (9.0 per collection)

Each collection copies the same nine words, the three live cells, however much garbage has accumulated, and the total copying work is a sixth of the allocation. The price is space: a copying collector can use only half of the memory it reserves, and it must be able to move objects, which rules out conservative collection for languages that let programs hold raw addresses.

Copying compacts the live objects, which removes fragmentation and makes allocation trivial, and it changes their order. Breadth-first order places an object's children together but far from the object, which can hurt locality when a program walks a structure depth-first. Moon's approximately depth-first variant scans the most recently copied page first^[9], and Wilson, Lam and Moher studied orderings that keep related objects on the same pages^[10]. Fenichel and Yochelson's earlier copying collector used a recursive, depth-first traversal, which needed a stack as deep as the longest chain of references^[2]; Cheney's scan pointer removed the need for it.

Most objects die young. Generational collectors exploit this by allocating in a small nursery that is collected often by copying, promoting the survivors into an older generation that is collected rarely^[5][6]. A copying nursery collection costs time proportional to the few survivors, and Cheney's scan is the usual way to do it; the references from the old generation into the nursery, recorded by a write barrier, are treated as extra roots. OCaml's minor heap works this way: survivors of a minor collection are copied into the major heap^[11]. Baker made copying collection incremental by copying objects on demand whenever the program reads a from-space pointer, so that the collector can run in small steps interleaved with the program^[7].

Minsky described a copying collector for Lisp that copied live data to secondary storage and back in 1963^[3]. Fenichel and Yochelson gave a two-semispace collector for virtual memory in 1969^[2], and Cheney published the non-recursive breadth-first version in 1970^[1]. Baker's real-time copying collector followed in 1978^[7], and in 1983–1984 Lieberman and Hewitt and Ungar made copying collection of young objects the core of generational garbage collection^[5][6].

• Generational GCA 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.
• Weak referenceA pointer the collector is allowed to ignore when deciding reachability, so a cache can hold a value without keeping it alive. An ephemeron strengthens this to a key/value pair where the value is retained only while the key is independently reachable, which is what makes a memo table not leak.
• 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.

1. [1]C. J. Cheney, “A nonrecursive list compacting algorithm”, Communications of the ACM 13 (1970).
2. [2]R. R. Fenichel, J. C. Yochelson, “A LISP garbage-collector for virtual-memory computer systems”, Communications of the ACM 12 (1969).
3. [3]M. L. Minsky, “A LISP garbage collector algorithm using serial secondary storage”, MIT AI Memo 58 (1963).
4. [4]R. Jones, A. Hosking, E. Moss, The Garbage Collection Handbook: The Art of Automatic Memory Management, ch. 4, CRC Press (2011).
5. [5]H. Lieberman, C. Hewitt, “A real-time garbage collector based on the lifetimes of objects”, Communications of the ACM 26 (1983).
6. [6]D. Ungar, “Generation scavenging: a non-disruptive high performance storage reclamation algorithm”, Software Engineering Symposium on Practical Software Development Environments (1984).
7. [7]H. G. Baker, “List processing in real time on a serial computer”, Communications of the ACM 21 (1978).
8. [8]A. W. Appel, “Simple generational garbage collection and fast allocation”, Software: Practice and Experience 19 (1989).
9. [9]D. A. Moon, “Garbage collection in a large Lisp system”, LISP and Functional Programming (1984).
10. [10]P. R. Wilson, M. S. Lam, T. G. Moher, “Effective “static-graph” reorganization to improve locality in garbage-collected systems”, PLDI (1991).
11. [11]Y. Minsky, A. Madhavapeddy, J. Hickey, Real World OCaml, ch. “Understanding the Garbage Collector”, Cambridge University Press (2nd ed., 2022).

last updated 27 September 2026