Why does a per-thread allocator cache refill and flush in batches against the shared arena instead of one block at a time?
answer
- one visit serves many allocations
- batch size divides the contention rate
- a single threshold can oscillate
- land between the two marks
- paid for in footprint and tail latency
basics
~20 sEach trip to the shared arena costs a lock acquisition, so moving a batch amortizes it over many allocations. Separate low and high water marks stop a program sitting on the boundary from taking that lock every time.
solid answer
~50 sA cache that fetched one block per visit would meet the shared arena once per allocation — exactly the contention it was built to remove, with an extra indirection on top. Moving `B` blocks per visit cuts the rate at which threads meet each other by a factor of `B`, so the batch size is the dial that sets residual contention. The second reason is **hysteresis**. With a single threshold, a loop that allocates and frees one block while sitting exactly on that threshold crosses it in both directions on every operation, taking the lock each time — worse than having no cache. Using a low-water mark to refill and a higher high-water mark to flush, and landing the count inside the band rather than on its edge, means the next crossing needs many operations in the same direction. The cost of a large batch is footprint, a latency spike on the refill itself, and blocks whose data is cold by the time they are used.
go deeper
Recall the idea of a bulk trip: fetching many items at once means fewer journeys to the place where everyone has to queue.
Quantify it. Refilling B blocks per visit divides the arena visit rate by B, and the cost is memory held privately plus one slower allocation whenever a refill fires.
Explain hysteresis with the boundary case: a single threshold can make an alternating allocate-and-free loop take the shared lock twice per iteration, worse than not caching at all.
Treat batch size as a fleet-wide policy dial with a footprint bill and a tail-latency bill, and prefer per-class adaptive sizing over one number applied to every service.
## The arithmetic of batching In steady state a thread allocating at rate `R` from a cache refilled `B` blocks at a time meets the shared arena `R/B` times per second. With sixty-four threads that is `64 x R/B` arrivals at one lock, against `64 x R` if the cache fetched one block per visit. The batch size is therefore a **direct divisor on contention**, and its effect is the same shape as the cache's own: the first factor of ten matters enormously, the next one much less, because contention falls until the arrival rate drops below what the lock can serve, after which further reduction buys nothing. That is why real batch sizes are tens of blocks, not thousands. Batching also amortizes work beyond the lock itself: - **Unlink cost.** Detaching a chain of `B` blocks from an arena-side list is close to the cost of detaching one, because the list is threaded through the blocks. - **Metadata updates.** Run descriptors and counters are updated once per batch rather than once per block. - **Locality.** Blocks taken as a batch usually come from the same run, so consecutive allocations land near one another in memory. ## Why one threshold thrashes Consider a loop that allocates a block, uses it, frees it, and repeats, and suppose the cache uses a single threshold `T` with the rule: refill when empty, flush down to zero when the count exceeds `T`. Now put the loop at a point where the cache's count is exactly at `T`. The free pushes a block and trips the flush, returning everything to the shared arena. The next allocation finds the list empty and refills. Every iteration performs both a flush and a refill — **two lock acquisitions per allocation**, which is strictly worse than the unbatched shared allocator. The fix is **hysteresis**: two marks, and a landing point between them. | Rule | Behaviour at the boundary | |---|---| | One threshold, flush to empty | Crosses the bound on nearly every operation; two lock trips per iteration | | Low mark and high mark, land in the middle | After a crossing, the count sits far from both bounds; the next crossing needs roughly half a batch of operations in one direction | The general principle is not specific to allocators: any threshold that triggers an expensive action must leave the system **away** from the threshold, or a workload that sits on it will pay the expensive action continuously. ## Choosing the batch size | Larger batch | Smaller batch | |---|---| | Fewer arena visits, less contention | More arena visits, more contention | | More free memory parked per thread | Less memory held outside the live set | | Occasional long refill shows up in tail latency | Smoother per-allocation cost | | Better locality within a batch | Stock returns to the shared pool sooner | Two refinements are common. First, **per-class batch sizes**: a class of tiny blocks is allocated far more often and costs little to hold, so it deserves a bigger batch than a class near the large-object boundary, where a batch of the same count could hold megabytes. Second, **adaptive sizing**: start small and grow the batch for a class the thread keeps draining, shrink it for a class it has not touched, so a thread's cache comes to reflect what that thread actually allocates rather than a fixed table. ## What to measure 1. **Arena visit rate per thread.** If refills per second per thread are high relative to the allocation rate, the batch is too small or the workload straddles a boundary. 2. **Cached free bytes across all threads.** This is the footprint side of the dial and it scales with thread count. 3. **Allocation latency distribution.** A bimodal shape — a cheap mode and a rare expensive one — is exactly what batching produces, and a tail that is too heavy argues for a smaller batch. 4. **Flush and refill counts for the same class.** Similar counts for a class in steady state mean the cache is oscillating rather than serving, which is the thrash signature. The summary an interviewer wants: batching converts many small coordinations into one larger one, hysteresis stops the boundary itself from becoming a hot path, and both are paid for in memory held privately and in a lumpier latency profile.
- Why not simply use a very large batch and stop worrying about contention?Because the memory parked in caches is threads times classes times batch size, and it is unavailable to every other thread. A very large batch also makes each refill a long operation that shows up in tail latency, and the returns fall away once arrivals at the shared arena are already below what the lock can serve.
- Should every size class use the same batch size?Usually not. A batch is a count of blocks, so the same count holds wildly different amounts of memory across classes. Small classes are allocated most often and cost little to stock, so they take larger batches; classes near the large-object boundary take small ones, and many allocators adapt the count per class to the thread's observed demand.
saying these in an interview costs you the question
- Thinks a bigger batch is strictly better with no cost attached
- Believes batching removes the shared arena from the design entirely
- Misses that one threshold can cause a lock trip per operation
- Assumes the same block count is appropriate for every size class
- Treats a bimodal allocation latency profile as evidence of a bug