When Fragmentation Turns into a Latency Problem

Fragmentation is usually presented as a space problem: free memory exists but is not usable because it is split into pieces of the wrong size. That framing leads to the wrong metric, because the free memory being unusable is only the visible half. The other half is that a program whose live objects are spread over a wide range of addresses pays more per access than the same objects packed together, even when the total bytes are identical and no allocation ever fails. Fragmentation becomes a performance problem long before it becomes an allocation-failure problem, and the two have different symptoms and different fixes.

Two kinds of fragmentation, two mechanisms

Internal fragmentation is waste inside an allocation: a request for 40 bytes served by a 48-byte chunk, or a 5 KiB buffer mapped onto two 4 KiB pages with most of the second unused. Its cost is capacity, and it is bounded by the rounding rules of the size classes.

External fragmentation is unusable free space between live objects. Its cost is also capacity when a request cannot be satisfied despite sufficient total free memory. But the reason external fragmentation produces a latency effect as well is that it increases the distance between live objects, and distance in the address space is what the translation layer charges for.

The translation layer has finite reach. A translation lookaside buffer holds some number of entries, commonly a few hundred to a couple of thousand per core across the levels, and each entry covers either 4 KiB or a larger page. The total address range the TLB can cover without a miss is the product of those two numbers: with a thousand 4 KiB entries the reach is about 4 MiB. A program whose live set spans more than that pays a page walk for accesses that miss in the TLB, and a page walk is itself several dependent memory accesses, because each level of the page table is a load whose result gives the next level’s address.

That dependence is the crux. A page walk costs not one memory latency but several in series, which makes a TLB miss more expensive than a data cache miss. When the walking is for a sequential stream of data, the hardware prefetcher and the page table walker overlap successive walks, and the cost is amortised. When the walking is for scattered accesses, each walk stands alone.

Why spread is invisible to byte counts

A program with a 200 MiB live set could have it in a contiguous 200 MiB region, or distributed across a 20 GiB address range in 64 KiB pieces. The byte count, and often the resident set size, are the same. The difference is that in the second case the working set touches three orders of magnitude more pages’ worth of address space, and the TLB reach is exceeded by a wide margin for any access pattern that is not strictly sequential.

Fragmentation creates spread in several ways. Repeated allocate-and-free cycles of mixed sizes leave holes that are filled by later allocations of different sizes, so a data structure’s objects end up in many regions rather than one. Growth sequences leave stranded large free blocks that cannot serve the next larger request, which pushes subsequent allocations to fresh regions and pushes the live set further apart. Long-running programs that allocate and release regions over years accumulate this spread slowly, which is why the symptom appears as degradation over uptime rather than as a discrete failure.

The measurement that exposes spread is the address range of live objects, not their count. Summing the sizes of live allocations gives the footprint; measuring the span from the lowest to the highest live address, and the number of distinct regions in between, gives the spread. A program with a 40 MiB footprint spanning 6 GiB has a translation problem regardless of how little memory it uses.

#include <stdio.h>
#include <stdlib.h>

/* Report the span of a sample of live objects, which is what the TLB sees.
 * The byte total is what a memory accounting tool reports; the span is the
 * quantity that decides page-walk frequency. */
#define SAMPLE 100000

int main(void)
{
    char **v = malloc(SAMPLE * sizeof *v);
    for (size_t i = 0; i < SAMPLE; i++)
        v[i] = malloc(4096);            /* 4 KiB each: one page per object */

    char *lo = v[0], *hi = v[0];
    for (size_t i = 1; i < SAMPLE; i++) {
        if (v[i] < lo) lo = v[i];
        if (v[i] > hi) hi = v[i];
    }
    printf("bytes=%zu span=%zuMiB\n",
           (size_t)SAMPLE * 4096, (size_t)(hi - lo) >> 20);
    return 0;
}

The byte total is fixed by the loop; the span printed varies with the allocator’s history. A span close to the byte total means the objects are packed; a span many times larger means they are not, and the accesses to them will walk page tables.

Huge pages as the reach fix

The direct remedy for insufficient TLB reach is fewer, larger pages. A 2 MiB page covers 512 times the address range of a 4 KiB page, so a TLB with the same number of entries covers 512 times as much memory, and the page table shrinks correspondingly: an x86-64 page table with 4 KiB pages has four levels, and using 2 MiB pages removes one level from the walk. The number of dependent loads per walk falls, as does the number of walks.

The catch is that huge pages require contiguity. On a system that has been running long enough to fragment physical memory, finding 512 contiguous 4 KiB frames may require compaction, which moves pages and is expensive; when compaction fails, the kernel falls back to small pages for that region. This is why the transparent huge page policy matters, and why madvise mode rather than always is often the appropriate configuration: the program knows which regions are large and long-lived enough to be worth the placement effort.

For applications whose live set is genuinely scattered, huge pages do not help, because neither the virtual nor the physical addresses are contiguous. The fix there is to change the allocation strategy rather than the page size: allocate the objects of a phase from a single region so that they are adjacent, and reuse that region across phases. That is the pooling approach described in Allocation Churn and the Locality of Recycled Memory, applied for its address-space effect rather than for its cache effect.

When compaction in user space pays

Compact-on-demand is the user-space equivalent: read the live objects, rewrite them into a fresh region in address order, and release the old region. The cost is proportional to the live set, since every object must be read and written once, plus the cost of updating every reference. The benefit is that all subsequent traversals see a smaller, denser address range.

Whether the trade pays depends on the ratio of compacted size to original span and on how many traversals follow. A compaction that halves the span and is followed by a million traversals is clearly worth it; one that is followed by one traversal is clearly not. The relevant comparison is bytes touched by the compaction versus bytes and translations saved across all subsequent traversals, which is computable before the work is done.

The complication is reference updating. Compaction requires either stable handles (indices rather than pointers, or a layer of indirection that survives the move) or the ability to find every pointer. The handle-based design is the subject of Shrinking Footprint with Narrow Handles and Inline Storage, and the two techniques compose: a structure that uses narrow handles is generally also one that can be relocated, because its internal references do not depend on absolute addresses.

Detecting that latency, not capacity, is the symptom

Three observations separate the latency effect from the capacity effect.

The first is whether the program’s resident memory grows while its live bytes do not. If RSS grows faster than the live set, the allocator is holding regions it cannot consolidate, and the spread is rising. Reading the process’s mapping list and its memory statistics distinguishes allocated from resident, and the ratio of the two over time is the trend.

The second is whether the cost of the same traversal rises over the lifetime of the process. A data structure that is traversed identically in minute one and hour twelve and takes longer in hour twelve is suffering from address drift, not from algorithmic change. Isolating the traversal from everything else is the point of the two-size measurement described in Working Set Size and the Miss-Rate Cliff.

The third is the fault and translation counters. Minor faults that continue after warmup mean regions are being returned to the kernel and re-obtained, which both costs faults and resets the address history. TLB miss counters that rise while the live byte count is flat are the signature of spread.

If none of the three shows a trend, fragmentation is not the explanation for the slowness, and the regimes of Bandwidth-Bound and Latency-Bound Work are the next place to look.

What actually bounds the damage

Fragmentation-induced latency is bounded by how much of the access stream is sequential. Sequence within a region pays one page walk for many accesses, because the walks for consecutive pages overlap. Random access across a wide span pays a walk per access for the subset that misses the TLB. The same program can therefore show a large fragmentation penalty in its random-hash phase and none in its scan phase, even though both touch the same objects.

The design consequence is that the cheap mitigation is often to reorder accesses rather than to compact memory. Sorting a set of objects by address before processing them turns random access into near-sequential access and lets each page’s translation be used for all the objects on it. The sort costs O(n log n) comparisons over a key that is usually already available, and it removes the translation cost entirely; where the processing is more expensive than the sort, that is the better trade. Where it is not, compaction or huge pages remain, and where none of the three applies, the latency is structural and belongs to the access pattern rather than to the allocator.