Allocation Churn and the Locality of Recycled Memory

A program that allocates and frees a fixed number of blocks in a loop performs the same operations every iteration, yet its per-iteration cost is not constant. What changes is which physical memory it gets. The allocator’s free lists reorder over time, threads migrate between arenas, and the distance between the moment a block is freed and the moment it is handed out again drifts. Since that reuse distance determines whether the block is still in cache and still mapped in the TLB, churn converts the memory hierarchy from a benefit into a liability: the program keeps reusing the same logical buffers while paying cold-memory prices for them.

This is the effect that separates steady-state performance from warmup performance in allocation-heavy code, and it is not visible in allocation counts or in a profile of the allocator itself.

Reuse distance, not reuse existence

The allocator guarantees that a freed block becomes available. It does not guarantee when, to which thread, or in what order relative to other frees. A block that is freed and immediately reallocated by the same thread on the same size class is likely to be served from a per-thread cache, which is a stack-like structure: the most recently freed block is the first handed back. That yields a reuse distance of zero or one, and the block is still in L1.

A block that is freed by one thread and allocated by another may be handed out from a shared arena after an unknown number of intervening operations. If the receiving thread is on a different core, the block is in the other core’s cache and the first write triggers a cache-to-cache transfer. If enough time has passed, the block has been evicted all the way to DRAM, and the first touch is a full miss plus possibly a TLB miss.

The pattern is stable once established. A producer thread that allocates buffers and a consumer that frees them can settle into a steady state where every buffer crosses the interconnect twice: once when produced, once when consumed. The allocation call itself stays on its fast path, and the cost appears entirely in the consumer’s first write. The allocator’s own metrics look healthy.

The same effect appears without threads, through size-class drift. A loop that alternates between two block sizes uses two free lists and two regions of memory; a loop that cycles through twelve sizes uses twelve, spreading the live blocks over more of the address space. The per-operation cost rises because the blocks are further apart, not because the allocator is slower per call.

Why free lists lose locality over time

First-fit, best-fit, and segregated-fit allocators all degrade in the same direction under churn: the free list becomes a permutation of memory that no longer corresponds to allocation order.

Two mechanisms drive this. The first is coalescing. When a block is freed and its neighbour is also free, the allocator merges them into a larger block, which may then be split later at a different offset. Each merge-and-split cycle reshuffles boundaries, so blocks returned to the caller come from addresses that have no relationship to the ones returned in the previous iteration. Segregated allocators that avoid coalescing within size classes retain more of the original order, at the cost of external fragmentation across classes.

The second is that allocation order and free order are rarely the same. A program that allocates output buffers in request order and frees them in completion order, which is the normal shape of asynchronous processing, produces a free list that is the reverse permutation of the allocation sequence. Blocks are then handed back in a different order than they were created, and any code that pairs allocations by adjacency finds them unpaired.

The measured consequence is that placement quality, not allocator speed, dominates. Published comparisons of general-purpose allocators repeatedly find that the differences between designs in a tight benchmark are smaller than the differences a workload’s own reuse pattern induces once the program runs long enough for the free lists to permute.

Churn rate versus footprint

The relevant quantity is not the number of allocations but the number of distinct blocks in flight relative to the cache. A loop with fifty live buffers of 1 KiB each occupies 50 KiB, which fits in L1 or L2 regardless of churn; even a fully permuted free list serves warm memory. The same loop with ten thousand live buffers occupies 10 MiB and exceeds the last-level cache, so the reuse distance now matters and the churn penalty appears.

Stated as a relation: the churn cost is negligible while the live set fits the level the traversal reads from, and becomes a first-order cost once the live set exceeds it. This is exactly the working-set knee described in Working Set Size and the Miss-Rate Cliff, with the wrinkle that churn moves the effective footprint above the nominal one. A program with a 10 MiB live set that recycles blocks across a 40 MiB address range behaves like a 40 MiB footprint, because the addresses actually visited per iteration span that range.

/* Churn with a bounded live set. The same n blocks are recycled forever, but
 * nothing constrains them to stay within any particular span of the heap, so
 * the addresses visited per round drift as the allocator's free lists permute. */
#define N 10000

void churn(size_t rounds)
{
    void *live[N];
    for (size_t i = 0; i < N; i++)
        live[i] = malloc(1024);
    for (size_t r = 0; r < rounds; r++) {
        /* Free in reverse order, so the free list is the reverse permutation
         * of allocation order. */
        for (size_t i = N; i-- > 0; )
            free(live[i]);
        for (size_t i = 0; i < N; i++)
            live[i] = malloc(1024);
    }
}

The footprint of this loop is fixed at N blocks, but the addresses accessed per round depend on the allocator’s bookkeeping rather than on the program’s intent. Reordering the free loop to match allocation order changes nothing about correctness and preserves the free list’s correspondence with address order, which is often enough to keep the recycling local.

Strategies that reduce reuse distance

Four recurring approaches appear in systems that must sustain high churn.

Reuse by the same thread, same size class. Per-thread caches make the common single-threaded allocate-free cycle near-zero distance. The effect is lost when the producer and consumer of a buffer are different threads, which is why thread-crossing pipelines are the hard case.

Free in allocation order. Where the program controls the order of destruction, freeing in the same order as allocation leaves the free list closer to allocation order, so the next round’s allocations walk memory roughly sequentially. This costs nothing and requires only that the data structure holding the live blocks be a queue rather than a stack.

Reuse a bounded pool of the same buffers. A pool that holds exactly the maximum number of concurrent buffers and never returns them to the allocator fixes the address set permanently. The reuse distance becomes zero for every user, and the fault and TLB costs are paid once. The cost is that the pool’s capacity is a memory commitment for the lifetime of the process, which must be decided in advance.

Batch allocation. Allocating a generation’s worth of blocks from one arena and freeing the whole arena at once keeps the generation’s blocks adjacent and removes per-block bookkeeping from the hot path. The technique trades granularity for locality: memory cannot be reused until the whole generation retires, so peak footprint is higher. Arena and region-based allocation is the standard form of this idea, and it is the mechanism behind most high-churn production designs.

The four strategies are not exclusive. A pool built on arena allocation, freed in allocation order by the same thread that allocated it, has near-zero churn cost; each element alone gives part of the benefit.

Measuring churn

Since the effect is invisible to allocation counters, measurement must target the memory rather than the allocator. Three signals work.

Hardware counters for last-level cache misses and TLB misses, sampled over the run, rise when churn spreads the address range and stay flat when it does not. Comparing the same workload at two churn rates with the footprint held constant isolates the effect: if the miss count rises when the number of rounds rises, the free lists are losing locality.

The address distribution of live blocks is the second signal. Sampling the addresses of currently allocated blocks at intervals and computing how much of the address space they span, rather than how many bytes they occupy, measures the spread directly. A spread much larger than the live set’s total size is the condition under which churn costs.

The third signal is the first-touch fault count per round. If a steady-state loop that reuses its own memory is still incurring minor faults, the allocator is repeatedly returning regions to the kernel and getting them back. That is a different but related pathology, driven by the mapping and trimming behaviour of the allocator rather than by free-list order, and it shows up as a fault curve that never flattens, of the kind described in First-Touch Costs in Demand-Paged Memory.

Where churn is unavoidable

Churn cannot always be removed. A server that accepts connections, each with buffers, has a genuinely unbounded number of distinct allocations over its lifetime, and the reuse distance between a buffer’s release and its reuse by a different connection is set by the arrival pattern. The mitigation there is pooling with a hard capacity and a drop policy, not localisation.

The judgement to make is whether the churn is a property of the workload or an artifact of the implementation. A loop that allocates a temporary per iteration when it could reuse one buffer is an artifact, and removing it eliminates the churn entirely rather than mitigating it. Churn that is inherent to the workload is the case for pooling and batching, and the decision between them rests on whether the peak concurrency is bounded, which is a question about the workload rather than about the memory system.