How to Learn Cheney’s Copying Garbage Collector: Semispaces, Forwarding Pointers, Cheney Scans and Production Memory Management

How can a runtime reclaim an entire heap without recursively walking every live object and without compacting objects in place? Cheney’s copying collector answers with a remarkably concrete idea: split memory into two regions, copy only the reachable objects into the empty region, repair every pointer as you go, and then discard the old region all at once.

This article teaches Cheney’s algorithm as a Learning Hall progression from simple boxes-and-arrows memory diagrams to the engineering questions that matter in a real runtime. It complements the existing Schorr–Waite garbage-collection article: Schorr–Waite focuses on constant-space graph marking, while Cheney focuses on moving live objects into a new semispace.

Quick Read

Cheney’s collector is a copying, moving, tracing garbage collector.
The heap is divided into a from-space and a to-space; only one is used for allocation at a time.
Roots are copied first. Each moved object leaves behind a forwarding pointer so later references can find its new address.
Two pointers in to-space—commonly called scan and free—turn the copied region itself into the work queue.
Collection cost is driven mainly by the amount of live data, not by every byte of dead data.
The design compacts automatically and gives excellent bump-pointer allocation, but it reserves substantial extra space and moves objects.

1. Beginner Level: Memory Is a Graph

Start with the simplest useful picture. A program has some roots: references held in registers, stacks, globals or runtime metadata. Heap objects may contain references to other heap objects. If an object can be reached by following references from a root, the running program may still need it. If no root can reach it, the object is garbage.

This turns garbage collection into a graph problem. Roots are starting vertices, objects are vertices, and pointers are directed edges. A tracing collector needs to discover the reachable subgraph. Cheney’s extra move is that discovery and compaction happen together: when a live object is discovered, it is copied into the new space.

2. Why Two Semispaces?

Suppose the collector reserves two equal regions. During normal execution, allocation happens only in from-space. When from-space fills, collection begins. To-space starts empty.

Before collection: from-space contains a mixture of live and dead objects; to-space is empty.
During collection: reachable objects are copied into to-space.
After collection: to-space becomes the new active heap, the old from-space can be forgotten wholesale, and the roles swap.

The important simplification is that dead objects require no individual deletion. If they were never copied, they vanish when the old semispace is abandoned.

3. Forwarding Pointers Prevent Duplicate Copies

A live object may be referenced from several places. Copying it independently for every reference would duplicate identity and break the object graph. Cheney’s algorithm therefore records where an object went.

When object A is copied from old address A_old to new address A_new, the old object is overwritten or marked with a forwarding pointer to A_new. The next time the collector encounters A_old, it does not copy again. It simply rewrites that reference to A_new.

This is one of the core invariants to test: every live object is copied at most once, and every live reference eventually points into to-space.

4. The Elegant Part: scan and free

A naive graph traversal might keep a separate stack or queue of copied-but-not-yet-scanned objects. Cheney’s algorithm does not need one. The copied objects themselves form the queue.

free points to the next unused byte in to-space. New copies are appended there.
scan points to the next copied object whose fields still need to be examined.
Objects below scan are fully processed.
Objects between scan and free have been copied but may still contain old-space references.
Memory above free is unused.

The collection ends when scan == free. At that moment there are no copied-but-unscanned objects left, so the reachable closure is complete.

5. A Small Worked Example

Imagine a root R pointing to object A. A points to B and C. B also points to C. Object D is unreachable.

Copy A to to-space and rewrite R to A’s new address.
Set scan to the start of A and free just after A.
Scan A. Its B reference causes B to be copied. Its C reference causes C to be copied.
Advance scan to B. When B’s pointer reaches old C, C already has a forwarding pointer, so B’s field is rewritten to the same new C.
Advance scan to C and scan its fields.
Now scan reaches free. Collection stops.
D was never reached and therefore never copied.

The new heap contains A, B and C packed together. D disappears automatically with the old semispace.

6. Core Pseudocode

free = start_of_to_space
scan = start_of_to_space

for each root reference r:
    r = evacuate(r)

while scan < free:
    object = object_at(scan)
    for each pointer field p in object:
        p = evacuate(p)
    scan += size(object)

swap(from_space, to_space)

function evacuate(old_ref):
    if old_ref is null:
        return null
    if old_ref is not in from_space:
        return old_ref
    if old_ref already has forwarding pointer:
        return forwarding_target(old_ref)

    new_ref = copy_object_to(free, old_ref)
    free += size(old_ref)
    install_forwarding_pointer(old_ref, new_ref)
    return new_ref

The exact representation of headers, object sizes and forwarding metadata is runtime-specific. The algorithmic job is stable: copy once, remember the destination, and ensure every pointer field is eventually rewritten.

7. A Teaching Simulator in Python

from collections import deque

# A high-level simulator: object names stand in for machine addresses.
heap = {
    "A": ["B", "C"],
    "B": ["C"],
    "C": [],
    "D": ["D"],   # unreachable garbage
}
roots = ["A"]

forward = {}
to_space = {}
work = deque()

def evacuate(name):
    if name is None:
        return None
    if name in forward:
        return forward[name]

    new_name = f"new_{name}"
    forward[name] = new_name
    to_space[new_name] = list(heap[name])
    work.append(new_name)
    return new_name

new_roots = [evacuate(r) for r in roots]

while work:
    obj = work.popleft()
    rewritten = []
    for old_child in to_space[obj]:
        rewritten.append(evacuate(old_child))
    to_space[obj] = rewritten

print(new_roots)
print(to_space)

This simulator uses a separate deque so the control flow is easy to see. The real Cheney insight is stronger: contiguous to-space plus the scan/free pointers can represent that queue without an external data structure.

8. Correctness Invariants

No duplicate identity: every from-space object gets at most one destination.
Processed prefix: every object before scan has had all pointer fields rewritten.
Pending interval: every object between scan and free is known live but may still need scanning.
No lost roots: every root that once referenced a live object is updated to its copied version.
Closure: if a copied object references another reachable from-space object, that target is eventually copied or redirected to its prior copy.
Termination: each newly discovered live object advances free, while scan advances through each copied object once.

These invariants are more useful than memorising the loop. They let you reason about corrupted pointers, duplicate copies and incomplete scans.

9. Complexity: Think in Live Bytes

If L is the total size of live objects and P is the number of pointer fields scanned inside them, collection work is proportional to the live graph copied and inspected. Dead objects are not individually traversed. That makes copying collection attractive when much of the heap is garbage at collection time.

Allocation between collections can be extremely cheap: check that enough room remains and advance a bump pointer. Compaction is also automatic because copied objects are densely packed in to-space.

10. The Cost You Pay: Space and Movement

The classic two-semispace design can use only roughly half of the reserved region for active allocation at a time. It also changes object addresses. A runtime therefore needs a reliable way to discover and rewrite every relevant pointer.

Raw external pointers can be difficult or impossible to update safely.
Pinned objects cannot simply be moved.
Large objects may be handled by a different region or policy.
Weak references, finalizers, ephemerons and concurrent mutation introduce semantics beyond the basic algorithm.
Precise collectors need trustworthy object-layout metadata so they know which words are pointers.

These are not defects in the teaching model. They are the boundary between the core algorithm and a production memory manager.

11. Why Copying Can Improve Locality

Copying compacts surviving objects into a dense region. Dense allocation can improve cache and virtual-memory locality compared with a badly fragmented heap. The effect is workload-dependent: breadth-first copying does not guarantee the perfect placement for every future access pattern, but it removes holes and makes subsequent bump allocation contiguous.

This is a professional lesson in algorithm evaluation: asymptotic complexity is not the whole machine. Memory layout, cache behaviour, bandwidth and pause-time goals matter too.

12. From Cheney to Modern Generational Collection

Many modern runtimes do not use one pure two-semispace collector for the entire heap. Nevertheless, evacuation remains a central technique: young-generation collectors and region-based collectors often copy surviving objects out of one area into another. Forwarding information, root updates and evacuation queues are therefore still professionally relevant ideas.

The important distinction is conceptual. Cheney’s algorithm gives a clean baseline for moving tracing collection; a production collector may add generations, remembered sets, barriers, parallel workers, concurrent phases, pinned regions and special object categories.

13. Failure Modes to Test

Two different old objects accidentally receive the same new address.
The same old object is copied twice because the forwarding marker is installed too late.
A root is missed and its object is reclaimed even though the program still needs it.
A non-pointer integer is mistaken for an address.
An interior pointer is updated incorrectly.
Object size is decoded wrongly, causing scan to land in the middle of an object.
Alignment rules are violated when free advances.
A cyclic object graph loops because forwarding state is ignored.
A pointer to outside from-space is incorrectly evacuated.
Collection runs out of to-space because the live set exceeds the available destination capacity.

14. Professional Testing Strategy

Do not test only acyclic toy lists. Generate heaps containing sharing, self-cycles, long chains, wide graphs, null fields, unreachable cycles, objects of different sizes and roots that alias the same object. After collection, verify graph isomorphism: reachable identities and edges should be preserved even though addresses changed.

Then add runtime-specific stress: collection at every allocation, minimal semispace headroom, randomized object layouts, repeated flips between semispaces and checks that no surviving pointer targets the abandoned space.

15. Learning Progression: Beginner to Professional

Beginner: draw roots and heap objects; cross out unreachable objects.
Intermediate: simulate copying and forwarding pointers by hand on a shared cyclic graph.
Advanced: implement a toy semispace with scan/free offsets and variable-sized objects.
Professional: add precise root maps, alignment, stress tests, telemetry for live bytes copied, and compare locality/pause behaviour with a mark-sweep design.

16. Practice Problems

Why does B pointing to C not cause a second copy of C in the worked example?
Construct a three-object cycle and trace scan/free until collection terminates.
Show why the region between scan and free corresponds to a queue of gray objects in the tri-colour abstraction.
Measure copied bytes when 10%, 50% and 90% of a toy heap is live.
Implement a deliberate bug that installs forwarding pointers after scanning; find a graph that exposes it.
Compare breadth-first copying order with a depth-first copying order and inspect the resulting object layout.
Design a test that proves no pointer in the new heap still references the abandoned semispace.

17. Sources and Further Reading

Final idea: Cheney’s algorithm is memorable because the data structure and the traversal strategy collapse into the same space. The new heap is not merely where objects end up; while collection is running, it is also the collector’s queue. That is a powerful algorithm-design pattern: sometimes the structure being built can carry the state needed to build it.

Small Group Tutorials