Working Set: Why Performance Falls Off a Cliff
The working set is the data a program actually touches in a window of time. Whichever level of the hierarchy it fits in determines what the program costs — and because the levels are discrete, crossing a boundary produces a step change rather than a gradual decline.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
What is actually hot
The working set is not the size of your allocation. It is the set of distinct cache lines touched within a window of time — and the window that matters is the one between reuses. A program streaming through a huge array has a *tiny* working set at any instant, because it touches each line once and never returns. A program randomly probing a moderate array has a large working set, because any line might be needed again at any moment.
This is why "the data is 4 GB" tells you almost nothing about cache behaviour, while "we revisit each row three times within a pass" tells you a great deal. The first is a storage fact; the second is a reuse fact, and reuse is what a cache monetises.
It also explains why two programs with identical memory footprints can differ by an order of magnitude. The one that touches its data in a compact, repeated pattern is served by a fast level; the one that scatters its accesses across the same footprint is served by a slow one. Same bytes, different working set, different machine underneath (Spatial Locality, Temporal Locality).
Why the curve steps instead of sloping
Capacity is discrete. A level either holds your hot data or it does not; there is no partial credit for being close. So as the working set grows past a boundary, the per-access cost does not drift upward — it switches to whatever the next level costs, which is several times more. Plotting time per element against size produces a staircase, with a plateau at each level and a sharp riser between.
The risers are not perfectly vertical, because a real workload has a distribution of reuse distances rather than one value: as the working set grows, an increasing fraction of accesses fall out of the level while the rest still hit. But the transition is narrow enough that engineers routinely experience it as a cliff, and small input changes produce disproportionate slowdowns.
Two practical consequences follow. First, benchmark inputs must span the boundaries, or you will characterise one plateau and generalise it wrongly (Every Way a CPU Microbenchmark Lies). Second, sitting deliberately just below a boundary is a real optimisation — and a fragile one, because effective capacity is shared and varies with what else is running.
| Observation | What it means | What to do |
|---|---|---|
| Flat cost per element across sizes | The working set is not crossing a boundary | Look elsewhere — this is not a hierarchy effect |
| One sharp step, then flat again | You crossed a single capacity boundary | Block the traversal so the hot set fits below it |
| Several steps at increasing sizes | Successive levels are being outgrown | Identify which step matters for production input sizes |
| Step position moves between runs | Effective capacity is shared and varying | Suspect co-tenancy or another thread on a shared level |
| Gradual slope with no step | Not a capacity effect | Check algorithmic cost or a non-memory bottleneck |
Shrinking the working set instead of the data
The lever is rarely "use less data" — the data is usually a requirement. The lever is to restructure *when* you touch it so that reuse happens while the line is still resident. Blocking a matrix multiplication does not reduce the number of multiply-adds by one; it reorders them so that a tile of each operand is reused many times before eviction. Same work, shorter reuse distance, different level of the hierarchy serving it.
The same idea appears throughout the stack under different names. A database processes rows in batches so a page stays in the buffer pool across its uses. A graphics pipeline processes in tiles. A join picks a build side small enough to stay resident. All are working-set reductions, and all are invisible to complexity analysis, which counts operations rather than transactions (Cache-Aware Algorithms).
The honest caveat: block sizes tuned to one machine are approximately right on others and occasionally wrong. Effective capacity depends on associativity, sharing, co-tenancy and what the prefetcher is doing. Pick a size from measurement, leave headroom rather than targeting the boundary exactly, and re-measure when the hardware changes.
1for i in 0 .. N-1:2 for j in 0 .. N-1:3 for k in 0 .. N-1:4 C[i][j] += A[i][k] * B[k][j]5 6// Between two uses of a given B element, the loop7// touches an entire row of A and a column of B.8// For large N that distance exceeds every level,9// so nothing is ever reused from cache.1for ii in 0 .. N-1 step T:2 for jj in 0 .. N-1 step T:3 for kk in 0 .. N-1 step T:4 for i in ii .. ii+T-1:5 for j in jj .. jj+T-1:6 for k in kk .. kk+T-1:7 C[i][j] += A[i][k] * B[k][j]8 9// Three T x T tiles are hot at a time. Choose T so10// they fit comfortably, and each element is reused11// many times before it can be evicted.The multiply-add count is identical. What changed is the number of distinct lines touched between two uses of the same line — which is the quantity the cache is actually sensitive to.
Key points
- The working set is what you touch in a window, not what you allocated — streaming has a tiny one, random probing a large one.
- Whichever level holds the working set sets the per-access cost, and levels are discrete, so the curve steps.
- Reuse distance is the operational quantity: distinct lines touched between two uses of the same line.
- Blocking and tiling reduce reuse distance without reducing work, which is why complexity analysis cannot see them.
- Effective capacity is smaller and more variable than nominal, because the level is shared with other data, cores and tenants.
Progressive depth
Overview
The working set is what you touch in a window, not what you allocated. A one-gigabyte array walked in small blocks has a small working set; a one-megabyte array touched randomly has a large one. Performance follows the working set, not the allocation.
Practical
Measure cost per element against input size and look for steps. Each step is a capacity boundary. Sitting just below one is comfortable; sitting just above is expensive; sitting exactly on one is unstable, because small changes in data or co-tenancy move you across it.
Advanced
The relevant quantity is reuse distance: how many distinct lines are touched between two uses of the same line. If reuse distance stays below a level's capacity, that level serves the reuse. Blocking and tiling are reuse-distance reductions — they do not reduce work, they reduce the gap between uses so it fits (Matrix Tiling: Same Arithmetic, Ten Times Faster).
Internals
Effective capacity is smaller than nominal capacity, and by a variable amount. Associativity limits which lines can coexist; the cache is shared with other data, instructions and — on shared levels — other cores; replacement is approximate; and on virtualised or multi-tenant hardware a co-tenant is consuming part of it. Treat measured cliff positions as authoritative and datasheet capacities as upper bounds (Cache Warmth and the Real Cost of Migration, NUMA: Not All Memory Is Equally Far).
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Loop → access stream: the program emits a sequence of line addresses over time.
- 2Stream → reuse distance: for each line, count the distinct lines touched before it is used again.
- 3Reuse distance → level: if that count fits within a level's effective capacity, the reuse is served there.
- 4Level → per-access cost: the serving level determines the cost, and the levels differ by large multiples.
- 5Working set grows → boundary crossed: the serving level switches outward and per-access cost steps up accordingly.
- • "Our data is 4 GB so caches are irrelevant" — a streaming pass over 4 GB has a small working set and benefits from every level.
- • "It scales linearly, we measured it" — measured on one plateau. The next size range may sit past a step.
- • "The tile size is optimal" — for one machine, one co-tenancy pattern, one input. Leave headroom instead of targeting exactly.
- • "Cache size from the datasheet tells me the boundary" — effective capacity is lower and varies; measure the cliff instead.
Consequences, controls and cost
- • Cost per element is flat across wide size ranges and then jumps, so single-point benchmarks mislead badly.
- • Two programs with identical footprints differ by an order of magnitude if their reuse distances differ.
- • Performance can change between runs when a co-tenant or sibling thread consumes part of a shared level.
- • Tuning that targets a boundary exactly is fragile; a small change in data or environment pushes it over.
- • Block or tile so the hot set fits comfortably inside a level, with headroom rather than at the boundary ([[matrix-tiling]]).
- • Shorten reuse distance by reordering work — process in batches, fuse passes that touch the same data.
- • Shrink the data itself where you can: narrower types and denser layouts increase what fits ([[aos-vs-soa]], [[data-oriented-design]]).
- • Benchmark across sizes that span the boundaries so you know where the steps are for your workload.
- • Sweep input size over several orders of magnitude and plot time per element; the steps localise the boundaries.
- • Compare miss rates per level across the sweep to confirm which boundary each step corresponds to ([[performance-counters]]).
- • Re-run the sweep under load from a co-tenant to see how much effective capacity a shared level actually offers.
- • Instrument reuse distance directly for a critical loop if the platform allows it — it predicts the cliff better than footprint does.
- • Blocked code is harder to read and easier to get wrong at boundaries than the straightforward triple loop.
- • Tile sizes tuned to one machine are merely adequate on others, and re-tuning is ongoing maintenance.
- • Denser layouts that improve residency can complicate code and reduce clarity for a benefit only visible under load.
Scope
§224 — what these claims are specific to.
- SIMPLIFIEDTreats each level as a clean capacity threshold. Real behaviour is blurred by associativity limits, sharing with instructions and other cores, prefetcher activity and approximate replacement.
- PLATFORM-SPECIFICEffective capacity depends on how much of a shared level co-tenants and sibling threads are using, which on virtualised hardware is outside your control or visibility.