Memory Allocation
Before garbage collection ever runs, something has to hand out the memory. Six allocators — four ways to pick a hole, plus the two structured schemes real kernels actually ship.
What is Memory Allocation?
The 60-second primer
Memory allocation is the act of handing out a chunk of free memory in response to a request — `malloc`, `new`, a stack frame, a kernel object — and reclaiming it later. Garbage collection decides what is still alive; allocation decides where the next live thing goes. Every program leans on an allocator on essentially every line, so the policy it uses quietly shapes throughput, latency, and how much memory you actually waste.
The core difficulty is fragmentation. Free memory is rarely one clean block — it's a patchwork of holes left behind as objects of different sizes come and go. An allocator's job is to choose which hole to carve a request from, and that single choice, repeated millions of times, determines whether your holes stay large and reusable or crumble into dust too small to use.
These six allocators split into two families. The first four — First, Best, Worst, and Next Fit — are sequential-fit strategies: they keep a list of holes and differ only in which one they pick. The last two are structured schemes that real systems ship: the buddy system (Linux's page allocator, splitting and merging powers of two) and slab allocation (the kernel's object caches, with O(1) allocation and zero external fragmentation).
Why the policy matters
- External fragmentation — free memory exists in total, but no single hole is big enough for the next request. A request fails even though there's plenty of room. This is the disease the fit strategies fight (and sometimes worsen).
- Internal fragmentation — you hand out more than was asked for (rounded up to a block size), and the slack inside the block is wasted. The buddy system trades this on purpose for speed.
- Allocation speed — how long it takes to find a hole. First/Next Fit stop early; Best/Worst Fit scan everything; buddy and slab are effectively O(1). On a hot path, this is the difference between a fast and a slow program.
- Coalescing cost — when memory is freed, can adjacent holes merge back into a big one? The buddy system makes this a single XOR and a list operation; naive free lists make it a search.
- Predictability — a kernel or real-time system cannot afford an allocator whose latency spikes or whose memory slowly rots into unusable slivers. That constraint is exactly why slab and buddy exist.
Where these live in real systems
Linux's page allocator is a buddy system; its slab/SLUB allocator sits on top to dish out kernel objects (inodes, task_structs, file handles). glibc `malloc` (ptmalloc) uses segregated free lists with best-fit-like binning. FreeBSD popularized the slab allocator (Bonwick's design from Solaris). The sequential fits are the textbook foundation every one of these is a refinement of — and First Fit, in particular, is still remarkably hard to beat in practice.
Side-by-side
How they compare
The same concepts, on the same axes. Use this as a map; the individual pages are the territory.
| Allocator | How it picks | Speed | Fragmentation | Best for |
|---|---|---|---|---|
01First Fit | First hole that fits, from the start | Fast (early stop) | External; clusters at front | Sensible general default |
02Best Fit | Smallest hole that fits | Slow (scans all) | External; tiny slivers | Minimizing leftover (in theory) |
03Worst Fit | Largest hole that fits | Slow (scans all) | External; eats big holes | Rarely — mostly a teaching foil |
04Next Fit | First fit, resuming where it stopped | Fast; spreads load | External; spread out | Cheap, even use of memory |
05Buddy System | Round to power of 2, split/merge | O(log n), fast coalescing | Internal (rounding waste) | Page allocation, fast free |
06Slab | Fixed slot in a per-type cache | O(1) | Almost none (per type) | Many same-sized objects |
- How it picks
- First hole that fits, from the start
- Speed
- Fast (early stop)
- Fragmentation
External; clusters at front- Best for
- Sensible general default
- How it picks
- Smallest hole that fits
- Speed
- Slow (scans all)
- Fragmentation
External; tiny slivers- Best for
- Minimizing leftover (in theory)
- How it picks
- Largest hole that fits
- Speed
- Slow (scans all)
- Fragmentation
External; eats big holes- Best for
- Rarely — mostly a teaching foil
- How it picks
- First fit, resuming where it stopped
- Speed
- Fast; spreads load
- Fragmentation
External; spread out- Best for
- Cheap, even use of memory
- How it picks
- Round to power of 2, split/merge
- Speed
- O(log n), fast coalescing
- Fragmentation
Internal (rounding waste)- Best for
- Page allocation, fast free
- How it picks
- Fixed slot in a per-type cache
- Speed
- O(1)
- Fragmentation
Almost none (per type)- Best for
- Many same-sized objects
Decision guide
Which one should you use?
A practical tour of when each algorithm wins.
How to think about picking one
- You want a simple, fast, good-enough general allocator → First Fit (or Next Fit if you want to spread allocations out). Decades of study show First Fit is hard to beat for general workloads.
- You're tempted by Best Fit to 'minimize waste' → measure first. Best Fit minimizes the leftover of each allocation but tends to litter the heap with slivers too small to ever reuse, and it pays a full scan every time.
- You're handing out whole pages and need fast merging → the buddy system. Power-of-two blocks make finding a buddy and coalescing nearly free, at the cost of rounding every request up.
- You allocate huge numbers of identically-sized objects (kernel structs, network buffers, nodes) → a slab allocator. One cache per type means O(1) allocation, no external fragmentation, and warm, pre-initialized objects.
- Real systems layer these — Linux uses buddy for pages and slab on top for objects. The fit strategies are the conceptual baseline you reach for inside a custom allocator or arena.
Two kinds of waste, one trade-off
Keep the two fragmentations straight: external is wasted space between allocations (the fit strategies' problem), internal is wasted space inside an allocation you over-rounded (the buddy system's deliberate cost). Slab allocation is special because, within a single object type, it has essentially neither — every slot is exactly the right size and packed tight. The price is structure: you must know your object sizes up front.
Concepts in this track
6 concepts, in order
Each links to a concept page with its own explanation, prototype, and quiz.
First Fit
Scan from the start, grab the first hole big enough. The fast, simple default — and where fragmentation begins.
Best Fit
Check every hole, take the smallest one that fits. Minimizes leftover — and breeds tiny, useless slivers.
Worst Fit
Always carve from the largest hole. The intuition is to leave reusable leftovers — it usually backfires.
Next Fit
First Fit with a memory: resume scanning where you stopped last time, wrapping around the end.
Buddy System
Round up to a power of two, split blocks in half to fit, and merge buddies back on free. Fast coalescing, at the cost of internal waste.
Slab Allocation
Pre-size caches of fixed slots per object type. O(1) allocation, zero external fragmentation — the kernel's workhorse.
Related tracks
If this one clicks, try these next.
Garbage Collection
How a runtime reclaims memory you stopped using — without you ever calling free(). Eight algorithms, from the counter on every object to the collectors that run alongside your program.
Cache Write Policies
Three ways to handle a write when you have a cache in front of the store. Each policy is a different bet about durability, throughput, and how stale your data is allowed to get.
Cache Eviction
When the cache fills up, something has to go — and which one you pick decides your hit rate. Ten classic policies, side-by-side.