Visual walkthrough — Cache miss types (compulsory, capacity, conflict)

Parent: Cache miss types. We will lean on Cache Associativity & Set Mapping, LRU and Replacement Policies, and Spatial and Temporal Locality as we go, and end pointing at Average Memory Access Time (AMAT).

---

Step 1 — What a cache actually is (a row of numbered boxes)

WHAT. A cache is a small set of storage boxes. Each box holds one block — a fixed-size chunk of memory (say 64 bytes) that always moves as one unit. We will label each block by a plain integer, its block number $B$ (0, 1, 2, …). Think of $B$ as "which 64-byte chunk of memory this is."

WHY. Before we can talk about a miss, we need a picture of the thing that can be full or empty. The cache is just boxes; a hit means "the block you asked for is sitting in a box already"; a miss means "it isn't — go fetch it from slow memory."

PICTURE. Below: memory is a long strip of numbered chunks on the left. The cache is four boxes on the right. An arrow shows one block being copied in.

---

Step 2 — The mapping rule: where is a block allowed to sit?

WHAT. A cache doesn't let a block go into any box. A direct-mapped cache gives each block exactly one legal box, chosen by a rule. If there are $S$ boxes (called sets), the legal box for block $B$ is:

$\underset{\text{which box}}{\underbrace{\text{index}}}=\underset{\text{block number}}{\underbrace{B}}\mathrm{mod}\underset{\text{number of sets}}{\underbrace{S}}$

Here $\mathrm{mod}$ means "the remainder after dividing." Term by term: take the block number $B$, divide by the number of boxes $S$, and the leftover tells you the box.

WHY this operation and not another? We need a rule that (a) is instant to compute in hardware and (b) spreads blocks across all boxes. Remainder-after-division does both: consecutive blocks $0,1,2,3$ land in boxes $0,1,2,3$, then it wraps around — block $4$ goes back to box $0$. That wrap-around is the seed of every conflict miss, so keep your eye on it.

PICTURE. Blocks $0,1,2,3,4,5$ each shown with an arrow to their forced box. Notice $0$ and $4$ point at the same box (both give remainder $0$).

---

Step 3 — The three imaginary caches (our measuring instruments)

WHAT. To ask "could a better cache have avoided this miss?" we build three reference caches and run the same request sequence through each:

1. Infinite cache — unlimited boxes, never evicts anything.
2. Fully-associative, finite — exactly $C$ boxes but no mapping rule; a block may sit anywhere, and we evict using LRU (throw out the least-recently-used block).
3. Real cache — $C$ boxes and a mapping rule (e.g. direct-mapped).

WHY. Each imaginary cache switches one cause of misses off:

• The infinite cache removes "ran out of room" and "mapping clash" — only truly-first-touch misses survive.
• The fully-associative finite cache removes "mapping clash" only — first-touch and ran-out-of-room survive.
• The real cache lets all three happen.

So each cache is a filter, and the difference between two filters isolates exactly one cause. This subtraction trick is the whole engine of the 3 C's.

PICTURE. Three cache diagrams side by side, each labelled with which miss causes it still allows (green = allowed to survive, faded = filtered out).

---

Step 4 — Naming the three causes by the questions they answer

WHAT. For a real miss, walk a chain of yes/no questions:

1. First reference ever to this block? → Compulsory (a.k.a. cold miss). It would miss even in the infinite cache.
2. Not first, but would the fully-associative finite cache also miss? → Capacity. The block was evicted purely because $C$ boxes couldn't hold your whole working set.
3. Fully-associative would have hit, real cache missed? → Conflict. Only the mapping rule caused the eviction.

WHY the chain is safe. The questions are asked in order and are mutually exclusive: a miss is compulsory, else capacity, else conflict — no miss escapes, none is counted twice.

PICTURE. A decision tree: one miss enters at the top, flows through the three questions, exits coloured by type.

---

Step 5 — Watch a pure conflict form (the thrash)

WHAT. Direct-mapped, $S=4$ boxes. Request the block stream 0, 4, 0, 4, 0, 4. Since $0\mathrm{mod}4=0$ and $4\mathrm{mod}4=0$, blocks $0$ and $4$ both demand box 0 and evict each other forever.

WHY this is conflict not capacity. Only two distinct blocks are ever used. A fully-associative cache with $C=4$ boxes has tons of room — it would keep both and hit every time after the first two. The real cache misses only because of the mapping clash. Subtract: $M_{\text{full}}=2$, $M_{\text{real}}=6$, so $M_{\text{conflict}}=6-2=4$.

PICTURE. Box 0 flip-flopping between $0$ and $4$; a red "thrash" arrow bouncing back and forth while boxes 1–3 sit empty (the wasted room that proves it isn't capacity).

Access	Result	Why
0	Compulsory	first touch of 0
4	Compulsory	first touch of 4 (evicts 0)
0	Conflict	seen before; fits fully-assoc → clash
4	Conflict	thrash
0	Conflict	thrash
4	Conflict	thrash

Cure: just 2-way associativity lets both live in set 0 → all conflicts vanish, no bigger cache needed.

---

Step 6 — Watch a pure capacity form (no room, no clash)

WHAT. Fully-associative, $C=2$ boxes, LRU. Stream 0, 1, 2, 0, 1, 2. Three distinct blocks, only two boxes.

WHY this is capacity not conflict. There is no mapping rule here — a block may sit anywhere — so "clash" is impossible by construction. Yet after the cache fills with {1,2}, requesting 0 misses because it was pushed out to make room. The working set (3 blocks) is bigger than the cache (2 boxes).

PICTURE. A 2-box LRU cache with a revolving door: each new block shoves out the oldest; the just-needed block is always the one that just left.

Access	Cache (LRU→MRU)	Result
0	[0]	Compulsory
1	[0,1]	Compulsory
2	[1,2]	Compulsory (evicts 0)
0	[2,0]	Capacity
1	[0,1]	Capacity
2	[1,2]	Capacity

Cure: a bigger cache ($\ge 3$ boxes) or a smaller working set. Associativity does nothing here.

---

Step 7 — The trap: a re-touch that looks like conflict but is capacity

WHAT. Direct-mapped, $S=2$, index $=B\mathrm{mod}2$. Stream 0, 1, 2, 0, 3, 0. Focus on access #4 (the second 0). It's not a first touch, and the real cache misses — tempting to stamp "conflict."

WHY you must simulate, not eyeball. Run the same stream on a fully-associative $C=2$ LRU cache: 0→[0], 1→[0,1], 2→[1,2] (0 evicted), then 0 → also a miss because 0 was already gone. Since the fully-associative cache also misses, access #4 is capacity, not conflict. Three distinct blocks {0,1,2} were live but only two boxes exist — that's a room problem, dressed up as a clash.

PICTURE. Two lanes running the identical stream: top = direct-mapped, bottom = fully-associative. Both light up red on access #4 → verdict: capacity.

---

Step 8 — Degenerate & limiting cases (so nothing surprises you)

WHAT / WHY / PICTURE, four corner cases lined up:

• Empty stream / single access. Every block appears once → all misses are compulsory; capacity and conflict are exactly zero. This is the floor: even a perfect infinite cache pays these.
• Working set fits entirely ($\text{distinct blocks}\le C$) in a fully-associative cache. Then $M_{\text{full}}=M_{\text{infinite}}$, so capacity $=0$; only compulsory (plus possibly conflict in the real cache) survive.
• Fully-associative real cache. No mapping rule ⇒ $M_{\text{real}}=M_{\text{full}}$ ⇒ conflict $\equiv 0$ by definition. A fully-associative cache cannot have conflict misses.
• Infinite real cache. Never evicts ⇒ $M_{\text{real}}=M_{\text{infinite}}$ ⇒ both capacity and conflict are zero; only compulsory remain.

Recall Corner-case quick check (cover the answers)

Fully-associative cache — how many conflict misses ever? ::: Zero, always. Infinite cache — which types survive? ::: Compulsory only. Distinct blocks $\le C$ in fully-assoc — capacity count? ::: Zero. A stream where every block is unique — the split? ::: 100% compulsory.

---

The one-picture summary

Everything on one canvas. A single request stream flows through the three imaginary caches; each cache filters out one cause; the leftover misses drain into three coloured buckets — orange compulsory, blue capacity, red conflict — with the subtraction identities written on the pipes between them.

Recall Feynman retelling (plain words)

Imagine three copies of the same shop. In the first shop the storeroom is infinite — the only time you can't sell something is the very first time a customer asks for a brand-new item you've never stocked. Those are compulsory misses. In the second shop the storeroom is small but you can put any item on any shelf — now you also fail when the storeroom simply isn't big enough for everything customers keep asking for. Those extra failures are capacity misses. In the third, real shop the storeroom is the same small size but each item has one assigned shelf — now two popular items forced onto the same shelf keep knocking each other off even though other shelves sit empty. Those further extra failures are conflict misses. Run the same day of customers through all three shops, count the failures in each, and subtract: the jump from shop 1 to shop 2 is your capacity problem, the jump from shop 2 to shop 3 is your shelving (mapping) problem, and whatever shop 1 already had is unavoidable coldness. Fix each with its own tool — bigger storeroom, or freer shelving, or ordering new stock before customers ask.