Incident report, coffee already cold:

process is too large
heap profiler says live objects are much smaller
the allocator insists nothing illegal happened

This is not rare. It is also not one bug wearing a trench coat.

The tempting word is “leak.” A leak is clean as a suspect: some object is still reachable by the allocator even though the program has lost the right to use it. Find the owner, cut the reference, watch the graph fall.

But many heap incidents are not leaks. They are accounting disagreements. The application asks for one number of bytes. The allocator rounds, splits, caches, coalesces, and maps pages in a different number of bytes. The operating system sees yet another number. RSS is the invoice, not the explanation.

So this post is a small memory forensics lab. The question on the wall is not:

is malloc fast?

The question is:

where did the bytes go?

Wilson, Johnstone, Neely, and Boles gave the allocator literature a useful warning label in their 1995 survey: random synthetic models can miss the regularities of real programs, and allocator policy often matters more than the low-level mechanism used to implement it.1 Johnstone and Wilson later showed a more optimistic side of the same point: on several real C and C++ programs, conventional allocators could exhibit near-zero fragmentation once implementation overheads were accounted for.2

Those two claims are not contradictory. Together they say: do not diagnose a heap with a folk theorem.

Exhibit A: Four Ledgers for One Trace

The simulator below runs the same allocation/free trace through four simplified allocators:

  • first fit: scan from low addresses and use the first free block that fits;
  • best fit: use the smallest free block that fits;
  • size classes: round requests to allocator classes, then place by best fit;
  • private caches: size classes plus one cached object per size class per thread, so a freed object may be quick to reuse by that thread but invisible to the central free list.

The private-cache row is a stress model, not a production allocator. It exists to make one question visible: when one thread frees an object, who is allowed to reuse that memory next?

Allocator forensics
Same trace, four ledgers

The canvas separates requested live bytes, rounding waste, free holes, and private cached slack. Nothing here moves an allocated object after the program receives a pointer.

synthetic trace
live request rounding waste free hole private cached slack

This is a policy microscope, not an allocator benchmark. Real allocators have page runs, arenas, huge-object paths, decay, scavenging, metadata, locks, NUMA effects, and OS return policies.

On the default trace, the program has about 22.6 KiB of live requested payload at the final snapshot. Best fit has committed 28 KiB, or about 1.27x the live bytes. First fit commits one extra page, 32 KiB, even though it has slightly less internal rounding waste. The size-class policy commits the same number of pages as best fit but spends about 8.3% of live payload on rounding. The private-cache stressor commits 60 KiB; about 26.7 KiB sits in per-thread cached blocks.

None of those numbers alone is “the fragmentation.” Each is a different line item in the bill.

Suspect 1: The Allocator Cannot Move the Furniture

Conventional C and C++ heap allocators are boxed in by a simple promise: after malloc returns a pointer, the allocator cannot later move the object and fix all copies of that pointer. Wilson et al. make this explicit in their model of general-purpose heap storage: the allocator knows sizes and free events, not the types and pointer graph inside the blocks.1

That constraint is why fragmentation is not just “run compaction.” A copying garbage collector can move live objects because it controls or discovers the references. A malloc implementation usually cannot. It must rearrange the map without moving the furniture.

This turns allocation into a historical process. Two heaps can contain the same live requests and still have different futures because the holes sit in different places. A large object does not care that total free memory is large. It cares whether a sufficiently large contiguous hole exists.

The lab’s “largest best-fit hole” metric is a small reminder of that fact. Free bytes are inventory. The largest hole is a capability.

Suspect 2: Rounding Bought a Market

Size classes look suspicious because they create internal fragmentation on purpose. Ask for 177 bytes and the allocator may hand you a 192-byte or 224-byte slot. That trailing space is real.

But the alternative is not free. Exact-size allocation can produce a zoo of tiny remainders, harder free-list searches, poor locality, and expensive metadata paths. Lea’s dlmalloc is an old but still instructive engineering document because it shows the allocator as a bundle of compromises: compatibility, portability, space, time, tunability, locality, and error detection all pull in different directions.3

jemalloc’s 2006 design makes the size-class trade explicit. Evans describes quantum-spaced classes for small allocations: more classes reduce average internal fragmentation, while segregated runs and bitmaps try to keep packing and lookup costs under control.4 The point is not that rounding is good or bad. The point is that rounding buys a simpler reuse market.

In the default lab trace, the size-class policy has more internal waste than best fit, but it does not commit more pages. Change the phase shift or seed and the answer can move. That is exactly the allocator problem: mechanism only has meaning under a workload.

Suspect 3: The Freed Block Went to the Wrong Desk

Single-threaded diagrams make free(x) look like a coin dropped back into one jar. Multithreaded allocators have more jars, and not every jar is on the same desk.

Per-thread caches and arenas reduce synchronization and often improve locality. They also introduce a question that a global heap never had to ask: if thread A allocates an object and thread B frees it, is that memory immediately useful to thread A’s next allocation?

Berger, McKinley, Blumofe, and Wilson put this problem at the center of Hoard. They call out producer-consumer patterns where memory consumption can grow because freed memory is not available to the thread that later needs it, and they design Hoard around per-processor heaps plus a global heap discipline that bounds this blowup.5

The private-cache row in the lab is a deliberately small version of that pressure. It caches at most one block per size class per thread. Even that is enough for visible slack when cross-thread frees are frequent. Set Cross-thread frees to zero and the story changes; increase Threads and the number of small private ledgers grows.

Modern allocators spend a lot of design effort making this trade livable. jemalloc, for example, emphasizes fragmentation avoidance and scalable concurrency, and its production story includes profiling and tuning hooks because the allocator has to be observable at scale.6

Bad Autopsy Has One Number

A bad heap autopsy reports one number:

RSS is high

A better one separates at least five:

requested live payload
allocated size after rounding
free bytes inside allocator spans
largest reusable hole or run
private or retained bytes not currently reusable by the caller that needs them

Then it asks when the peak occurred. Fragmentation at the final snapshot can be irrelevant if the incident happened during a phase transition. Wilson et al. argued that real programs have ramps, peaks, plateaus, phase behavior, and ordering dependencies that simple random traces erase.1 That is why allocator evaluation by “random sizes, random lifetimes” can be worse than uninformative. It can train your intuition on a workload your software never runs.

The default lab trace includes a phase shift for this reason. Early allocations are drawn from one size mix; later allocations drift toward another. Long-lived objects from the first phase survive into the second. Those survivors are the rocks in the river. Later allocations have to flow around them.

My First Six Questions

If I saw this in production, I would not start by changing allocators.

I would first ask for a ledger:

  1. live requested bytes by allocation site;
  2. live allocated bytes after allocator rounding;
  3. mapped, committed, resident, and returned-to-OS bytes over time;
  4. per-thread or per-arena retained bytes;
  5. object lifetime histograms by size class;
  6. the trace shape around the peak, not only the after-the-fire snapshot.

Only then would I choose a remedy. A real leak wants ownership work. Too much internal waste may want different object layout or size-class-aware pooling. A phase-change hole pattern may want lifetime segregation. Cross-thread retained slack may want allocator tuning, cache flushing, fewer arenas, different handoff patterns, or a workload-specific allocator.

The dangerous move is collapsing all of those into one word.

Fragmentation is not one substance. It is a ledger whose columns happen to add up to memory you paid for.

  1. Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles, “Dynamic Storage Allocation: A Survey and Critical Review”, International Workshop on Memory Management, 1995. ↩ ↩2 ↩3

  2. Mark S. Johnstone and Paul R. Wilson, “The Memory Fragmentation Problem: Solved?”, 1998. ↩

  3. Doug Lea, “A Memory Allocator”, describing dlmalloc’s goals and design tradeoffs. ↩

  4. Jason Evans, “A Scalable Concurrent malloc(3) Implementation for FreeBSD”, BSDCan 2006. ↩

  5. Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R. Wilson, “Hoard: A Scalable Memory Allocator for Multithreaded Applications”, ASPLOS 2000. ↩

  6. Jason Evans, “Scalable memory allocation using jemalloc”, Meta Engineering, 2011. ↩