Working Set Size and the Miss-Rate Cliff

Strip a program of everything except its memory accesses and one variable remains: how much distinct memory it touches between reuses of the same data. That quantity, the working set, predicts performance better than instruction count, allocation count, or any property of the source. Programs whose working set fits in a cache level run at that level’s latency; programs whose working set exceeds it pay the next level’s latency for most accesses. The transition between those two states is abrupt, and its abruptness is what makes working set size the first thing to measure.

The knee, not the slope

If cache misses grew linearly with working set size, tuning would be a matter of shaving bytes until the curve flattened. They do not. The miss rate stays near zero while the working set fits, rises slowly as it approaches capacity, and then rises steeply over a small range. Plotting misses against working set produces a shape with a distinct knee, and the knee sits at the capacity of the largest cache level the data still fits in.

The mechanism behind the knee is that a cache of size C holding a working set of size W behaves very differently for W < C and W > C. Below capacity, a line evicted by a conflict is likely to be replaced by a line that will not be reused soon, and the reuse distance of the working set is less than C, so the replacement policy, even a poor one, has enough slack to keep the hot lines. Above capacity, every reuse is a compulsory miss: the data cannot be retained because there is no room, and no replacement policy helps.

For a fully associative cache with optimal replacement, the miss rate as a function of W is predicted by the stack distance distribution: the fraction of accesses whose reuse distance exceeds C. That distribution is often close to uniform in the region above capacity, which produces a linear rise, and near zero below capacity, which produces the flat part. The knee is the corner where the two meet, and it is sharp because the reuse distance distribution itself usually has a step at W.

Real caches are not fully associative, and their miss rates depart from the model in both directions. Conflict misses add a component that persists even when W < C, and prefetching shifts the curve down. The knee remains, which is why the shape is usable as a diagnostic.

What counts as the working set

The working set is not the total allocated bytes. It is the set of bytes touched within a window of time short enough that touching them again still finds them in cache. Three definitions are useful in practice, and they give different numbers.

The footprint is the total distinct bytes touched over the whole run. It is an upper bound, easy to obtain, and almost always larger than the useful working set, because programs touch cold data once per run: configuration, metadata, code that executes during startup only.

The instantaneous working set is the bytes touched within a window of n accesses. This is the classic Denning definition and the one that matches what a cache holds. Its size depends on n, and the practical question is which n corresponds to a given cache. For a 1 MiB last-level cache and random access, the window is roughly the number of lines the cache can hold, on the order of 16000 lines at 64 bytes each; for sequential reuse, the window is larger because each line yields many consecutive accesses.

The reuse distance is the number of distinct lines accessed between two accesses to the same line. It is the most predictive of the three, because a cache of C lines can retain a line across a distance below C and generally cannot across a distance above it. Measuring the distribution of reuse distances for a workload gives the miss rate for every cache size at once, which is why the technique is used in cache simulation and in profiling tools that report reuse distance rather than miss counts.

The levels and their capacities

The cliff recurs at each level. Current server and desktop processors commonly have a private L1 data cache of 32 or 48 KiB per core, a private L2 of several hundred KiB to a few MiB, and a shared L3 in the range of a few MiB to tens of MiB per socket. The exact numbers vary by part and should be read from the CPU, not assumed, but the ordering of magnitudes is stable across vendors.

Approximate access latencies follow the same ordering: L1 hits cost around 4 to 5 cycles, L2 hits around a dozen, L3 hits a few dozen, and a main-memory access on the order of a hundred or a few hundred cycles, with translation lookaside buffer misses and remote-socket accesses adding further hundreds. Since a miss at the last level costs roughly two orders of magnitude more than a hit, a miss-rate change of a few percent near the knee can move total runtime by tens of percent.

The table below is a way to reason about where the cliff will be found, not a specification. Kernel versions differ in how much of the LLC is usable by page cache and how THP changes effective footprint, and the numbers are per-part.

Level	Typical capacity	Approximate latency	Primary determinant of miss rate
L1 data	32-48 KiB per core	~4-5 cycles	Loop body footprint, stride
L2	256 KiB-2 MiB per core	~12-20 cycles	Loop nest working set
L3	4-64 MiB shared	~40-80 cycles	Footprint of hot phases, sharing
DRAM	GiB	~100-350 cycles	Total footprint, access pattern

The last column is the important one. Each level’s miss rate is set by a different property of the program, so a single “working set” figure that does not say which level it refers to is not actionable.

Locating the knee by construction

The reliable way to find the knee is to build a synthetic access pattern with a controlled working set and measure it across sizes. The pattern matters: sequential and random access produce different curves for the same footprint, so the synthetic loop must match the real one’s reuse structure.

#include <stdint.h>
#include <stdlib.h>

/* Chase a permutation of `n` slots, one dependent load per step.
 * Accesses are random over exactly n * stride bytes of address space. */
double chase(uint32_t *perm, size_t n, size_t steps)
{
    uint32_t i = 0;
    for (size_t s = 0; s < steps; s++)
        i = perm[i];         /* address of next load depends on the last */
    return (double)i;
}

Varying n through the size of each cache level and measuring cycles per step produces the curve directly. The dependent chain makes each step’s latency the full miss latency rather than overlapping with the next, which is why this shape is used to measure latency rather than bandwidth; the distinction between the two regimes is the subject of Bandwidth-Bound and Latency-Bound Work.

For real programs, the equivalent measurement is a footprint sweep: run the same phase with input sizes spanning the cache capacities and record the hardware cache-miss counters at each size. perf stat with the cache-misses and cache-references events gives the pair, and the ratio plotted against input size shows the knee. The counters are not identical to a simulator’s miss count, but their shape is.

Why the cliff is sharper in practice than in theory

Several mechanisms steepen the transition beyond what a simple capacity model predicts.

The first is the translation lookaside buffer. As a footprint grows, it also spans more pages, and a TLB that holds a few hundred to a couple of thousand entries covers a bounded amount of memory. Once the footprint exceeds that coverage, every access risks an additional page walk, which is itself several memory accesses. The TLB cliff and the cache cliff often occur at nearby footprint sizes, compounding each other, and the compounded curve is steeper than either alone.

The second is prefetcher saturation. A prefetcher works by recognising a stream and issuing requests ahead of demand. When the footprint fits in cache, prefetched lines are used; when it does not, the prefetched lines are evicted before the demand access arrives, and worse, they consume bandwidth and displace other lines. The prefetcher’s contribution can therefore go from positive to negative across the knee, inverting part of the curve.

The third is that the footprint of a real program is not stationary. A workload that alternates between two phases, each with a working set below capacity but with the combined set above it, behaves differently from one with a working set equal to the union. In the alternating case each phase transition evicts the other phase’s data, so each phase begins cold, and the effective miss rate is that of the full footprint even though the instantaneous working set is smaller. This interference is the reason per-phase measurements can look excellent while the whole-program profile looks poor.

What to do with the measurement

The location of the knee determines which class of fix applies. If the working set already fits and performance is still poor, the problem is latency or dependency structure, not capacity, and blocking or splitting will not help. If the working set exceeds the last-level cache by a factor of two, blocking the traversal so that each block fits is the direct fix, and it typically recovers most of the loss. If it exceeds by orders of magnitude, blocking at cache granularity is futile and the relevant levers are reducing bytes per useful item, as described in Bytes Fetched per Field, improving access order at a coarser level, or avoiding the traversal entirely.

The mistaken fix is to reduce the footprint by shrinking data structures when the footprint is dominated by an array that cannot shrink. Moving a 44-byte record to 40 bytes rarely crosses a knee; reordering a traversal so that the hot subset is contiguous often does. The distinction between shrinking and reordering is the distinction between moving along the curve and moving the curve, and only the second produces a step change.

One further diagnostic is worth keeping: measure the curve at two input sizes far apart, not at many. A workload whose time per element is roughly constant across a tenfold input range is compute-bound or latency-bound in a way that capacity does not explain; one whose time per element rises sharply between the two sizes is capacity-bound, and the knee lies between them. The ratio of the two per-element times is a cheap estimate of how much headroom a capacity fix could recover, before any code is changed.