Copying Collection, Cheney Scanning, and the Bump Pointer

Split a heap into two equal halves and use only one at a time. When the active half fills, copy every live object into the other half, packed against one end, and switch roles. The dead objects are simply left behind in the abandoned half, which is then declared free in its entirety. No free list is built, no fragmentation is possible, and allocation in the new half is a single pointer increment. The price is that half the address space is unavailable at any moment, and the price of that price is that the collector must be able to copy every object and rewrite every pointer to it.

Copying is one of the earliest compacting schemes, and the details that make it work are worth following closely, because they explain why copying collectors are fast for short-lived data and why they are unsuitable for large heaps without a generational structure on top.

Allocation in two instructions

A bump allocator holds a pointer to the next free byte. Allocation rounds the requested size up to an alignment, adds it to the pointer, and returns the old value. A comparison against the region’s end detects exhaustion and triggers a collection.

static char *alloc_ptr, *alloc_end;

void *bump_alloc(size_t n) {
    n = (n + 7u) & ~(size_t)7u;              /* 8-byte alignment */
    if (alloc_ptr + n > alloc_end) {
        collect_and_flip();                  /* rewrites alloc_ptr */
        if (alloc_ptr + n > alloc_end) return NULL;
    }
    void *p = alloc_ptr;
    alloc_ptr += n;
    return p;
}

There is nothing else in the fast path: no size lookup, no free-list walk, no header write. The newly allocated objects are contiguous in address order, so an allocation loop produces data that occupies whole cache lines and streams well. This is the main reason copying collectors can outperform free-list allocators on allocation-heavy workloads even though the collection itself does more work per byte.

The catch is that the size must be recorded somewhere, because a copying collector has to know how much to copy. Objects need a header with their size, or the runtime needs an out-of-line size map per type, which is the common arrangement in managed runtimes: the size is a function of the class, so no per-object field is needed, and the header holds a class pointer and flags instead.

The copy loop and why order does not matter

Collection proceeds in two halves. First, the roots are scanned: for each root pointer that refers into the from-space, the object is copied to the to-space and the root is updated to the new address. Second, the copied objects are scanned: each pointer field of each copied object is examined, and any field pointing into from-space causes its target to be copied and the field rewritten.

The invariant that makes this correct is that once an object has been copied, all references to it must be rewritten to the new address, including references that have not been visited yet. The mechanism is a forwarding pointer: the old copy’s first word is overwritten with the new address, marked in a way that distinguishes it from an ordinary object. When a pointer is found pointing into from-space, the collector reads the first word; if it is a forwarding pointer, the object has already moved and the pointer is simply updated to the recorded address. If it is an ordinary header, the object is copied, the forwarding pointer is written into the old copy, and the pointer is updated.

static struct obj *forward(struct obj *p) {
    if (!in_from_space(p)) return p;
    if (is_forwarded(p)) return forwarded_to(p);
    struct obj *q = copy_to_space(p);
    set_forwarding(p, q);
    return q;
}

static char *scan_ptr, *free_ptr;   /* both inside to-space */

static void scan(void) {
    /* forward() may extend free_ptr, so the bound is re-read each step. */
    while (scan_ptr < free_ptr) {
        struct obj *o = (struct obj *)scan_ptr;
        for (size_t i = 0; i < pointer_field_count(o); i++) {
            struct obj **f = pointer_field(o, i);
            *f = forward(*f);
        }
        scan_ptr += object_size(o);      /* advance by the object's extent */
    }
}

Cheney’s trick: the scan pointer is the queue

The naive version of this loop needs a queue of copied objects awaiting scanning, and that queue can be as large as the live set. Cheney’s 1970 paper removes the queue entirely by observing that the to-space is itself the queue.

Two pointers divide the to-space. The free pointer marks where the next object will be allocated; the scan pointer marks where scanning has reached. Every byte between the start of to-space and the scan pointer belongs to an object that has already been scanned; every byte between the scan pointer and the free pointer belongs to an object that has been copied but not scanned. Scanning advances the scan pointer to the next object’s start; copying advances the free pointer. The traversal is breadth-first, and the queue is the interval between the two pointers.

Baker’s work on real-time list processing took the same copying primitive in a different direction, interleaving the copy with execution to bound the pause. The consequence of Cheney’s arrangement is that a copying collection needs no auxiliary stack at all, so a linked list of arbitrary depth does not overflow anything. That property alone makes Cheney’s algorithm the default for semispace collectors, and it is the reason a copying collector does not need the pointer-reversal machinery described in reachability from roots.

What the live set actually costs

The work of a semispace collection is proportional to the live data, not to the heap. Copying costs one memcpy per surviving object plus one pointer rewrite per pointer field, and the pointer rewrite touches the to-space copy, which was just written and is therefore in cache. For a heap where 90 percent of the bytes are garbage, the collection moves only a tenth of the heap, which is why copying collectors are described as having a cost proportional to survival rather than to allocation.

The flip side is that the same property makes them catastrophic when survival is high. A heap that is 90 percent live costs nine times as much per collection as one that is 10 percent live, and the space overhead is 100 percent regardless. This is precisely the observation that motivates generational collection: if most objects die young, put the young objects in a small semispace and let the old ones stay put.

The address-space question

Allocating two semispaces does not necessarily require twice the physical memory. The from-space is never read except during the collection, and its pages can be returned to the operating system or simply left uncommitted while the to-space grows into them. On a system with virtual memory and demand paging, a semispace that is never touched costs page-table entries and nothing else. On a system without an MMU, or with a heap in a fixed physical arena, the halving is real and the design becomes expensive.

There is a related cost that is easy to overlook: the collector must be able to tell whether a pointer refers into from-space. With semispaces of known bounds the test is two comparisons, but a heap with multiple spaces, large objects allocated outside the semispaces, and objects in native memory makes the test more involved. Implementations use a page map or a coarse-grained address table to answer “which space does this address belong to” in a few instructions, and that table is itself a structure the collector must maintain.

Large objects break the pure semispace model. Copying a 10 MiB array costs 10 MiB of memcpy and provides no benefit, since the array’s survival is usually all-or-nothing. The standard treatment is to allocate objects above a threshold in a separate large-object space that is collected by mark-sweep rather than by copying, so the copying collector only ever handles objects below the threshold. That hybrid is why a “copying collector” in a real runtime usually has a non-copying region alongside it, with the fragmentation concerns of mark-sweep and free lists confined to that region.

Pinning, handles, and the cost of moving

Moving objects is only possible if every reference to them can be found. A runtime that exposes raw addresses to native code cannot move an object that native code holds. The usual solution is a handle table: native code holds an index, the runtime translates it to the current address on each access, and the object is free to move. The translation costs an indirection per access, and the table must be scanned as part of the root set, which is why the handle mechanism in a foreign-function interface is both a convenience and a performance boundary.

Within the managed heap, the collector must find all pointers without help from the program. That requires either precise layout metadata, the same type descriptor the marker uses, or a constraint on where pointers may appear. Conservative collection, which treats any word that looks like a heap address as a pointer, cannot move objects, because it cannot rewrite the words it guessed about. That incompatibility is fundamental: conservative stack scanning is a technique for non-moving collectors only.

Copying also changes what the program can assume about object identity. Two references to the same object remain equal because both are updated, but any integer derived from an address changes value across a collection, and any hash computed from an address is invalidated. Runtimes that expose identity hashes therefore compute them from a stable field or from the object’s contents, never from its address.

The remaining question for a copying design is how to avoid copying the old generation repeatedly, which is where the generational structure and its write barrier come in, treated in generational collection and write barriers.