Skip to main content

Internal vs External Fragmentation

What This Concept Is​

Two distinct ways allocators "waste" memory:

  • Internal fragmentation is waste inside an allocated block. The block is bigger than the user asked for; the slack is attached to the allocation but cannot be used by anyone else. A 40-byte request rounded up to a 64-byte size class produces 24 bytes of internal fragmentation.
  • External fragmentation is waste between allocated blocks. Free memory exists, but it is scattered in pieces too small (or not correctly aligned) to satisfy a request. Total free bytes may be large; the largest contiguous free run may be tiny.

Both reduce usable memory; they require different mitigations.

Why It Matters Here​

Different allocation schemes trade these two:

  • Fixed-size blocks (slab, size-class allocators) have almost no external fragmentation within a pool, but can have substantial internal fragmentation (rounding up).
  • Variable-size best-fit/first-fit allocators (classical heap allocators) minimize internal fragmentation (they hand you close to what you asked for), but accumulate external fragmentation over time as free blocks proliferate.
  • Paging itself almost eliminates external fragmentation at the page-frame level, at the cost of internal fragmentation per allocation (the last page of every variable-sized region is partly wasted).
  • Segmentation has severe external fragmentation (big variable-sized segments) and little internal fragmentation.

Choosing an allocator is largely choosing which kind of waste you can tolerate. Measuring it is essential.

Concrete Example​

Internal fragmentation in jemalloc. A 40-byte allocation goes to the 48-byte size class: 8 bytes internal frag (~17%). A 1,000-byte allocation goes to the 1,024-byte class: 24 bytes internal frag (~2.4%). Size-class granularity controls this trade-off.

Internal fragmentation with pages. A 4100-byte anonymous mapping occupies 2 pages = 8,192 bytes. Internal fragmentation 4,092 bytes (~50%).

External fragmentation classic. A heap has 10 KiB total free in chunks of sizes 1, 2, 1, 3, 1, 2 KiB. A request for 5 KiB cannot be satisfied. Free memory is plentiful; usable memory is none.

Real-world signature on Linux. /proc/buddyinfo shows plenty of order-0 pages (single 4 KiB frames) but zero at orders 9, 10, 11. A driver's request for a 2 MiB contiguous buffer fails even though "there is lots of free memory." That is external fragmentation at the frame level.

Slab signature. slabinfo shows a cache with active_objs = 100,000 and num_objs = 200,000. Half the objects in the cache are unused but the slab pages are held. That is internal fragmentation inside the slab cache.

Common Confusion / Misconception​

"Fragmentation and leaks are the same problem." A leak is memory the allocator thinks is in use but the program no longer references. Fragmentation is memory the allocator correctly counts as free but cannot coalesce or serve. A leak grows RSS without bound; fragmentation typically reaches a steady state at some amplification factor.

"External fragmentation is solved by more RAM." Only until the request grows. A service handling progressively larger requests is vulnerable to external fragmentation even with plenty of memory.

"Paging eliminates fragmentation." It eliminates external fragmentation at the page-frame level but not at the huge-page level, and it introduces internal fragmentation per mapping.

How To Use It​

For a concrete application:

  1. Identify the allocation size distribution. Is it a tight cluster of a few sizes, or a long tail?
  2. For a tight cluster, size-class / slab wins; tiny internal frag, near-zero external frag.
  3. For a long tail with many distinct sizes, a general-purpose allocator with compaction or a mmap threshold (very large allocations go directly to mmap and are released directly) works better.
  4. Measure: compare virtual size (VSZ), resident set size (RSS), and used allocations (if the runtime reports it). The gap is fragmentation + cached free memory.

If RSS keeps creeping up but active-allocation bytes do not, suspect fragmentation; switching to a size-class allocator or enabling periodic trim can help.

Check Yourself​

  1. Give a one-sentence definition of each: internal and external fragmentation.
  2. For a fixed-size slab cache of 128-byte objects, what is the worst-case internal fragmentation for an allocation of 96 bytes?
  3. Why does paging eliminate external fragmentation at the frame level but not at the huge-page level?
  4. Why can a buddy allocator fail a 1 MiB allocation while /proc/meminfo shows 500 MiB free?

Mini Drill or Application​

  1. A size-class allocator offers classes {16, 32, 48, 64, 80, ...}. A workload allocates objects of sizes 20, 45, 65, 70, 100. For each, compute class selected and internal fragmentation.
  2. A process allocates then frees a random mix of 100, 200, ..., 1000-byte chunks in a tight loop. Sketch how external fragmentation might accumulate over time if the allocator is first-fit without coalescing.
  3. Read /proc/buddyinfo. Identify an external-fragmentation trend: when do higher orders empty out?
  4. Under what workload does a slab cache show high internal fragmentation, and what signal in slabinfo reveals it?
  5. A data-processing pipeline grows RSS from 4 GiB to 12 GiB over two hours while its live-object bytes (reported by the runtime) stay at ~3 GiB. What is the most likely explanation?

Read This Only If Stuck​