Mark-Compact: Sliding Objects Without a Second Semispace

A mark-sweep collector can fail an allocation for a 200 KiB object in a 64 MiB heap that is 30 percent live, because the free space is five thousand small holes rather than one large one. The remedy is to move the live objects together so that the free space becomes a single contiguous region. Copying collection does this by evacuating to a second semispace, which costs half the address space. Mark-compact does it in place, sliding objects toward one end of the same heap, and that difference is what makes compaction viable for a large old generation where reserving a second copy is unacceptable.

The in-place constraint creates the central difficulty. When an object moves to an arbitrary address, every pointer to it must be rewritten, including pointers in objects that have not moved yet and pointers in objects that have already moved. There is no second region in which to leave the original intact, so the old copy’s location must be repurposed to hold the new address, and that repurposing must not be confused with an ordinary object.

The two passes, and why one is not enough

Compaction is normally done in three phases over the marked heap: compute each live object’s new address, update every pointer to use the new address, and then move the bytes.

The computation phase walks the heap in address order, accumulating the sizes of live objects, and records for each live object the address it will occupy. The recording is the problem: with N live objects, storing N new addresses requires space proportional to N, which the collector may not have. Three techniques are used. A side table indexed by object stores one address per live object. A break table stores only the points at which the displacement between old and new addresses changes, so its size is proportional to the number of runs of live objects rather than to the number of objects. An in-place technique overwrites the object’s own first word with its new address, which works only if the size and mark bit have already been moved somewhere the collector can still find them.

The update phase walks the heap again, this time examining every pointer field of every live object and every root, and replaces each pointer with the object’s new address. To do that it must map old address to new address, using the same structure the computation phase produced.

The move phase walks the heap once more, copying each live object’s bytes to its new address. The direction of the walk matters: if objects slide toward lower addresses, moving in ascending address order means each object is copied before any later object is moved into its space, so the copy is safe. Sliding toward higher addresses requires the opposite order. Getting this backwards corrupts data, and the failure is intermittent because it depends on the sizes involved.

/* Compute phase: slide toward lower addresses and record a break table.
   A break entry is needed wherever the old-to-new displacement changes,
   which happens exactly where a run of dead objects is skipped. */
struct brk { char *old_addr; char *new_addr; };

static size_t compute(char *base, char *end, uint8_t *marks,
                      struct brk *table, size_t cap) {
    char *free_ptr = base;
    size_t n = 0;
    for (char *p = base; p < end; ) {
        struct header *h = (struct header *)p;
        size_t idx = (size_t)(p - base) / GRANULE;
        if (marks[idx / 8] & (1u << (idx % 8))) {
            if (n == 0 || table[n - 1].new_addr - table[n - 1].old_addr
                          != free_ptr - p) {
                if (n == cap) abort();     /* table too small: see below */
                table[n].old_addr = p;     /* displacement changes here */
                table[n].new_addr = free_ptr;
                n++;
            }
            free_ptr += h->size;
        }
        p += h->size;
    }
    return n;                              /* entries used in the table */
}

Forwarding pointers versus break tables

Writing the new address into the object’s header is the simplest forwarding scheme, but it overwrites information the object needs: the header held the size and the mark bit, and after the overwrite the collector can no longer distinguish a forwarded object from an ordinary one by looking at the header alone. Implementations resolve this by encoding a tag in the low bits of the stored address, or by keeping the size in a side map indexed by address so that the header is free to be overwritten.

A break table takes a different approach. Instead of storing one new address per object, it stores the boundaries at which the mapping from old to new address changes. Between two consecutive break points the displacement is constant, so an old address maps to a new one by adding a fixed offset found through a search of the table. The table’s size is proportional to the number of runs of live objects, not to the number of objects, which for a heap with large clusters of survivors is far smaller. The cost is a search per pointer update, though a binary search over a small table is cheap and the table usually fits in cache.

The break-table technique is associated with Bartlett’s work on compacting with ambiguous roots, where the collector cannot distinguish pointers from integers in the stack and registers. It compacts the heap and builds a table mapping old addresses to new, then uses that table during the update phase of the collection to rewrite every pointer it can find. For the ambiguous roots the collector does what it can: a stack word whose value maps to a moved object is rewritten, on the assumption that it was a pointer, while a word that does not map is left alone. The break table makes this feasible because its size is proportional to the number of runs of live objects, so the update pass can search it cheaply, but it is still a structure used only inside the collection, not an indirection the program pays on every load.

Does object order matter?

Sliding compaction preserves the relative order of objects: the first live object stays first, the second stays second, and so on. That is convenient for a mark-sweep heap, because address order corresponds to the order in which the heap was built, and the new addresses are computable by a single forward walk.

Order preservation is not required for correctness, and a collector that ignores it can do better on locality. If the collector knows which objects are used together, from a profile or from the traversal order of the marking phase, it can place them adjacently and improve cache behaviour. The cost is that computing the mapping now requires knowing the placement policy, which usually means the new order is derived from a separate traversal rather than from address order, and the break table or forwarding array becomes larger and less regular.

There is a stronger reason order can matter: a compacting collector must not break interior pointers. If the runtime allows a pointer into the middle of an object, such as a pointer to an array element or to a field, the collector must be able to map that interior address to the object’s new base plus the same offset. With sliding compaction that is a simple subtraction of the old base, but it requires knowing the old base from the interior address, which requires a search of the object map. Runtimes that forbid interior pointers avoid the problem; runtimes that permit them, such as those exposing arrays to native code, pay for a base-lookup on every such pointer.

The cost model compared with copying

Both compaction and copying move the live set, so both cost roughly one copy per live byte plus one rewrite per pointer. The difference is in what else is needed.

Copying needs a destination region, which for a semispace design is half the heap, and it needs no forwarding structure beyond the old copy’s header, because the old copy is intact until the collection ends and the whole from-space is discarded. Compaction needs no destination region but does need a forwarding structure covering every live object, and it touches the heap three times rather than two: once to compute addresses, once to update pointers, once to move bytes. The extra pass over the live set is a real cost, and it is why compacting collectors are typically used for the old generation where collections are infrequent, while copying collectors are used for the young generation where they happen constantly.

A collector that compacts must also handle the same root set a marker walks, which is why the root enumeration is shared between the two designs. The three passes can be fused. A single pass that walks the heap, computes the new address for each live object, and immediately moves it, works if the pointer update can be done later, but it cannot, because the pointer fields inside the moved object still contain old addresses and will be updated in the second pass, which reads the object at its new location. Fusing the compute and move phases is possible with a careful ordering, but the pointer update must still traverse the whole live set after all moves are known.

Incremental and concurrent compaction

Compaction is harder to make concurrent than marking. Marking only needs to keep the black-white invariant, which a write barrier can maintain. Compaction moves objects, so any thread reading an object’s address concurrently may observe a half-moved state. The collector must either stop the world for the move, or arrange for the program to use an indirection that can be updated atomically.

The standard concurrent approach divides the heap into regions and compacts one region at a time, with a read barrier on every object access that forwards the access if the object has moved. That is the mechanism used by collectors that promise low pause times on large heaps: the mark phase runs concurrently with a write barrier, and the compaction phase runs region by region with a read barrier, so no single pause covers the whole heap. The read barrier’s cost is a check on every load of a reference, which is significant and is why such collectors accept it only when the pause requirement justifies it.

A cheaper middle ground is to compact only part of the heap. A collector can compact the regions with the most free space and leave the rest alone, which reduces pause time and still consolidates enough contiguous free space to satisfy large allocations. The policy question, how much to compact to recover how much contiguous space, is a scheduling decision, and the answer depends on the allocation pattern rather than on any property of the collector.

Failure modes specific to in-place movement

Three things go wrong in practice.

The first is a stale forwarding entry. If the compute phase records a new address for an object that later turns out to be unreachable, which cannot happen if marking is correct but can happen if the mark phase and the compute phase see different heap states, the update phase will write a pointer to a location that holds another object. This is why compaction runs with the world stopped unless the marking is concurrent and the barriers are correct.

The second is an object whose size is not known to the collector, typically one allocated by foreign code. Such an object cannot be slid, so it must be pinned, and pinning splits the free region that compaction was meant to create. Runtimes that support pinning typically keep pinned objects in a separate non-moving space to preserve compaction’s benefit for everything else.

The third is the interaction with weak references. A weak reference points at an object without keeping it alive; after compaction the object may have moved, and the weak reference must be updated or cleared. Updating requires the forwarding information to still be available when weak processing runs, which constrains the order of phases: weak references are usually processed after marking and before or during compaction, and the exact ordering determines whether a weak reference can be resurrected. That ordering problem is treated in weak references and finalization.