Part ofSystems Programming Companion, week 11
Custom Allocators
malloc is a generalist. Any size, any lifetime, any pattern — it'll cope. Generality has a price, though: bookkeeping overhead, fragmentation, and timing you can't reliably predict. In systems work, you usually know more about your allocation patterns than malloc does. Lean on that knowledge and you can build allocators that are both faster and more predictable.
Why Custom Allocators?
Consider these scenarios:
- Game frame allocator: Every frame, a game allocates hundreds of temporary objects. At the end of the frame, they all get freed. Why pay the cost of individual
freecalls when you can reset a pointer? - Network buffer pool: A server allocates fixed-size buffers for each connection. A pool of pre-allocated buffers eliminates allocation latency.
- Compiler AST nodes: A compiler creates millions of AST nodes during parsing and frees them all at once when compilation finishes. An arena is ideal.
Arena Allocator
An arena (a.k.a. bump allocator or linear allocator) is the simplest custom allocator there is. One buffer, one pointer that marches forward with each allocation. Freeing individual allocations isn't a thing — you reset the whole arena at once or not at all.
#include <stdlib.h>#include <stdint.h>#include <string.h>#include <stdio.h>
typedef struct { uint8_t *buffer; size_t capacity; size_t offset;} Arena;
Arena arena_create(size_t capacity) { Arena a; a.buffer = malloc(capacity); a.capacity = a.buffer ? capacity : 0; // a failed malloc gives an empty arena a.offset = 0; return a;}
void *arena_alloc(Arena *a, size_t size) { // Align to 8 bytes size_t aligned_offset = (a->offset + 7) & ~7; if (aligned_offset + size > a->capacity) { return NULL; // out of space } void *ptr = a->buffer + aligned_offset; a->offset = aligned_offset + size; return ptr;}
void arena_reset(Arena *a) { a->offset = 0;}
void arena_destroy(Arena *a) { free(a->buffer); a->buffer = NULL; a->capacity = 0; a->offset = 0;}Alignment matters for both speed and correctness. Most CPUs want data sitting on its natural boundary — 4 bytes for an int, 8 bytes for a double or pointer. The (offset + 7) & ~7 trick is a tidy bit-twiddle that rounds up to the next 8-byte boundary.
Using the Arena
int main() { Arena a = arena_create(4096);
int *x = arena_alloc(&a, sizeof(int)); int *y = arena_alloc(&a, sizeof(int)); double *z = arena_alloc(&a, sizeof(double));
*x = 10; *y = 20; *z = 3.14;
printf("%d %d %.2f\n", *x, *y, *z); // 10 20 3.14
arena_reset(&a); // All allocations are now invalid - the arena is empty
arena_destroy(&a); return 0;}The arena flies. Each allocation is a pointer bump and a bounds check, full stop. No per-allocation bookkeeping. No fragmentation.
Exercise: Aligned Allocations and Checkpoints
arena_alloc only promises 8-byte alignment. SSE loads want 16, AVX wants 32, and anything you're padding out to a cache line wants 64. The other gap is the all-or-nothing reset: often you'd like to throw away just the scratch work from one function call and keep everything allocated before it.
The starter has two stubs. Fill in arena_alloc_aligned so the returned address is a multiple of align, and arena_rollback so it rewinds the arena to a checkpoint. When every line says ok, you're done.
One possible solution
void *arena_alloc_aligned(Arena *a, size_t size, size_t align) { uintptr_t base = (uintptr_t)a->buffer; uintptr_t p = (base + a->offset + align - 1) & ~(uintptr_t)(align - 1); size_t offset = p - base; if (offset + size > a->capacity) return NULL; a->offset = offset + size; return (void *)p;}
void arena_rollback(Arena *a, ArenaMark mark) { a->offset = mark;}Rounding a->offset on its own isn't enough. Offset 64 is only 64-byte aligned if the buffer itself starts on a 64-byte boundary, and malloc only promises 16. A checkpoint is nothing more than a saved offset, which is why rollback costs a single store. Anything allocated after the mark is gone, so don't hang on to pointers into it.
Pool Allocator
A pool allocator hands out fixed-size blocks. Everything's the same size, which kills fragmentation and gets you O(1) allocation:
typedef struct pool_block { struct pool_block *next;} pool_block;
typedef struct { uint8_t *buffer; pool_block *free_list; size_t block_size; size_t count;} Pool;
Pool pool_create(size_t block_size, size_t count) { // Ensure block_size is at least sizeof(pool_block) if (block_size < sizeof(pool_block)) block_size = sizeof(pool_block);
Pool p; p.block_size = block_size; p.count = count; p.buffer = malloc(block_size * count); p.free_list = NULL;
// Thread all blocks into the free list for (size_t i = 0; i < count; i++) { pool_block *b = (pool_block *)(p.buffer + i * block_size); b->next = p.free_list; p.free_list = b; } return p;}
void *pool_alloc(Pool *p) { if (p->free_list == NULL) return NULL; pool_block *b = p->free_list; p->free_list = b->next; return b;}
void pool_free(Pool *p, void *ptr) { pool_block *b = (pool_block *)ptr; b->next = p->free_list; p->free_list = b;}
void pool_destroy(Pool *p) { free(p->buffer);}The neat trick: store the free-list pointers inside the free blocks themselves. The blocks aren't in use, so the first few bytes are free real estate for our next pointer.
Free List Allocator
A free list allocator (sometimes called first-fit or just general-purpose) lives closer to what malloc itself does. It threads free blocks together in a linked list and walks them looking for one that's big enough:
typedef struct block_header { size_t size; int is_free; struct block_header *next;} block_header;
// Round the 24-byte header up to 32 so user pointers stay 16-byte aligned#define HEADER_SIZE ((sizeof(block_header) + 15) & ~(size_t)15)
static _Alignas(16) uint8_t heap[65536];static block_header *free_list = NULL;
void heap_init() { free_list = (block_header *)heap; free_list->size = sizeof(heap) - HEADER_SIZE; free_list->is_free = 1; free_list->next = NULL;}
void *heap_alloc(size_t size) { size = (size + 15) & ~(size_t)15; // keep every block a multiple of 16 block_header *current = free_list; while (current) { if (current->is_free && current->size >= size) { // Split if there is enough room for another block if (current->size >= size + HEADER_SIZE + 16) { block_header *new_block = (block_header *) ((uint8_t *)current + HEADER_SIZE + size); new_block->size = current->size - size - HEADER_SIZE; new_block->is_free = 1; new_block->next = current->next; current->size = size; current->next = new_block; } current->is_free = 0; return (uint8_t *)current + HEADER_SIZE; } current = current->next; } return NULL;}The alignment work matters. malloc promises memory aligned for any standard type (_Alignof(max_align_t), which is 16 on x86-64 Linux), and callers rely on that for long double and SSE values. A bare uint8_t array only promises 1-byte alignment, so _Alignas(16) on heap, a header padded to 32 bytes and sizes rounded to 16 together keep every returned pointer on a 16-byte boundary.
When to Use Each
| Allocator | Best For | Alloc Speed | Free Speed | Fragmentation |
|---|---|---|---|---|
| Arena | Batch alloc, batch free | O(1) | N/A (reset all) | None |
| Pool | Fixed-size objects | O(1) | O(1) | None |
| Free list | Variable sizes, variable lifetimes | O(n) | O(1) or O(n) | Possible |
| malloc | General purpose | Amortized O(1) | O(1) | Managed |
Big-O hides the constant factors, and for small objects the constants are the whole story. The program below makes two million 32-byte allocations each way: malloc with a free per block, then the arena with one reset per batch of 100,000. The runner compiles at -O0 on a shared machine, so the numbers will wobble from run to run (and differ from your laptop). Watch the ratio rather than the milliseconds.
Real-World Usage
Custom allocators ship in plenty of real software:
- SQLite gives each database connection a "lookaside" pool of fixed-size slots for the many small, short-lived allocations made while preparing statements (parse tree nodes, names and the like)
- Linux kernel uses slab allocators (a sophisticated pool) for kernel objects
- Game engines use frame arenas, pool allocators for entities, and specialised allocators for GPU resources
- jemalloc/tcmalloc (replacements for malloc) use thread-local caches and size-class pools internally
Knowing these patterns helps you tune your own hot paths and decode the allocation strategies of the systems sitting under your code.
Challenges
Implement a simple arena allocator that pre-allocates a buffer and hands out sequential chunks. Allocate three integers (10, 20, 30), print them, then reset the arena. Print 'Arena reset' after resetting.