Memorycompulsorycapacityconflicttaxonomydiagnosis

Three Kinds of Miss, Three Different Fixes

Compulsory, capacity and conflict misses look identical in a counter and have almost nothing in common as problems. Prefetching helps one, blocking helps another, and layout changes help the third — so classifying the miss is what turns a measurement into a plan.

▶ Run the labFollow the mechanism

Software view, hardware view

The gap between what you wrote and what the machine does is where this whole domain lives.

The question
My miss rate is high — but which kind of miss is it, and does that change what I should do?
What you wrote
The profiler reports cache misses. There is one number, so it looks like one problem with presumably one class of fix.
What the hardware does
The misses have different causes: some data had never been touched, some was evicted because the cache was too small, and some was evicted despite free space because of where it mapped.
Because the fixes are disjoint and applying the wrong one wastes effort convincingly. Adding capacity does nothing for compulsory misses. Blocking does nothing for conflict misses. Changing alignment does nothing for a working set that is simply too big. Classification is the step that stops you optimising the wrong axis.
Source→Compiler→Instructions→Front End→Execution→Registers→Caches→Memory→I/O→Behavior

The three Cs

The classic taxonomy asks a counterfactual for each miss. Would it have missed in an infinitely large cache? Then it is compulsory — the data had never been fetched and something had to bring it in. Would it have hit in a fully associative cache of the same size? If not, it is capacity — the working set simply exceeds what fits. If it would have hit in a fully associative cache of the same size but missed in the real one, it is conflict — the placement rules, not the capacity, evicted it.

That framing is useful precisely because each counterfactual points at a different lever. Compulsory misses are reduced by fetching earlier or by fetching more per trip, not by having more room. Capacity misses are reduced by needing less at once. Conflict misses are reduced by changing which set an address maps to, which means changing addresses — alignment, padding or stride.

A fourth category is worth naming on multicore machines: coherence misses, where a line was invalidated because another core wrote to it. These are not a capacity or placement failure at all, and the fix is neither more cache nor better layout but reducing sharing (False Sharing: Independent Data, Shared Line, MESI and Its Relatives).

Same counter, four different problems
KindCauseTypical signatureWhat actually helps
CompulsoryFirst touch of a line; it was never residentScales with data volume, not with reusePrefetching, larger effective transfers, denser data
CapacityWorking set exceeds the cacheStep change as size grows past a levelBlocking, smaller footprint, fewer live structures
ConflictToo many hot addresses map to one setSensitive to stride and alignment; erraticChange alignment, padding or stride (Tag, Index and Offset: How an Address Finds Its Line)
CoherenceAnother core wrote the lineAppears only under threading; scales with coresReduce sharing; pad separated data (False Sharing: Independent Data, Shared Line)

Telling them apart in practice

You rarely get a counter that says "conflict". You infer the category from how the miss rate responds to controlled changes, which is a small set of cheap experiments.

Grow the working set gradually and watch for a step: a sharp transition at a size boundary implicates capacity. Change the stride slightly — from a power of two to a nearby odd number, or pad an array by one line — and watch the miss rate move sharply: that is the conflict signature, because you changed which sets are used without changing how much data there is. Run the same data twice and compare the first pass to the second: what remains on the second pass is not compulsory, and what disappears was.

The power-of-two stride case deserves special mention because it is so common and so surprising. Arrays dimensioned to exact powers of two frequently cause many rows to map to the same sets, which is why padding a matrix row by a single element sometimes produces a large speedup with no other change. It looks like superstition and it is Set-Associative Caches: The Compromise That Won arithmetic.

Power-of-two row length: rows collide in the same sets
1float a[1024][1024];   // row stride = 4096 bytes
2 
3for (i in 0..1024)
4    sum += a[i][0];    // walk one column
5 
6// Every element is 4096 bytes apart. With a power-of-two
7// stride, these addresses map to very few sets, so they
8// evict each other while most of the cache sits unused.
Padded row length: the same walk spreads across sets
1float a[1024][1024 + 1];   // row stride = 4100 bytes
2 
3for (i in 0..1024)
4    sum += a[i][0];        // identical walk
5 
6// One extra element per row shifts each successive address
7// into a different set. Same data, same instructions,
8// conflict misses largely gone.

Nothing about capacity or access order changed — only which sets the addresses map to. That is the definition of a conflict miss, and padding is the standard fix. It also shows why "add more cache" would not have helped: most of the cache was already idle.

The taxonomy is a model, not a physical fact

SIMPLIFIEDThe three-Cs model is defined against idealised caches; real misses can be mixed, prefetching reclassifies some compulsory misses, and multicore adds a coherence category the classical model omits

The three Cs are defined by counterfactuals against idealised caches, which means a real miss does not carry a label. A miss can be partly capacity and partly conflict — the working set is somewhat too large *and* poorly distributed — and reasonable people classify borderline cases differently. Prefetching further blurs the boundary by converting some compulsory misses into traffic that never appears as a demand miss at all.

This matters because the taxonomy is a thinking tool for choosing an experiment, not a measurement you can report. The productive use is: form a hypothesis about which category dominates, run the cheap experiment that would distinguish it, and act on the result. The unproductive use is arguing about how to classify a miss you have not tried to change.

It generalises well beyond CPU caches, which is part of why it is worth knowing. A database buffer pool has the same three failure modes — first read of a page, working set exceeding the pool, and hot pages mapping awkwardly — and the same three families of fix, which is why The Buffer Pool reasoning feels familiar once you have this framing.

The four experiments that classify a miss, in the order worth running them
1. FIRST vs SECOND PASS over the same fresh data
     second pass still misses  -> capacity or conflict
     second pass hits          -> the first pass was compulsory

2. SWEEP the working-set size, plot time per element
     sharp step at a size      -> capacity
     smooth curve              -> not capacity

3. PERTURB the stride: pad one array dimension by a single element
     large swing               -> conflict
     no change                 -> not conflict

4. VARY thread count, holding per-thread work constant
     miss rate grows w/ threads -> coherence, not cache sizing

None of these is a counter you can read directly. The category is
inferred from how the miss rate RESPONDS, which is why the model is
a hypothesis generator rather than a measurement.

Key points

  • Compulsory, capacity and conflict misses look identical in a counter but have disjoint fixes.
  • Compulsory misses respond to prefetching and denser transfers; capacity to blocking; conflict to alignment and stride changes.
  • Multicore adds coherence misses, where the fix is reducing sharing rather than anything cache-related.
  • Classify by controlled experiment — vary size for capacity, vary stride for conflict, compare first and second pass for compulsory.
  • Power-of-two array dimensions are a common conflict-miss trap, and padding by one element is the standard remedy.

Cache Simulator

Change an input and watch which number moves — and which one refuses to.

Cache simulator
SIMULATED
Access pattern
hit rate
87.5%
misses
250
evictions
186
over-fetch
1.0×
compulsory250
capacity0
conflict0
16 sets × 4 ways × 64 B

Almost all hits. Either the working set is resident or the pattern has enough spatial locality that each line pays for many accesses.

Follow the mechanism

The path through the machine, hop by hop — and the conclusions it invites that are wrong.

  1. 1
    First touch → compulsory miss: no copy exists anywhere on chip, so the line must be fetched regardless of cache size.
  2. 2
    Working set exceeds capacity → eviction before reuse: lines are displaced by other lines simply because there is not room.
  3. 3
    Address maps to a busy set → conflict eviction: the line is displaced although other sets have free ways (Tag, Index and Offset: How an Address Finds Its Line).
  4. 4
    Another core writes the line → invalidation: your copy is dropped for correctness, not for space (MESI and Its Relatives).
  5. 5
    Next access → refetch: in every case the line is re-fetched from further out, at the cost of wherever it now lives.
What people conclude from this — wrongly
  • • Concluding "we need a bigger cache" from a raw miss rate, when the misses are compulsory and capacity is irrelevant.
  • • Applying blocking to a conflict problem, getting a small improvement from the incidental layout change, and stopping there.
  • • Assuming a power-of-two array size is optimal because it makes the address arithmetic tidy.
  • • Treating the three-Cs classification as something a counter reports rather than something you infer.

Consequences, controls and cost

What it causes
  • • Adding cache capacity produces no improvement when the misses are compulsory or conflict-driven.
  • • A tiny change to an array dimension can produce a large, seemingly inexplicable speedup.
  • • Blocking a computation whose misses are conflicts yields disappointing results and wasted effort.
  • • Threaded code can show a miss rate that grows with core count while single-threaded behaviour is fine.
What you can do
  • • Run the distinguishing experiment before choosing a fix — size sweep, stride perturbation, first-versus-second pass.
  • • For capacity: block the computation, shrink the footprint, reduce the number of live hot structures ([[working-set]]).
  • • For conflict: pad array dimensions off powers of two, realign hot structures, or change the traversal stride.
  • • For compulsory: increase useful bytes per transfer through denser layout, or prefetch where the pattern is predictable.
  • • For coherence: separate per-thread data onto distinct lines and reduce genuine sharing ([[false-sharing]]).
How to see it
  • • Sweep the working-set size and look for step changes — a sharp step at a level boundary indicates capacity.
  • • Perturb the stride or pad an array by one element and re-measure; a large swing implicates conflict.
  • • Compare miss rate on a first pass over fresh data against a second pass over the same data to isolate compulsory misses.
  • • For threaded code, compare single-thread and multi-thread miss rates; growth with thread count implicates coherence.
What it costs
  • • Padding to avoid conflicts wastes memory and can push a working set past a level, trading one miss type for another.
  • • Blocking adds a machine-specific tuning parameter and makes the code harder to read.
  • • Prefetch hints are easy to get wrong and can evict useful data or waste bandwidth when the prediction is poor.

Scope

§224 — what these claims are specific to.

What these claims are specific to
  • SIMPLIFIEDThe three-Cs model is a teaching taxonomy defined against idealised caches; real misses are frequently mixed, and prefetching moves work between categories
  • GENERALThe same taxonomy and the same families of fix apply to database buffer pools and OS page caches; only the units and capacities change

Misconceptions

Claim
“A high miss rate means the cache is too small.”
Reality
Only for capacity misses. Compulsory misses are irreducible by capacity, and conflict misses can occur with most of the cache sitting unused. Determine which kind you have before concluding anything about size.
Claim
“Power-of-two array dimensions are best because the indexing arithmetic is cheapest.”
Reality
The address arithmetic is marginally cheaper and the cache behaviour is frequently much worse, because power-of-two strides concentrate accesses into few sets. Padding a dimension by one element is a well-known fix that costs a little memory and can remove a large fraction of misses.
Claim
“The three Cs are properties a performance counter reports.”
Reality
They are counterfactual definitions — would this have missed in an infinite cache, or in a fully associative one? No hardware answers that directly. You infer the category from how the miss rate responds to controlled changes in size, stride and thread count.

Apply it

🔍 Fast at 1023 Columns, Slow at 1024🔍 A Hundred Per Cent Busy and Getting Nothing Done
← Hits, Misses and What a Miss Actually CostsDirect-Mapped Caches: One Address, One Home →