Cache miss types (compulsory, capacity, conflict)

Setup: what is a cache and what is a "miss"?

WHAT we want to measure: for a given program's access sequence, how many misses happen and why.

The 3 C's — precise definitions

Intuition The three reference caches (WHY this works)

The trick is to compare against idealized caches:

Infinite cache → only compulsory misses survive.
Fully-associative, finite → compulsory + capacity survive.
Real cache → compulsory + capacity + conflict.

So by subtraction: $\text{Conflict} = \text{Misses}_{\text{real}} - \text{Misses}_{\text{full-assoc}}$ $\text{Capacity} = \text{Misses}_{\text{full-assoc}} - \text{Misses}_{\text{infinite}}$ $\text{Compulsory} = \text{Misses}_{\text{infinite}}$ Why this step? Each idealized cache removes exactly one cause of miss, so the differences isolate each cause cleanly.

Figure — Cache miss types (compulsory, capacity, conflict)

Deriving the classification from first principles

HOW do we decide a real miss's type? Simulate the same access trace on all three model caches.

Formula Total miss decomposition

$M_{\text{total}} = M_{\text{compulsory}} + M_{\text{capacity}} + M_{\text{conflict}}$ Derivation (not a memorized formula):

Start: every real miss is one of the three by construction (the question-chain above is exhaustive and mutually exclusive).
$M_{\text{compulsory}}$ = number of distinct blocks touched (each unique block must be fetched once).
$M_{\text{full}}$ = misses of a fully-assoc LRU cache of size $C$ ⇒ $M_{\text{capacity}} = M_{\text{full}} - M_{\text{compulsory}}$ .
$M_{\text{conflict}} = M_{\text{total}} - M_{\text{full}}$ .

Worked Example 1 — direct-mapped conflict

Cache: direct-mapped, 4 lines (block = 1 word for simplicity, so $S=4$ ). Access sequence of block numbers: 0, 4, 0, 4, 0, 4.

Index $= B \bmod 4$ : block 0 → set 0; block 4 → $4\bmod4=0$ → also set 0.

Access	State before	Result	Why
0	empty	Compulsory miss	first ever touch of 0
4	{0}	Compulsory miss	first ever touch of 4 (evicts 0)
0	{4}	Conflict miss	0 seen before ⇒ not cold; only 2 blocks used ⇒ fits in fully-assoc ⇒ conflict
4	{0}	Conflict miss	same reasoning
0	{4}	Conflict miss	thrashing continues
4	{0}	Conflict miss	thrashing continues

Result: 2 compulsory + 4 conflict + 0 capacity. Fix: just 2-way associativity makes both blocks live together in set 0 → all later accesses hit. Conflict misses vanish without enlarging the cache.

Worked Example 2 — capacity miss

Cache: fully-associative, 2 lines, LRU. Sequence: 0, 1, 2, 0, 1, 2.

Access	Cache (LRU→MRU)	Result	Why
0	[0]	Compulsory	first touch
1	[0,1]	Compulsory	first touch
2	[1,2]	Compulsory (evicts 0)	first touch of 2
0	[2,0]	Capacity	0 seen before, but fully-assoc still missed ⇒ cache too small (3 blocks, 2 slots)
1	[0,1]	Capacity	same
2	[1,2]	Capacity	same

Result: 3 compulsory + 3 capacity + 0 conflict. Why not conflict? The cache is fully-associative, so there is no mapping restriction — nothing to fix with associativity. The only cure is a bigger cache (≥3 lines) or a smaller working set.

Worked Example 3 — all three in one trace

Direct-mapped, 2 lines ( $S=2$ , index $=B\bmod2$ ). Sequence: 0, 1, 2, 0, 3, 0.

Access	Index	State	Result	Why this step?
0	0	—	Compulsory	first touch
1	1	{0,1}	Compulsory	first touch
2	0	{2,1}	Compulsory	first touch (evicts 0, both map to set 0)
0	0	{0,1}	Conflict	0 seen before; only blocks {0,1,2} used, would fit in a 2-line fully-assoc? No — 3 blocks > 2 lines... check carefully
3	1	{0,3}	Compulsory	first touch (evicts 1)
0	0	{0,3}	Hit	0 still in set 0

For access #4 we must test fully-assoc size 2: sequence 0,1,2,0… — a 2-line fully-assoc LRU would have {1,2} when 0 is re-requested ⇒ it also misses. So access #4 is actually a capacity miss, not conflict! This shows the classification requires simulating the reference cache, not eyeballing. (This subtle case is exactly why we define types by comparison, not intuition.)

Common mistakes (Steel-man + fix)

Active recall

Recall Forecast then verify (cover the answers!)

Which miss type survives in an infinite cache? → Compulsory only.
Which cure fixes conflict but NOT capacity? → Higher associativity.
Sequence 0,4,0,4 in a direct-mapped 4-line cache ( $4\bmod4=0$ ): how many conflict misses? → 2 (after the 2 compulsory ones).
Formula for conflict count? → $M_{\text{real}} - M_{\text{full-assoc}}$ .
Does a fully-associative cache ever have conflict misses? → No, by definition.

Recall Feynman: explain to a 12-year-old

Imagine a small bookshelf (the cache) and a huge library (memory).

Compulsory: the first time you ever need a book, it's never on your shelf — you must walk to the library. Nobody could avoid that.
Capacity: your shelf holds 3 books but you keep switching between 4. Something always gets pushed off. Only a bigger shelf helps.
Conflict: you have plenty of shelf space, but a silly rule says "the red book and the blue book must go on the same single spot." They keep kicking each other off even though other spots are empty. Change the rule (allow more spots) and the problem disappears.

80/20 — the essential takeaways

Classify by comparison to idealized caches (infinite → full-assoc → real).
Cause ⇒ cure: compulsory→prefetch/bigger blocks; capacity→bigger cache; conflict→more associativity.
Conflict $=$ real misses $-$ fully-associative misses; if that's 0, associativity won't help.

Connections

Cache Associativity & Set Mapping
LRU and Replacement Policies
Spatial and Temporal Locality
Cache Block Size Trade-offs
Average Memory Access Time (AMAT)
Working Set & Program Behavior
Prefetching

The 3 C's model classifies cache misses into which three types?

Compulsory (cold), Capacity, Conflict.

What is a compulsory miss?

The first-ever reference to a block; it misses even in an infinite cache.

What is a capacity miss?

A miss that would also occur in a fully-associative cache of the same size — the working set exceeds cache capacity.

What is a conflict miss?

A miss that would have HIT in a fully-associative cache of equal size but missed because limited associativity forced eviction.

Which idealized cache leaves only compulsory misses?

An infinite cache.

How do you compute the number of conflict misses?

Misses(real cache) − Misses(fully-associative cache of same size).

How do you compute capacity misses?

Misses(fully-associative same size) − Misses(infinite cache).

Cure for conflict misses?

Increase associativity (or victim cache / better indexing).

Cure for capacity misses?

Increase total cache size or reduce the working set.

Cure for compulsory misses?

Prefetching or larger block size (spatial locality).

In a direct-mapped cache with S sets, which set does block B map to?

index = B mod S.

Does a fully-associative cache ever suffer conflict misses?

No — with no mapping restriction, conflict misses are zero by definition.

Why can larger blocks hurt?

Fewer blocks fit, increasing capacity and conflict misses and wasting bandwidth.

Sequence 0,4,0,4 on a direct-mapped 4-line cache (4 mod 4 = 0): miss breakdown?

2 compulsory then 2 conflict (both map to set 0 and thrash).

Why can't associativity fix a capacity miss?

Capacity misses occur even with full associativity; the problem is total size, not mapping.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, cache ek chhoti fast memory hai jo bade slow RAM ke saamne rehti hai. Jab bhi CPU ko data chahiye aur wo cache mein nahi milta, us ko miss bolte hain. Ab har miss ka reason alag hota hai, aur reason ke hisaab se hi uska ilaaj alag hota hai — isiliye engineers ne 3 C's banaye: Compulsory, Capacity, Conflict.

Compulsory (Cold) matlab data ko pehli baar hi touch kiya ja raha hai — obviously wo cache mein hoga hi nahi, chahe cache kitni bhi badi ho. Isko sirf prefetching ya bade block se thoda kam kar sakte ho. Capacity (Crowded) tab hota hai jab tumhara kaam ka data (working set) cache se bada hai — cheezein baar-baar bahar phenki jaati hain kyunki jagah hi kam hai. Iska ilaaj sirf ek: badi cache. Yahan associativity badhane ka koi faayda nahi.

Conflict (Collision) sabse interesting hai: cache mein jagah khaali padi hai, par mapping rule (index = block mod number-of-sets) do blocks ko same slot pe zabardasti bhej deta hai, to wo ek dusre ko thoda-thoda kick karte rehte hain (thrashing). Iska simple ilaaj: associativity badhao (2-way, 4-way), taaki ek set mein zyada blocks reh sakein — cache ka size badhaaye bina hi problem khatam.

Yaad rakhne ka smart tarika: kisi miss ko classify karne ke liye compare karo — infinite cache (sirf compulsory bachega), phir fully-associative same size (compulsory + capacity), phir real cache (teenon). Subtract karke har type nikal jaata hai. Yeh soch exam aur real design dono mein kaam aati hai kyunki cause pata chalte hi cure clear ho jaata hai.

Cache miss types (compulsory, capacity, conflict)

Setup: what is a cache and what is a "miss"?

The 3 C's — precise definitions

Deriving the classification from first principles

Worked Example 1 — direct-mapped conflict

Worked Example 2 — capacity miss

Worked Example 3 — all three in one trace

Common mistakes (Steel-man + fix)

Active recall

80/20 — the essential takeaways

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Memory Hierarchy & Caches

Connections