Part 8 · 1 chapters · ~8 min

Memory Allocators

How malloc gets memory (brk and mmap), free lists and size classes, fragmentation, thread caches (jemalloc, tcmalloc, mimalloc), arenas and bump allocation measured, pool allocators, allocator choice in Redis and databases, and writing a small allocator.

From brk to arenas

code

// a bump allocator: the fastest allocator there is
static char arena[64 << 20]; static size_t off;
void *bump(size_t n) { n = (n + 15) & ~(size_t)15; if (off + n > sizeof arena) return NULL; void *p = arena + off; off += n; return p; }
void reset(void) { off = 0; }                         // free everything at once, end of request

// a free-list allocator for one size (pool)
typedef struct Node { struct Node *next; } Node;
static Node *free_list;
void *pool_alloc(void) { if (!free_list) refill(); Node *n = free_list; free_list = n->next; return n; }
void pool_free(void *p) { Node *n = p; n->next = free_list; free_list = n; }

// measured: malloc+free 64 B 23.0 ns, bump 5.4 ns (M3 Pro, 1M iterations)

allocator	known for	used by
glibc ptmalloc	default on Linux; arenas per thread, can fragment	most Linux programs
jemalloc	low fragmentation, introspection	Redis (default on Linux), FreeBSD, many databases
tcmalloc	per-CPU caches, very fast small allocations	Google services
mimalloc	compact, fast, free-list sharding	Microsoft, some runtimes

Large allocations (typically 128 KB and above in glibc) come straight from mmap and go back to the OS on free; small ones come from heap regions grown with brk or mmap and are reused.

ALLOCATORS, MEASURED

Apple M3 Pro, clang 17 -O2, 1,000,000 allocations of 64 bytes

swipe the figure sideways, or tap expand for full screen

1/3

general purpose

malloc must handle any size, any order of frees and many threads: size classes, free lists, per-thread caches. 23 ns per malloc and free pair here.

general: 23 nssize classes and caches