Allocation and fragmentation

Why it matters

A service whose memory creeps up for days without any leak, a C++ or Rust program that gets dramatically faster by switching allocators, a Python process that never gives memory back to the OS, a cache that uses twice the memory its contents suggest: these are allocator and fragmentation stories. The allocator is the layer between your new and the kernel's pages, and it decides both speed and footprint for every allocation-heavy program.

The idea

The kernel hands out memory in pages, through brk (growing the heap) and mmap (mapping new regions). Programs allocate objects of arbitrary sizes, many tiny and short-lived. The memory allocator (malloc in C, the runtime allocator in Go, Java, Rust or Python) sits between them: it requests large chunks from the kernel and carves them into objects, recycling freed objects for later requests.

How a modern allocator works

1. 1

   Size classes

   Requests are rounded up to a small set of sizes (8, 16, 32, 48, 64 bytes and so on). Each class has its own pool of same-sized slots, so finding space is a list pop, and freeing is a list push.
2. 2

   Per-thread caches

   Each thread keeps a small cache of free slots per size class, so most allocations and frees touch no lock and no shared memory at all.
3. 3

   Arenas and central pools

   Thread caches refill from and return to larger shared pools (arenas), with locking only on that slower path.
4. 4

   Large allocations

   Objects above a threshold (often 128 KB or more) get their own mapping straight from the kernel and are returned to it on free.
5. 5

   Returning memory

   Pages that become entirely free can be given back to the kernel (madvise), but allocators often keep them for reuse, trading footprint for speed.

jemalloc, tcmalloc and mimalloc all follow this shape; glibc's malloc does too, with less aggressive per-thread caching, which is why heavily multithreaded C and C++ services often switch.

Fragmentation

External fragmentation means free memory exists but is scattered in pieces too small or too dispersed to satisfy requests or to return to the kernel. In long-running services it shows as resident memory that keeps growing even though live data is flat: a few live objects pin each partly used page, so the allocator cannot release it, and new allocations of different sizes need new pages. Internal fragmentation is the slack inside each block from rounding up to a size class or page; it is bounded and predictable, typically 10 to 25 percent.

Patterns that make it worse or better

Mixing short-lived and long-lived objects of many sizes in the same pools is the classic recipe for growth: the long-lived ones pin pages that are otherwise empty. Remedies: allocate long-lived structures up front or from a dedicated arena; use arena (region) allocation for request-scoped objects, freeing the whole region at the end of the request in one step; pool and reuse fixed-size objects (buffers, connections); and choose an allocator that returns memory and defragments better. In garbage-collected languages, compacting collectors move objects together and eliminate external fragmentation, at the cost of moving them.

Kernel allocators

The kernel has the same problem for its own objects. Linux uses the buddy allocator for physical pages (splitting and merging power-of-two blocks) and slab allocators (SLUB) for kernel objects of fixed types, which is where the idea of per-type caches of preconstructed objects comes from.

Trade-offs

Size classes and per-thread caches make allocation fast and add internal waste and memory held per thread. Keeping freed memory speeds reuse and raises footprint; returning it eagerly saves memory and causes page-fault churn. Arenas make allocation nearly free and require objects to share a lifetime. Compaction removes fragmentation and costs pauses or copying.

In an interview

Explain memory growth without a leak: "The heap profile shows live data flat at 4 GB but resident memory at 9 GB and growing. That is fragmentation from long-lived cache entries interleaved with request garbage; we moved the cache to its own arena and switched to jemalloc with background purging, and RSS stabilised at about 5 GB."