Thread-Local Caches

Take a perfectly tuned single-threaded allocator and run it on 32 cores, and performance collapses. Every ALLOC and FREE grabs the same global lock, and the lock, not the allocation logic, becomes the bottleneck: threads can spend microseconds queueing for nanoseconds of work. After this lesson your program will model the fix that defines tcmalloc, jemalloc and mimalloc: a private stash of blocks per thread, backed by a central list that is touched only in batches.

The idea

Thread 1 cache           Thread 2 cache          Central 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

The fast path: ALLOC pops from your own thread's cache and FREE pushes onto it. No lock, no sharing, no cache line bouncing 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 whole trick: the lock cost divided by the batch size.

The protocol you will implement

Constants: CACHE_MAX = 5 blocks per class per thread, BATCH = 4 blocks moved from central on a miss, HALF = 3 blocks returned to central on overflow. A cache is per thread AND per class.

ALLOC <tid> <class>:

• The thread's cache for that class has a block: pop it, print local.
• It is empty: take BATCH blocks from the central list under one lock, hand 1 to the caller and keep the other BATCH - 1 in the cache. Print central.

FREE <tid> <class>:

• Push the block onto the cache. If the cache now holds at most CACHE_MAX, print local.
• If the push made it exceed CACHE_MAX, return HALF blocks to the central list and print flush.

The central list is shared by every thread, and that is what makes recycling work. It holds held blocks per class. A miss takes min(BATCH, held) of them and creates the missing ones brand new from the OS, which the model counts as minted. A flush adds HALF to held. So memory freed by one thread can serve another thread's miss, and CENTRAL <class> prints held=<h> minted=<m> so you can watch it happen.

A short trace with thread 7 and class 48 (the tests use other numbers):

ALLOC 7 48    cache empty: central gives 4 (all minted), 1 handed out, 3 kept   -> central
CENTRAL 48                                                                      -> held=0 minted=4
FREE 7 48     cache 3 -> 4                                                      -> local
FREE 7 48     4 -> 5                                                            -> local
FREE 7 48     5 -> 6 is over the limit: 3 go to central, 3 stay                 -> flush
CENTRAL 48                                                                      -> held=3 minted=4
ALLOC 9 48    thread 9 is empty: central has 3, so 3 are reused and 1 is minted -> central
CENTRAL 48                                                                      -> held=0 minted=5

STATS <tid> prints that thread's non-empty classes in ascending numeric order, as class=<c>:<count>.

Real-world calibration

tcmalloc caps each thread cache near 4 MB and scavenges the caches of idle threads, which matters in thread-pool servers where most threads sleep most of the time. jemalloc's tcache is configurable per arena. The payoff, per published benchmarks, is 10 to 30 ns per malloc/free on the fast path, about a hash-table lookup, and much better tail latency than a contended global lock.

Common mistakes

• Flushing when the cache merely REACHES CACHE_MAX. Six frees in a row print local five times and flush once, on the sixth.
• Keeping all BATCH fetched blocks instead of BATCH - 1: one of them goes to the caller.
• Sharing a cache between threads or between classes. Each (thread, class) pair is its own counter.
• Sorting STATS classes as text, which puts 128 before 16.
• Minting BATCH fresh blocks on every miss instead of reusing what the central list already holds.

Your exercise

The starter holds the per-thread table and prints the replies. Implement the three accounting rules for ALLOC, FREE and CENTRAL. The tests include a thread that finds blocks another thread flushed, and a STATS over classes whose text and numeric order differ.