Mark-Sweep and the Fragmentation It Leaves Behind

A tracing collector that marks correctly has only finished half its work. The dead objects are identified, but nothing has been made allocatable, and the bytes they occupy are still interleaved with live data in whatever order the program happened to allocate them. The sweep pass turns mark bits into free space. The trouble is that the space it produces is shaped by the program’s history, and a heap whose free space is a large number of small holes will fail to satisfy a request for one medium-sized object even though the total free bytes are more than sufficient.

Fragmentation is therefore not an incidental cost of mark-sweep but its central weakness, and every allocation policy that lives on top of a sweeping collector is an attempt to manage it.

The sweep itself is trivially simple

Given a mark bitmap and a heap laid out in address order, the sweep is a linear walk. For each granule, read the mark bit; if it is clear the granule is dead, and the corresponding bit in a free bitmap is set; if it is set the granule is live, and the mark bit is cleared so the next cycle starts from a clean slate. The cost is proportional to the heap size divided by the granule size, and the walk is sequential in memory, which hardware prefetchers handle well.

/* Bitmap sweep: one mark bit and one free bit per granule. */
void sweep(size_t ngranules, uint8_t *marks, uint8_t *free_bits) {
    for (size_t i = 0; i < ngranules; i++) {
        uint8_t bit = (uint8_t)(1u << (i % 8));
        if (marks[i / 8] & bit) {
            marks[i / 8] &= (uint8_t)~bit;     /* live: clear for the next cycle */
            free_bits[i / 8] &= (uint8_t)~bit; /* and the granule is not free */
        } else {
            free_bits[i / 8] |= bit;           /* dead: the granule is reusable */
        }
    }
}

With a side bitmap the sweep produces a free bitmap from which contiguous runs of dead granules can be extracted in one scan, and each run becomes one free-list insertion. That matters because insertion into a sorted list is the expensive part of building the free structure, so the number of runs, not the number of dead granules, sets the cost. With per-object mark bits and variable sizes, the sweep must walk object headers to find each object’s extent, and each header touch is a potential cache miss on a heap that no longer fits in cache.

Why the resulting free space is the wrong shape

Consider a heap of 1 MiB managed as 16-byte granules, in which a long-lived object at the beginning is followed by ten thousand 32-byte objects that all die at once. The sweep produces roughly 300 KiB of contiguous free space, and any request up to that size can be served. Now consider the same heap in which every other 32-byte object survives: the sweep produces five thousand separate 32-byte holes. The total free space is the same, but the largest contiguous run is 32 bytes.

That second shape is what real programs produce, because live and dead objects interleave according to allocation order rather than according to lifetime. The 1995 survey of dynamic storage allocation by Wilson, Johnstone, Neely, and Boles reviews the measurements that exist and concludes that the space lost depends heavily on the object size distribution and on whether object lifetimes are correlated, and it states the general result that no placement policy avoids severe fragmentation for some request sequence.

There are two responses. The first is to accept fragmentation and make allocation fast enough that the wasted bytes are affordable. The second is to move objects, which is compaction, and is the subject of mark-compact and the forwarding problem.

Free lists, and why one list is not enough

A first-fit allocator keeps a list of free blocks sorted by address and walks it until it finds one large enough. Best-fit walks the whole list and takes the smallest adequate block. Both are O(n) in the number of free blocks in the worst case, and both suffer from the same pathology: splitting a block to satisfy a request leaves a remainder that is often too small to be useful, so the number of list entries grows while the useful free space shrinks.

Segregated free lists fix the search cost by bucketing blocks by size. A request of size s goes to the bucket covering s, and the allocator takes the first block from that bucket. Blocks larger than the bucket’s range are split, with the remainder returned to an appropriate bucket. This is the design used by most production allocators, including the size-class machinery in modern C allocators and in managed runtimes’ non-moving spaces, and it turns allocation into a constant-time operation in the common case.

The cost is internal fragmentation. A request for 33 bytes served from a 48-byte size class wastes 15 bytes, and the waste is systematic rather than accidental. Size classes are chosen geometrically, often with a ratio around 1.1 to 1.25 between consecutive classes, so the worst-case waste per object is bounded by the ratio: at 1.25, a request can waste up to a fifth of the block. At a 1.1 ratio the waste falls to under a tenth but the number of classes, and therefore the number of partially used pages, rises.

/* Size classes: geometric spacing bounds per-object waste. */
static const size_t classes[] = {16, 32, 48, 64, 80, 96, 128, 160, 192, 256, 320, 512};
#define NCLASSES (sizeof classes / sizeof classes[0])

static int class_for(size_t n) {
    for (int i = 0; i < (int)NCLASSES; i++)
        if (classes[i] >= n) return i;
    return -1;              /* too large for the segregated heap */
}

Coalescing, and the price of adjacency

When two adjacent blocks are both free, merging them produces a block that can serve larger requests. Coalescing requires knowing whether the physically neighbouring block is free, which is done either with boundary tags or with a bitmap of free granules.

Boundary tags place a footer at the end of each block recording its size and status, so the allocator can step backwards from a block’s start to find the preceding block’s header. That is four to sixteen bytes of overhead per allocation, and it doubles the number of cache lines touched during a free. For a heap of millions of 24-byte objects the footer is a serious fraction of memory.

A free-granule bitmap avoids the per-object overhead. One bit per granule marks whether that granule is free; coalescing becomes a scan of adjacent bits, and the whole bitmap is small enough to stay in cache. The catch is that a block’s extent must be discoverable, which requires either a header with the size or an allocation-side record, and the bitmap must be maintained on every split and merge. Bitmap-based coalescing also makes allocation’s fast path slightly slower, since the search for a free run is a bit-scan over the bitmap rather than a pointer dereference.

The pathological case for coalescing is a heap in which a single long-lived object sits in the middle of a region that otherwise churns. The object splits the region permanently, and no amount of merging on either side can join the two halves. This is the classic reason non-moving collectors develop a “popular object” problem, and it has no solution within the non-moving design.

Allocation-time behaviour and the bump-pointer contrast

A non-moving allocator’s allocation cost depends on the free list’s state. With a segregated list and a non-empty bucket, allocation is a few instructions: pop the head, adjust the size, return the pointer. With an empty bucket the allocator must split a larger block, and with no larger block it must either request more memory from the operating system or trigger a collection.

The contrast with a copying allocator is stark. A bump allocator keeps a single pointer into a contiguous region and allocates by adding the object size and returning the old value. That is one addition and one store, no list traversal, no size-class lookup, and perfect locality for the newly allocated objects because they are laid out in allocation order. The cost is that the region must be contiguous, which means objects must be moved to keep it so. That is the trade that copying collection and Cheney’s algorithm makes explicit.

For a managed runtime, the choice is usually made per generation rather than globally: a bump-allocated nursery for short-lived objects, and a mark-sweep or mark-compact space for the survivors. That split is what generational collection and write barriers is built on.

When fragmentation becomes a correctness problem

Fragmentation is normally a performance issue: the heap grows to hold the same live data, and the operating system supplies more pages. It becomes a correctness issue when the heap cannot grow, which happens on embedded systems, inside a fixed-size arena, or when the runtime has committed to a maximum heap size.

In that situation the collector can fail to satisfy an allocation even though the live set is well below the heap size. The failure surfaces as an out-of-memory condition caused by the shape of free space rather than by its quantity, and the standard remedy is to run a compacting collection as a last resort. That is exactly what several production collectors do: sweep normally, and compact only when a large allocation cannot be satisfied, which keeps the moving cost off the common path while retaining the ability to recover.

A second correctness-adjacent effect is on the program’s own assumptions. A runtime that hands out raw pointers into the heap cannot move objects without updating every pointer, so fragmentation is unfixable in that design. A runtime that hands out handles, or that can find and rewrite all pointers, can compact. The distinction between those two object models is what decides whether a collector has compaction available as a fallback at all, and it is the constraint that shapes the next stage of collector design.