Cache Misses: The Three Cs

A cache miss occurs when a requested memory block is not present in the cache and must be fetched from a lower level of the memory hierarchy. Miss rate — misses divided by total accesses — is a central performance metric, but a raw miss rate alone tells a designer nothing about what to change. The Three Cs model, decomposes total misses into three mutually exclusive, collectively exhaustive categories. A compulsory miss (also called a cold or first-reference miss) happens the very first time a block is touched by the program, since it cannot possibly already be in the cache. Compulsory misses would occur even in an imaginary cache of infinite size with full associativity, because no amount of retained history helps you before you've seen the data once. The only real levers against compulsory misses are increasing block size (so one miss brings in more useful neighboring data) and prefetching (fetching blocks before they're requested). A capacity miss happens when the cache is fully associative but too small to hold the entire working set of the program between reuses. Even with an optimal replacement policy and unlimited placement freedom, blocks that were evicted to make room for others must be re-fetched. Capacity misses isolate the pure effect of cache size. The only cure is more capacity — a bigger cache, a smarter working-set-reducing algorithm, or a memory hierarchy level (like an L2 or L3) that catches what L1 evicts. A conflict miss happens only because the cache does not have full associativity: a block is evicted (and must later be re-fetched) even though a fully associative cache of the same total size would have kept it, because some other block competing for the same limited set of slots pushed it out. Conflict misses are the price paid for cheaper, faster hardware — direct-mapped and low-associativity set-associative caches are simpler and faster to probe, but they restrict where a block can live, causing collisions that a fully associative design would avoid. The cure is more associativity (moving along the Fully Associative Caches and the Design Spectrum) or a better placement/replacement scheme. Formally, for a given cache size $C$, block size $B$, and associativity $A$, define three reference caches:

• $\text{Cache}_\infty$: infinite size, fully associative (block size $B$ fixed) — measures only compulsory misses.
• $\text{Cache}_{C,\text{FA}}$: finite size $C$, fully associative — measures compulsory + capacity misses.
• $\text{Cache}_{C,A}$: the actual cache under study, size $C$, associativity $A$ — measures compulsory + capacity + conflict misses.

Then:

These three quantities sum exactly to the total misses of the real cache, by telescoping subtraction — this is the entire mathematical content of the model, and it is exact by construction, not an approximation, given a fixed reference ordering (fully associative caches must use an optimal or LRU-style policy consistently, discussed below).

Classifying a miss stream requires simulating multiple caches side-by-side on the same address trace and comparing outcomes access-by-access. This is a standard technique in architecture research (trace-driven simulation) and is directly implementable. The key subtlety: to make the three categories well-defined, all three reference caches must use the same replacement policy family (conventionally LRU) so that differences in miss counts are due only to size and associativity, not to different eviction luck. This connects directly to Cache Replacement Policies — the Three Cs model implicitly assumes a "good" (typically LRU or OPT) policy is used uniformly, otherwise a bad replacement choice could masquerade as a capacity or conflict miss. ```pseudocode

# Classify every access in a trace into COMPULSORY, CAPACITY, CONFLICT, or HIT.

# Requires three synchronized cache simulators sharing LRU replacement. function CLASSIFY_MISSES(trace, C, B, A):

# trace: sequence of block addresses (already divided by block size B)

# C: real cache capacity in blocks; B: block size; A: associativity of real cache infiniteCache = new FullyAssocCache(capacity = INFINITY, policy = LRU) capacityCache = new FullyAssocCache(capacity = C / B, policy = LRU) realCache = new SetAssocCache(capacity = C / B, ways = A, policy = LRU) counts = { COMPULSORY: 0, CAPACITY: 0, CONFLICT: 0, HIT: 0 } for addr in trace: hit_inf = infiniteCache.access(addr) # true = hit, false = miss (& insert) hit_cap = capacityCache.access(addr) hit_real = realCache.access(addr) if not hit_real: if not hit_inf: counts[COMPULSORY] += 1 # never seen before, anywhere elif not hit_cap: counts[CAPACITY] += 1 # seen before, but capacity evicted it else: counts[CONFLICT] += 1 # capacity cache kept it; only real cache lost it else: counts[HIT] += 1 return counts ``` ```pseudocode

# A minimal fully-associative / set-associative cache simulator with LRU. class Cache: function init(numSets, ways): self.numSets = numSets # 1 for fully associative self.ways = ways self.sets = array of LRUSet(ways) for each of numSets function access(blockAddr): setIndex = (numSets == 1) ? 0 : (blockAddr mod numSets) s = self.sets[setIndex] if blockAddr in s.tags: s.touch(blockAddr) # move to most-recently-used position return true # HIT else: if s.isFull(): s.evictLRU() # remove least-recently-used tag s.insertMRU(blockAddr) return false # MISS ``` The algorithm's structure guarantees the classification is mutually exclusive: the `if / elif / else` chain checks strictly nested conditions (real cache miss, then infinite-cache status, then capacity-cache status), so exactly one bucket is incremented per real miss.

Time and space complexity of classification. Given a trace of $N$ accesses, the classification algorithm runs three cache simulations in parallel. A fully associative cache with LRU can be implemented with a hash map plus a doubly linked list (for LRU order), giving $O(1)$ amortized time per access for lookup, touch, insert, and evict. A set-associative cache with $A$ ways does an $O(A)$ scan (or $O(1)$ with per-way tag comparators, as in real hardware, but $O(A)$ in a straightforward simulator) per access. Total time is:

for the full trace (the $A$ term dominates only the real-cache simulation; the two fully associative caches are $O(N)$ each). Space is $O(U)$ for the infinite cache, where $U$ is the number of unique blocks touched (bounded by $N$), and $O(C/B)$ for each finite cache — so overall space is $O(N + C/B)$.

Correctness — why the decomposition is exact, not heuristic. The argument rests on a monotonicity / containment lemma: for LRU replacement, if cache $X$ has less associativity or less capacity than cache $Y$ (with $Y$'s configuration otherwise a "superset" of $X$'s placement freedom and size), then any block resident in $X$ at a given time is also resident in $Y$ at that time, provided both are driven by the same access sequence and both use LRU. This is a classical inclusion property: fully associative LRU caches of increasing size are stack-based — the contents of a size-$k$ cache are always a subset of the contents of a size-$(k+1)$ cache at every point in time (Mattson et al.'s stack-distance argument). Consequently:

• If the infinite cache misses, the block has never been seen — a true compulsory miss, and no cache configuration could have prevented it.
• If the infinite cache hits but the size-$C$ fully associative cache misses, the block was seen before but capacity limits (not placement limits) evicted it — by the inclusion property, this eviction is attributable purely to insufficient size, since a fully associative cache already grants maximal placement freedom.
• If the size-$C$ fully associative cache hits but the real $A$-way cache misses, the only remaining difference between these two caches is restricted placement (some other block mapped to the same set forced an eviction that full associativity would have avoided) — a true conflict miss.

Because the chain of implications is strictly nested (miss in real cache $\Rightarrow$ check infinite $\Rightarrow$ check capacity-limited), every miss falls into exactly one bucket, and the buckets sum to total misses by simple arithmetic (each stage subtracts off exactly the previous stage's count). This is why the model is described as exact by construction rather than approximate: it is a definitional partition of a fixed miss count, backed by the inclusion property that guarantees the comparison is apples-to-apples.

Honest caveats. The model assumes a single, unified, fully-associative reference policy (typically LRU) at each stage; the inclusion/stack property holds rigorously for LRU (and other "stack algorithms" like Belady's optimal OPT) but not for all replacement policies (e.g., FIFO is not a stack algorithm and can exhibit Bélády's anomaly, where a bigger cache has more misses — breaking the clean inclusion argument). Real caches also often use pseudo-LRU approximations for hardware cost reasons, which slightly blurs the conflict/capacity boundary in practice, but the model is still the standard analytical tool architects use, with the understanding that it idealizes replacement as true LRU. Also note: the three categories are defined relative to a fixed block size $B$ and a fixed reference "infinite cache" with that same block size. Changing block size changes what counts as compulsory (larger blocks reduce compulsory misses via spatial locality, but the same larger blocks may increase conflict misses by packing fewer blocks into each set) — this cross-coupling is discussed below.

Consider block-address trace (already in units of cache blocks, so consecutive integers are consecutive blocks):

Let the real cache have capacity $C = 2$ blocks, block size $B$ irrelevant here (already in block units), associativity $A = 1$ (direct-mapped), with 2 sets, so block address $x$ maps to set $x \bmod 2$. We compare against:

• Infinite, fully associative cache (never evicts).
• Capacity-limited fully associative cache, size 2, LRU.
• Real direct-mapped cache, size 2 (2 sets, 1 way each), LRU within — trivial since 1 way means no choice.

Let's verify the Cap-2 FA trace carefully with explicit LRU stacks (most-recent on left): 1. access 0 → miss, stack: [0] 2. access 1 → miss, stack: [1,0] 3. access 2 → miss, evict LRU=0, stack: [2,1] 4. access 0 → miss (0 not present), evict LRU=1, stack: [0,2] 5. access 3 → miss, evict LRU=2, stack: [3,0] 6. access 1 → miss, evict LRU=0, stack: [1,3] 7. access 2 → miss (2 not present!) — correction: this is actually a capacity miss, not conflict, since 2 was evicted at step 6. Let me redo the classification with this corrected Cap-2 FA trace. Recomputing column 4 with the correct LRU stack evolution:

With capacity 2 and a working set that keeps cycling through more than 2 distinct recently-used blocks, every access after the first two is a capacity miss in the FA-2 cache — this trace thrashes even fully associative caches at size 2, which is itself an instructive lesson: a small enough cache turns nearly everything into a capacity miss, leaving nothing left over to blame on conflicts. Final classification (infinite cache hits exactly when the address was seen at any earlier step):

Totals for this trace: Compulsory = 4 (blocks 0,1,2,3,4 are 5 unique blocks but block 4 appears once... actually unique blocks touched are {0,1,2,3,4} = 5, matching 5 compulsory misses: steps 1,2,3,5,10). Correcting the count: Compulsory = 5, Capacity = 7, Conflict = 0 (since Cap-2 FA already misses on everything the real direct-mapped cache misses on — the tiny 2-block cache is so capacity-starved that associativity is irrelevant here). Total misses = 12 out of 12 accesses (every access in the real direct-mapped cache misses, since with only 2 blocks and 5 unique addresses reused densely, nothing survives). This worked trace teaches an important lesson beyond the mechanical classification: when capacity is severely constrained, capacity misses dominate and conflict misses can vanish entirely, because there's no "extra" hardware freedom (full associativity) left to lose in the first place — the fully associative reference cache of the same tiny size is already thrashing just as badly. Conflict misses only show up distinctly when the fully associative cache of the same size would have done meaningfully better than the limited-associativity real cache — which requires a larger, less pathological cache size relative to the working set, as shown in the earlier compact SVG example.

The Three Cs framework crystallized from decades of cache-simulation research into memory hierarchy behavior, most influentially formalized in analyses connecting stack-based replacement algorithms (LRU, OPT) to cache-size inclusion properties — work that made rigorous the earlier empirical observation that "some misses would happen no matter what you do, and some misses are purely a hardware placement artifact."

Every general-purpose CPU cache hierarchy — L1, L2, L3 on chips from ARM, x86, and RISC-V implementations — is designed using exactly this reasoning. When architects decide L1 data caches should be small but highly associative (e.g., 32KB, 8-way) while L3 caches are large but lower associativity (e.g., 8MB, 16-way relative to size), they are directly trading off conflict-miss risk against hit-time and area, informed by Three-Cs-style simulation on representative workloads (SPEC benchmarks, real application traces). Compiler and systems engineers exploit the same taxonomy: loop tiling and blocking transformations in numerical linear algebra (BLAS, LAPACK) are explicitly designed to keep working sets under the cache's effective capacity, directly targeting capacity misses. Array padding techniques (adding unused columns to matrices) are a direct, well-known countermeasure against conflict misses caused by power-of-two strides colliding in the same cache sets. Hardware and software prefetchers in modern processors (stream prefetchers, stride prefetchers) exist specifically to hide the latency of compulsory misses by fetching blocks before first use. Translation lookaside buffers (TLBs) and disk/web caches use analogous compulsory/capacity/conflict reasoning even outside the CPU cache context, since the Three Cs model is a general property of any finite, associativity-limited caching structure, not just SRAM caches. This classification is also the conceptual stepping stone toward computing overall Cache Performance and Average Memory Access Time, where miss rate (decomposed by cause) combines with miss penalty and hit time into the single number that predicts real execution time.

Ask the tutor: Given a fixed total cache size, how do I choose the block size and associativity that jointly minimize the sum of compulsory, capacity, and conflict misses for a specific workload?