Introduction

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.

Try It

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).

<!-- Memory allocator fragmentation demo — buddy / slab / tcmalloc -->
<div class="controls">
  <div class="row">
    <label for="strategy">Strategy:</label>
    <select id="strategy">
      <option value="buddy">Buddy system</option>
      <option value="slab">Slab allocator</option>
      <option value="tcmalloc">tcmalloc</option>
    </select>
    <label for="reqsize">Request 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">Allocate</button>
    <button id="btn-free" type="button">Free last</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
</div>
<div class="heap-wrap">
  <div id="heap" class="heap" title="Heap visualization — blue=used, red=waste, gray=free"></div>
</div>
<div class="stats-row">
  <span id="stat-used" class="stat used-dot">Used: <b id="v-used">0</b></span>
  <span id="stat-waste" class="stat waste-dot">Waste: <b id="v-waste">0</b></span>
  <span id="stat-free" class="stat free-dot">Free: <b id="v-free">512</b></span>
</div>
<div id="status" class="status"></div>
<div class="legend">
  <span class="leg used-dot">Used bytes</span>
  <span class="leg waste-dot">Internal waste (fragmentation)</span>
  <span class="leg free-dot">Free bytes</span>
</div>

/* Heap visualization styles */
* { 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; }
/* Heap cell colors */
.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; }
/* Stats row and legend dots */
.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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Allocator simulation — buddy, slab, tcmalloc strategies over a 512-byte virtual heap

const HEAP_BYTES = 512; // total virtual heap size in bytes

// heap array: each index is one byte
// 0 = free, positive integer = allocation ID (used bytes), -1 = internal waste
let heap = new Array(HEAP_BYTES).fill(0);
let nextId = 1;
let allocations = []; // track live allocations for free-last { id, start, used, size }

// Buddy allocator: rounds up to next power of two, finds aligned free block
function buddyAlloc(n) {
  let sz = 1;
  while (sz < n) sz *= 2; // round up to next power of 2
  // find aligned free region
  for (let start = 0; start <= HEAP_BYTES - sz; start++) {
    if (start % sz !== 0) continue; // must start at power-of-2 boundary
    let free = true;
    for (let i = start; i < start + sz; i++) if (heap[i] !== 0) { free = false; break; }
    if (!free) continue;
    const id = nextId++;
    for (let i = start; i < start + n; i++) heap[i] = id;
    for (let i = start + n; i < start + sz; i++) heap[i] = -1; // mark internal waste (padding to power-of-2)
    allocations.push({ id, start, used: n, size: sz });
    return { id, waste: sz - n };
  }
  return null;
}

// Slab allocator: fixed size classes [8,16,32,64,128,256]
// Size classes: 8, 16, 32, 64, 128, 256
const SLAB_CLASSES = [8, 16, 32, 64, 128, 256];
function slabClass(n) { return SLAB_CLASSES.find(c => c >= n) || 256; }
function slabAlloc(n) {
  const sc = slabClass(n);
  // find aligned free slot in slab
  for (let start = 0; start <= HEAP_BYTES - sc; start++) {
    if (start % sc !== 0) continue;
    let free = true;
    for (let i = start; i < start + sc; i++) if (heap[i] !== 0) { free = false; break; }
    if (!free) continue;
    const id = nextId++;
    for (let i = start; i < start + n; i++) heap[i] = id;
    for (let i = start + n; i < start + sc; i++) heap[i] = -1; // mark internal waste (padding to slab class)
    allocations.push({ id, start, used: n, size: sc });
    return { id, waste: sc - n };
  }
  return null;
}

// tcmalloc: finer size classes, 8-byte aligned
// tcmalloc: size classes rounded to nearest 8 below 64, nearest 16 below 256
function tcClass(n) {
  if (n <= 64)  return Math.ceil(n / 8) * 8;
  if (n <= 256) return Math.ceil(n / 16) * 16;
  return Math.ceil(n / 64) * 64;
}
function tcAlloc(n) {
  const sc = tcClass(n);
  // find 8-byte-aligned free region
  for (let start = 0; start <= HEAP_BYTES - sc; start++) {
    if (start % 8 !== 0) continue; // 8-byte alignment
    let free = true;
    for (let i = start; i < start + sc; i++) if (heap[i] !== 0) { free = false; break; }
    if (!free) continue;
    const id = nextId++;
    for (let i = start; i < start + n; i++) heap[i] = id;
    for (let i = start + n; i < start + sc; i++) heap[i] = -1; // mark internal waste (padding to size class)
    allocations.push({ id, start, used: n, size: sc });
    return { id, waste: sc - n };
  }
  return null;
}

function doAlloc() {
  const n = parseInt(document.getElementById('reqsize').value, 10);
  if (!n || n < 1 || n > 256) { setStatus('Please enter a size between 1 and 256 bytes.', 'err'); return; }
  const strat = document.getElementById('strategy').value;
  let res;
  if (strat === 'buddy')    res = buddyAlloc(n);
  else if (strat === 'slab') res = slabAlloc(n);
  else                       res = tcAlloc(n);
  if (!res) { setStatus('Not enough contiguous free space — try freeing some blocks.', 'err'); return; }
  // allocation succeeded — compute fragmentation percentage
  const pct = Math.round((res.waste / HEAP_BYTES) * 100);
  setStatus(i18nFmt('Allocated %n% bytes. Internal waste: %waste% bytes (%pct% of heap).', { n, waste: res.waste, pct }), 'ok');
  render();
}

function doFree() {
  // free the most recent allocation (LIFO for simplicity)
  if (allocations.length === 0) { setStatus('Nothing allocated yet.', 'err'); return; }
  const a = allocations.pop();
  for (let i = a.start; i < a.start + a.size; i++) heap[i] = 0;
  setStatus(i18nFmt('Freed %n% bytes — space reclaimed.', { n: a.used }), 'ok');
  render();
}

function doReset() {
  heap = new Array(HEAP_BYTES).fill(0);
  allocations = [];
  nextId = 1;
  setStatus('Heap reset.', '');
  render();
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

function render() {
  const heapEl = document.getElementById('heap');
  heapEl.innerHTML = '';
  let usedBytes = 0, wasteBytes = 0, freeBytes = 0;
  for (let i = 0; i < HEAP_BYTES; i++) {
    const d = document.createElement('div');
    if (heap[i] === 0)  { d.className = 'cell free';  freeBytes++; }
    else if (heap[i] === -1) { d.className = 'cell waste'; wasteBytes++; }
    else { d.className = 'cell used'; usedBytes++; }
    heapEl.appendChild(d);
  }
  document.getElementById('v-used').textContent  = usedBytes;
  document.getElementById('v-waste').textContent = wasteBytes;
  document.getElementById('v-free').textContent  = freeBytes;
}

document.getElementById('btn-alloc').addEventListener('click', doAlloc);
document.getElementById('btn-free').addEventListener('click', doFree);
document.getElementById('btn-reset').addEventListener('click', doReset);
render();
Result
Console

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.

The Real Trade-offs

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 — 20,21,…,2k2^{0}, 2^{1}, \dots, 2^{k} bytes. To allocate nn bytes the system picks the smallest power of two ≥n\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)O(1) per level and coalescing is automatic, but internal fragmentation can be up to 50%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)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 ~6060 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/memory-allocators/Content licensed under CC BY-NC 4.0.