Thread-Local Caches

Take a perfectly tuned single-threaded allocator and run it on 32 cores: performance collapses. Every ALLOC and FREE grabs the same global lock, and the lock — not the allocation logic — becomes the bottleneck. On contended glibc malloc, threads can spend microseconds queueing for nanoseconds of work.

The fix that defines modern allocators (tcmalloc, jemalloc, mimalloc): give every thread a private stash.

Thread 1 cache           Thread 2 cache          Central free list
  16: [b,b,b]              16: [b]                 16: [b,b,b,b,...]
  32: []                   32: [b,b]               32: [b,b,...]
      no lock                  no lock                ONE lock

Fast path: ALLOC pops from your own thread's cache and FREE pushes to it — no lock, no sharing, no cache-line ping-pong between cores. The central list is touched only when a local cache runs dry or overflows, and then in BATCHES, so one lock acquisition is amortized across many operations. Batching is the entire trick: lock cost divided by batch size.

The exact protocol you will implement

Constants: CACHE_MAX = 5 blocks per class per thread, BATCH = 4 fetched on a miss, HALF = 3 returned on overflow.

ALLOC <tid> <class>:

• Cache has blocks: pop one, print local.
• Cache empty: fetch BATCH (4) from central under one lock, hand 1 to the caller, keep the other 3 in the cache. Print central.

FREE <tid> <class>:

• Push the block into the cache. If the count is still within CACHE_MAX (at most 5), print local.
• If the push overflows (the count would reach 6), return HALF (3) blocks to central, leaving 3 cached. Print flush.

Trace the ALLOC rhythm — this is test 2 verbatim:

ALLOC 1 16 -> central    (miss: fetch 4, keep 3)
ALLOC 1 16 -> local      (2 left)
ALLOC 1 16 -> local      (1 left)
ALLOC 1 16 -> local      (0 left)
ALLOC 1 16 -> central    (miss again)

Caches are per-thread AND per-class. Thread 2's first ALLOC is a miss even when thread 1's cache is full — hidden test 5 prints central, central, local for the sequence thread 1, thread 2, thread 1. STATS <tid> reports only that thread's non-empty classes, sorted, as class=<c>:<count>.

Real-world calibration

tcmalloc caps each thread cache near 4 MB and scavenges the caches of idle threads — vital in thread-pool servers where most threads sleep most of the time. jemalloc's tcache is configurable per arena. The payoff, per published benchmarks: 10-30 ns per malloc/free on the fast path — about a hash-table lookup — and dramatically better tail latency than a contended global lock. Allocations that never leave the thread cache never contend at all.

Your exercise

Test 4 pins the overflow boundary: six consecutive FREE 1 16 must print local five times and flush ONLY on the sixth — the push that would make the count 6. The classic mistake is flushing when the cache merely REACHES CACHE_MAX, which prints flush on the fifth line where the grader demands local. The ALLOC side has its own trap: test 2's expected output is exactly central, local, local, local, central — if your miss path keeps all 4 fetched blocks instead of BATCH - 1 = 3 (forgetting to hand one to the caller), the rhythm shifts and the fifth line comes out local.