Memory Allocators

Every time your program calls malloc(), it hands a puzzle to a piece of system software that most programmers never think about: the memory allocator. The heap is a finite stretch of bytes. The allocator must hand out chunks of the right size, track which parts are free, and eventually reuse them — all in microseconds, thousands of times per second.

The core tension is simple: fragmentation. After many allocations and frees, the free space can scatter into dozens of small gaps that together would fit a new request but individually can't. An allocator that grabs memory too greedily wastes space; one that splits it too finely turns the heap into Swiss cheese.

Three strategies dominate in practice — the buddy system, the slab allocator, and tcmalloc — and each makes a radically different bet about what programs usually need. Understanding them means understanding a trade-off that shapes every server, game engine, and database running today.

Pick an allocator, then Allocate and Free blocks to see how each strategy manages the heap. The bar shows used space (blue) and wasted space (red fragmentation).

<!-- {{c_html_intro}} -->
<div class="controls">
  <div class="row">
    <label for="strategy">{{lbl_strategy}}</label>
    <select id="strategy">
      <option value="buddy">{{opt_buddy}}</option>
      <option value="slab">{{opt_slab}}</option>
      <option value="tcmalloc">{{opt_tcmalloc}}</option>
    </select>
    <label for="reqsize">{{lbl_size}}</label>
    <input id="reqsize" type="number" min="1" max="256" value="48" style="width:60px">
    <span>bytes</span>
  </div>
  <div class="row">
    <button id="btn-alloc" type="button">{{btn_alloc}}</button>
    <button id="btn-free" type="button">{{btn_free}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div class="heap-wrap">
  <div id="heap" class="heap" title="{{heap_title}}"></div>
</div>
<div class="stats-row">
  <span id="stat-used" class="stat used-dot">{{lbl_used}} <b id="v-used">0</b></span>
  <span id="stat-waste" class="stat waste-dot">{{lbl_waste}} <b id="v-waste">0</b></span>
  <span id="stat-free" class="stat free-dot">{{lbl_free}} <b id="v-free">512</b></span>
</div>
<div id="status" class="status"></div>
<div class="legend">
  <span class="leg used-dot">{{leg_used}}</span>
  <span class="leg waste-dot">{{leg_waste}}</span>
  <span class="leg free-dot">{{leg_free}}</span>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.controls { display: flex; flex-direction: column; gap: .4rem; margin-bottom: .6rem; }
.row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; }
label { font-weight: 600; }
select, input[type=number] { padding: .3rem .4rem; border: 1px solid #aaa; border-radius: 6px; font-size: 14px; }
button { font: 600 13px system-ui, sans-serif; padding: .38rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
/* {{c_heap_style}} */
.heap-wrap { background: #f0f2f5; border-radius: 8px; padding: 6px; margin: .4rem 0; }
.heap { display: flex; flex-wrap: wrap; gap: 2px; }
.cell { width: 12px; height: 20px; border-radius: 2px; }
.cell.free  { background: #d0d6de; }
.cell.used  { background: #3a86ff; }
.cell.waste { background: #e63946; }
/* {{c_stats_style}} */
.stats-row { display: flex; gap: 1rem; margin: .4rem 0; flex-wrap: wrap; }
.stat { font-size: .88rem; }
.used-dot::before  { content: ""; display: inline-block; width: 10px; height: 10px; border-radius: 2px; background: #3a86ff; margin-right: 4px; vertical-align: middle; }
.waste-dot::before { content: ""; display: inline-block; width: 10px; height: 10px; border-radius: 2px; background: #e63946; margin-right: 4px; vertical-align: middle; }
.free-dot::before  { content: ""; display: inline-block; width: 10px; height: 10px; border-radius: 2px; background: #d0d6de; margin-right: 4px; vertical-align: middle; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.3em; margin: .3rem 0; }
.status.ok  { color: #0a7d33; }
.status.err { color: #c92f3c; }
.legend { display: flex; gap: 1rem; font-size: .82rem; color: #555; flex-wrap: wrap; }
.leg { display: flex; align-items: center; }

// Code not found

Notice the difference. Buddy rounds every request up to the next power of two — simple and fast to merge, but a 65-byte request wastes 63 bytes. Slab pre-carves fixed pools for common sizes — near-zero waste for objects that fit, but a fresh slab for every new size class. tcmalloc uses per-thread caches of size classes — low contention, low fragmentation, high complexity.

Each strategy handles the same heap but optimizes a different goal:

Buddy system (Knuth, 1966): memory is always split into blocks whose sizes are powers of two — $2^{0}, 2^{1}, \dots, 2^{k}$ bytes. To allocate $n$ bytes the system picks the smallest power of two $\geq n$. To free a block it checks whether its "buddy" (the partner block it was split from) is also free; if so, they merge back. Merging is $O(1)$ per level and coalescing is automatic, but internal fragmentation can be up to $50\%$: a 65-byte request occupies a 128-byte block.

Slab allocator (Bonwick, 1994): instead of splitting a monolithic heap, the kernel pre-allocates slabs — contiguous pages carved into equal-size slots for a single object type. Allocating an object of a known type takes a pointer from a free list: $O(1)$, zero fragmentation within the slab. The cost is slab waste: if only one object in a slab survives, the whole slab stays pinned until the last object is freed.

tcmalloc (Google, 2005): each thread owns a thread-local cache of small-object free lists, organized into ~$60$ size classes (rounded to the nearest multiple of 8, 16, 64 bytes, etc.). Allocations under 256 KB almost never touch a global lock. Large objects go to a central page heap. The design minimizes lock contention at the cost of holding memory in per-thread caches even when other threads are starving.

The theoretical bound all three fight is that optimal offline bin packing — deciding the perfect placement knowing all future requests — is NP-hard. Real allocators run online, with no lookahead. Each strategy is essentially a heuristic: buddy bets on power-of-two sizes being common, slab bets on object types being repeated, tcmalloc bets on thread locality being exploitable.

Memory allocation is not an academic concern — it shows up wherever software runs at high throughput:

• OS kernels: Linux's SLUB allocator (a modern slab variant) manages every kernel object from inodes to network buffers. Fragmentation here corrupts system performance globally.
• Databases: PostgreSQL uses its own arena allocator; Redis's jemalloc (a tcmalloc cousin) lets it publish live fragmentation ratios in INFO memory. A mismatched allocator can double memory usage under workloads with many small keys.
• Game engines: frame allocators reset a whole arena every 16 ms — zero fragmentation, near-zero overhead, at the cost of no random frees. Unity and Unreal both ship custom arenas for hot paths.
• Browsers: Chrome switched to PartitionAlloc, a type-segregated allocator, partly as a security hardening measure: keeping objects of different types in separate partitions limits use-after-free exploits — the same insight as slab but weaponized against attackers.
• Garbage-collected languages: the JVM's generational GC uses bump-pointer allocation in young space — the fastest possible allocator — and only invokes complex strategies in older generations. See how dynamic programming ideas appear even in GC design.

Choosing the wrong allocator for a workload does not crash programs — it just makes them silently slower and larger, often by a factor most teams never measure.

The buddy system, the slab allocator, and tcmalloc all solve the same problem — carve a heap into live chunks and reclaim the dead ones — but each exploits a different assumption about the world. Buddy assumes power-of-two requests are common. Slab assumes object types repeat. tcmalloc assumes threads mostly allocate their own objects.

When the assumption holds, the strategy shines. When it breaks — a buddy allocator serving arbitrarily sized network packets, a slab allocator where every object is a unique type — the fragmentation penalty appears silently in your memory graphs. No allocator is universally optimal, because optimal offline allocation is NP-hard and programs reveal their intentions one request at a time.

Understanding the trade-off does not mean rewriting your allocator. It means knowing when to reach for jemalloc instead of the system default, when an arena is the right answer, and why the memory usage number in your monitoring dashboard is not quite what it seems.