Why a single free list dies under threads
Everything in this rung so far has quietly assumed one thread. The textbook allocator from guide 1 — one free list, walked under a placement policy, with splitting and coalescing — works beautifully right up to the moment a second thread calls malloc() at the same time. Two threads both editing the same linked list will corrupt it: one unlinks a block while the other reads the very pointer it just changed. So the obvious fix is to wrap every malloc() and free() in a single global lock with pthread_mutex_lock(). Correct, and fatal to performance.
Picture an eight-core server where every thread allocates in its hot loop. With one lock, the cores spend their lives queued behind that mutex, and adding cores makes things worse, not better — this is allocator contention, and it shows up as a program that refuses to scale no matter how much hardware you throw at it. The lock is not even the whole cost. Two threads bouncing the same lock and the same free-list head between their private caches drag a cache line back and forth across the chip; that ping-pong, called false sharing, can cost more than the lock itself. The lesson production allocators absorbed is blunt: the fast path of malloc() must touch no shared state at all.
The shared blueprint: thread caches over size classes
Here is the surprise: jemalloc, tcmalloc, and mimalloc differ in a hundred details, but their skeletons are nearly identical, and you already know every bone. Start from the size classes of guide 4 — instead of arbitrary sizes, every request is rounded up to one of a fixed menu (8, 16, 32, 48, 64, ... bytes). Each size class owns its own pool of identical slots, exactly like a slab. Allocating from a slab of fixed-size slots needs no search and no splitting: you pop a free slot off that class's list, and freeing pushes it back. That alone turns the O(n) free-list walk into O(1).
Now solve contention by giving each thread its own private stash of these slots: a thread cache. The fast path of malloc(n) becomes — round n to a size class, pop a slot from this thread's cache for that class, done. No lock, no atomic, no shared memory touched, just a few instructions reading thread-local storage. free(p) is the mirror: find p's size class and push the slot back onto this thread's cache. Ninety-something percent of all allocations never go further than this. When a thread's cache runs dry it grabs a batch of slots from a shared backing store under one lock, amortizing that lock across dozens of allocations — the amortized cost of the lock falls toward zero.
malloc(n): fast path slow path (cache empty)
---------------------------------------- ----------------------------
c = size_class(n) // round up lock(central[c])
slot = tcache[c].pop() // thread-local grab a BATCH into tcache[c]
if slot != NULL: unlock(central[c])
return slot // no lock! return tcache[c].pop()
central store, if empty, splits a fresh run/span/slab from a big arena
(mmap'd region), carved into fixed-size slots for class c.Where the three diverge
Given that shared skeleton, the interesting engineering is in the choices each one made for the shared backing store behind the thread caches — the layer that fights fragmentation and decides how memory comes from the kernel. tcmalloc (Google, "thread-caching malloc") is the purest expression of the blueprint above: per-thread caches in front of a central free list per size class, backed by a page heap that hands out runs of OS pages. Its whole identity is fast small-object allocation for huge multi-threaded services, with the thread cache front and center.
jemalloc (originally for FreeBSD, then famously Facebook's) leans on the arena idea from guide 2. It splits the heap into several independent arenas, each a self-contained allocator with its own locks and free structures, and assigns each thread to an arena. Two threads on different arenas never contend at all, even on the slow path — it is contention reduction by partitioning the heap itself, not just by caching in front of one shared heap. jemalloc also invests heavily in deliberate fragmentation control and tunability, with rich runtime statistics; that combination of low fragmentation and predictability is why it earned a reputation for taming long-running server processes whose memory would otherwise creep upward for days.
mimalloc (Microsoft, 2019) is the youngest and pushes a different lever: per-thread heaps built from "pages" of one size class each, with a clever free list sharding scheme. The deep idea is to keep frees local. When thread A frees a block that thread B originally allocated, that block belongs to B's page; mimalloc uses a separate atomic "thread-free" list per page so the cross-thread free is one lock-free atomic push, and B later reclaims a whole batch at once. The result is a tiny, fast fast-path and good behaviour even in producer-consumer patterns where one thread allocates and another frees — the case that punishes naive thread caches.
The hard parts they all must face
Thread caching is not a free lunch; it creates problems the simple allocator never had, and how each one solves them is most of the remaining engineering. The first is cache blowup: every thread holding its own stash of every size class can pin a lot of memory that no one is using. A thread that mallocs a megabyte's worth of slots, then sleeps forever, keeps them hostage. So caches have size limits and periodically flush idle slots back to the shared store — a direct trade of a little extra memory for a lot of speed, and a knob real deployments tune.
The second is the producer-consumer free, the case mimalloc targets head-on: thread A allocates, hands the object to thread B, and B frees it. The block belongs to A's cache or arena, so B cannot just drop it into its own thread-local list without leaking it from A's accounting. Every production allocator needs a safe path for these remote frees — a per-thread or per-page list that the owner reclaims later — and getting it both correct and lock-free is genuinely subtle, leaning on the atomic operations and memory-ordering ideas from the synchronization rung. This is one place where "just use a thread cache" stops being trivial.
The third is hardware locality. On a multi-socket machine, memory physically attached to socket 0 is slower to reach from socket 1; a good allocator practises NUMA-aware allocation, steering a thread's memory to its own socket so it does not pay the cross-socket penalty on every access. Closely related is alignment: large allocations are aligned so they can map cleanly onto huge pages, and slot sizes are chosen to spread objects across cache lines rather than packing two hot objects onto one line where two cores would fight over it. The allocator is, quietly, a performance-engineering tool that shapes how your data meets the memory hierarchy.
Using one in practice — and what it cannot fix
The lovely part is how little it costs to try one. Because all three obey the same malloc()/free() interface as the system allocator, you can swap them in without touching a line of your code — this is allocator interposition. You link the library in, or even just preload it at run time, and every malloc() in your process is silently rerouted. Here is the no-recompile path on Linux:
- Build normally, against the ordinary headers: gcc -O2 -Wall main.c -o app — you change nothing in the source.
- Preload the allocator at launch so its malloc() wins over libc's: $ LD_PRELOAD=/usr/lib/libjemalloc.so ./app (or libtcmalloc.so, or libmimalloc.so).
- Measure, do not guess. Run your real workload under each and watch peak resident memory and tail latency — the right allocator is workload-dependent, and the only honest answer comes from your own numbers.
Be clear-eyed about the limits, though, because a faster allocator is not a fix for a buggy program. Switching to jemalloc will not cure a memory leak — if your code never calls free(), no allocator can reclaim the memory; it just leaks faster or with prettier statistics. It will not save you from a use-after-free or a double free; in fact a different allocator can make such bugs surface differently, so a program that "worked" on glibc may crash under jemalloc precisely because it was relying on undefined behaviour all along. And no allocator escapes fragmentation entirely — these designs manage it brilliantly, they do not abolish it.
Stand back and see the whole rung in one frame. You started with the allocator's job and a single linked list; you added arenas and bump pointers, slabs and the buddy system, size classes and alignment. Every one of those was a piece these production allocators bolt together: size classes give O(1) lookups, slabs give search-free fixed-size pools, arenas partition contention, thread caches make the common case lock-free, and boundary tags and coalescing still lurk in the slow paths fighting fragmentation. jemalloc, tcmalloc, and mimalloc are not exotic — they are your guide-1 allocator, hardened for many cores and measured against the real cost model of the machine.