Arena, Bump, and Pool Allocators

Why a special-purpose allocator can win

In guide 1 you built a general free list: it answers any malloc(n) for any n, in any order, with free() allowed at any moment. That generality is exactly what makes it slow — every call must search a list, maybe split a block, and on free() maybe coalesce neighbours. But most programs do not actually need all that freedom. A web request allocates a hundred little structures and then throws them all away at once. A game loop builds a pile of temporary objects each frame and resets every frame. A parser allocates thousands of nodes that all share one lifetime. When the usage pattern is that regular, a general allocator is wasted generality — and you can build a tiny custom one that is dramatically faster.

The trick in all three allocators here is the same: trade away some freedom to buy speed. A bump allocator gives up the ability to free individual blocks — you can only reset the whole thing at once. A pool allocator gives up the ability to allocate arbitrary sizes — every block is the same fixed size. In exchange, allocation stops being a search and becomes a couple of pointer operations. Crucially, none of these replaces malloc(); each sits on top of a big chunk you got from the general allocator (or straight from the kernel with mmap()) and hands out slices of it. They are scalpels, not a new heart.

The bump allocator: allocation as a single addition

Start with the simplest allocator that exists. Take one contiguous region of memory and keep a single pointer, call it next, sitting at the first free byte. To allocate n bytes you do exactly one thing: read next, round it up for alignment, remember that address as the result, advance next by n, and return the remembered address. That is the entire algorithm. No list, no header, no search — allocation is one addition and a bounds check. This is the bump (or linear) allocator, named because each request just bumps the pointer forward.

  start                      next (free pointer)            end
    |                           |                             |
    v                           v                             v
    [ obj A | obj B | obj C | . . . . . . . . . . . . . . . . . ]
     <----- already handed out ----->  <------ still free ----->

  allocate(n):
     p     = align_up(next, alignment)
     if p + n > end:  return NULL        // region is full
     next  = p + n                       // the whole "bump"
     return p

  reset():  next = start                 // frees EVERYTHING at once

Look at what is missing, because that is the whole point. There is no per-block free(): you cannot hand back object B while keeping A and C, because the only state is one pointer and it has no idea where B began or whether the gap could be reused. The only way to reclaim memory is reset(): set next back to start and the entire region is free again in one instruction. So a bump allocator is perfect when many objects share one lifetime — allocate freely all request long, then reset() once at the end. It is useless when objects die at independent, unpredictable times.

The arena: a region that frees in one stroke

An arena (also called a region allocator) is the bump allocator grown up into a practical tool. The core is still a bump pointer, but with two additions. First, when the current region fills up, instead of returning NULL the arena grabs another big chunk from malloc() or mmap() and chains it onto a list of blocks, so it can grow without bound. Second, freeing is redefined to mean freeing the whole arena: walk the chain of underlying chunks and release each one. You never free a single object — you destroy the entire arena and everything in it dies together.

This matches an astonishing number of real programs. Think of handling one HTTP request: you create a request arena, allocate every header, parsed field, and temporary buffer out of it during the request, and then free the arena in a single call when the response is sent. You do not — and must not — track the individual objects. This is why the idea is sometimes called a memory pool or arena: lifetimes are grouped by phase of work, not by individual object. The payoff is huge: zero risk of leaking any one of those objects (they all die together), and free() of the whole batch is one walk of a short chunk list rather than thousands of separate free() calls each touching headers and free lists.

Be exact about the cost, though, because the arena's strength is also its trap. Memory inside an arena is never reclaimed until the whole arena dies. If one long-lived object hides in an arena you keep alive, it pins the entire arena — every byte ever bumped stays resident. So arenas leak in a particular way: not by losing pointers, but by keeping the wrong things grouped together. The rule of thumb is to size the grouping to the work: one arena per request, per frame, per parse — something with a clean, short, well-defined end. Mix a long lifetime into a short-lived arena and you have built a slow, silent memory hog.

The pool: a free list of identical blocks

The bump and arena allocators bought speed by giving up individual free(). The pool allocator (also called an object allocator) keeps individual free() but pays for it differently: every block in a pool is exactly the same fixed size. Suppose your program constantly allocates and frees objects of one type — say a 48-byte node in a linked list, millions of times. A pool carves one big region into a grid of equal 48-byte slots and threads all the free slots onto a free list, just like guide 1 — but because every slot is identical, that free list needs no size field, no search, and no splitting.

Now allocation and freeing are both O(1) with no search at all. To allocate: pop the first slot off the free list (read its embedded next-pointer, that becomes the new head) and return it. To free: push the slot back onto the front of the free list (write the old head into the slot, point the head at the slot). Two pointer writes each way. Like guide 1's trick, the next-pointer lives inside each free slot, so the free list costs no extra memory. And because there is exactly one block size, there is no external fragmentation at all — every freed slot is interchangeable with every request, so a hole can always be reused.

  region carved into fixed 48-byte slots (S0..S5):
    [ S0 ][ S1 ][ S2 ][ S3 ][ S4 ][ S5 ]

  free list links the FREE slots through their own bodies:
    head -> S1 -> S4 -> S5 -> NULL        (S0,S2,S3 are in use)

  allocate():  p = head;  head = *(void**)head;  return p;   // pop
  free(p):     *(void**)p = head;  head = p;                  // push

  no size field, no search, no splitting, no coalescing.

The honest cost is the flip side of the win: a pool only holds one size, so you typically run many pools, one per common object size. Store a 24-byte object in a 48-byte-slot pool and you waste 24 bytes to internal fragmentation; store a 60-byte object and it does not fit at all. And the moment two threads share a pool, that free list head becomes a contended pointer that needs a lock or an atomic compare-and-swap. These are precisely the problems the next guides solve: the slab allocator in guide 3 generalises the pool to manage many object caches and recycle initialised objects, while guide 4's size classes are the principled way to choose how many pools you keep and how big each one's blocks are.

Choosing among them

These three are not competitors so much as different shapes cut to fit different lifetime patterns. The single question that picks one is: *when and how do my objects die?* Match the allocator to the answer and you get most of the speed of a hand-rolled system with very little code.

1. Do many objects share one lifetime and die together at a clean phase boundary (per request, per frame, per parse)? Use an arena: bump to allocate, free the whole region in one stroke, never track individuals.
2. Do you allocate scratch, use it, and want it gone in strict reverse order? Use a stack allocator: save a mark before the work, restore the mark after, and the whole batch pops at once.
3. Do you churn through countless objects of one fixed size that die at independent times? Use a pool: O(1) pop to allocate, O(1) push to free, zero external fragmentation for that size.
4. Are sizes truly arbitrary and lifetimes truly unpredictable, with no pattern to exploit? Stay with the general free list from guide 1 — that is exactly the case it was built for, and a special-purpose allocator would only get in the way.

Notice the throughline that links this guide back to guide 1 and forward into the rest of the rung. Guide 1's general allocator was slow because it made no assumptions; every allocator here is fast because it makes one strong assumption and enforces it. The bump allocator assumes a shared lifetime; the pool assumes a shared size. Production allocators like jemalloc and tcmalloc do not pick one — they layer them, running per-size pools and per-thread arenas underneath a general fallback, so the common case hits the fast path and only the unusual case pays for full generality. You have just met the two building blocks they are made of; guides 3 to 5 show how the masters assemble them.