a thread-local cache and the contention problem
Picture a busy warehouse with one central stockroom and one clerk who guards the door. If every worker has to queue at that door for even the smallest part, the whole floor slows to the clerk's pace — that single door is the bottleneck. Now give each worker a small personal toolbox stocked with the parts they use most. Most of the time they just reach into their own box, no queue, no clerk. That personal toolbox is a thread-local cache, and it is the central trick that lets a memory allocator scale across many threads.
The contention problem it solves is this: a simple allocator protects its one shared heap with a lock (a mutex). When many threads call malloc() and free() at once, they serialize on that lock — each must wait its turn — so adding more cores stops helping and can even hurt, because threads spend their time fighting over the lock and bouncing the heap's data between CPU caches. A thread-local cache fixes it by giving each thread a small private stash of free blocks, organised by size class, kept in thread-local storage. The fast path of malloc becomes: look in my own cache for a free block of this size class and pop it — purely thread-local, no lock at all. free becomes: push the block back onto my own cache. Only when a thread's cache is empty (or overflowing) does it briefly take the shared lock to refill or flush a whole batch at once, so the expensive synchronized operation is amortized over many cheap local ones.
This is why every scalable allocator — tcmalloc, jemalloc, mimalloc — is built around thread caches, and why swapping one in can transform a multithreaded server's throughput. The honest tradeoffs: thread caches cost memory (each thread holds blocks it is not currently using, so total footprint grows with thread count), and they can cause blow-up when one thread allocates a block and a different thread frees it (the block ends up cached on the wrong thread), so allocators add machinery to migrate or periodically purge caches. The cache is a speed-versus-memory bargain, not a free lunch.
/* fast path: no lock, look only in this thread's own cache */ _Thread_local struct free_block *tcache[NCLASSES]; void *fast_malloc(size_t n) { size_t c = size_to_class(n); struct free_block *b = tcache[c]; if (b) { tcache[c] = b->next; return b; } /* HIT: thread-local, lockless */ return refill_from_central(c); /* MISS: take lock, grab a batch */ }
The common case touches only thread-local storage and takes no lock; the shared lock is hit only to refill in bulk.
Thread caches trade memory for speed: each thread pins free blocks it is not using, so footprint grows with thread count, and cross-thread free (alloc on one thread, free on another) needs extra handling to avoid blow-up.