Where is an address allowed to sit?
Guide 1 left us with a 64-byte cache line as the unit that moves between memory and cache, and a cache that is thousands of times smaller than the memory it stands in front of. That smallness forces a hard question this guide opens with: when a line arrives, which slot in the cache does it go into? Millions of addresses are competing for a few thousand slots, so the cache cannot just store anything anywhere and hope to find it again quickly. Associativity is the rule that answers this — it fixes which slots a given address is allowed to occupy, and it is the single design choice that decides whether a cache that is theoretically big enough actually behaves well.
Picture a coat-check at a theatre. The most rigid design gives every coat exactly one numbered hook, computed straight from your ticket number — a direct-mapped cache. Lookup is instant (check the one hook), but if two coats you wear all winter happen to map to the same hook, they evict each other forever, even while a hundred other hooks sit empty. The opposite extreme lets your coat hang on any free hook — a fully-associative cache. No coat is ever forced out by a mapping collision, but to find your coat the attendant must check every hook, which is far too slow to do on every memory access, so this is reserved for tiny structures. Real data caches live in the sensible middle.
That middle is the set-associative cache, and it is what almost every L1, L2 and L3 actually is. The cache is divided into sets; each address maps to exactly one set (so lookup checks only that set, staying fast), but within the set the line may sit in any of N ways — hence an N-way set-associative cache, commonly 4-, 8- or 16-way. It is the coat-check where your ticket sends you to one specific row of hooks, and your coat may hang on any hook in that row. You get most of the collision-resistance of full associativity at a tiny fraction of the lookup cost. The whole topic of cache associativity is really just naming the point you pick on this spectrum from one way to all ways.
How the hardware actually places a line
Here is the mechanism, and it is wonderfully concrete. To place or find a line, the hardware chops the address into three fields. The lowest bits are the offset — which byte inside the 64-byte line (a 64-byte line needs 6 bits, since 2^6 = 64). The next bits are the index — which set this address belongs to. The remaining high bits are the tag, which is stored next to the line in the cache so the hardware can confirm which of the many addresses that share this set's index is actually present. No division, no search across the whole cache: a couple of bit extractions pick the set, then the few tags in that set are compared in parallel.
address = [ tag | index | offset ] (one 64-bit address)
high mid low
Example: 32 KiB, 8-way, 64-byte lines
sets = 32768 / 64 / 8 = 64 sets
offset = low 6 bits (byte within the 64-byte line, 2^6 = 64)
index = next 6 bits (selects 1 of 64 sets, 2^6 = 64)
tag = remaining high bits
0x10000 -> offset 0, index 0, tag ...01
0x20000 -> offset 0, index 0, tag ...10
same index -> both fall in set 0 -> they compete for its 8 waysNow the danger becomes visible. Because the index is a fixed slice of middle address bits, addresses spaced apart by exactly the set stride share an index and so fight inside one set. The classic trap is striding through memory by a power of two: if you walk an array touching one element every 4096 bytes, and 4096 happens to be a multiple of (number of sets x line size), then every touched address maps to the same set, and you thrash an 8-way set while the other 63 sets sit empty. This is why an array stride of 1024 can run dramatically slower than a stride of 1023 — the off-by-one breaks the power-of-two aliasing and spreads the addresses across sets again. The cache was big enough the whole time; the placement rule defeated you.
Three reasons a line is not where you wanted it
A cache miss is just the moment the CPU asks for data the cache it checked does not hold, so it must go to a slower level and stall while it waits. But not all misses have the same cause, and since each cause has a different cure, a famous classification — the three C's — sorts them by root cause. Knowing which C dominates your hot loop tells you precisely what to change instead of guessing. This is the substance of the three C's of cache misses, and it is the bridge from understanding the hardware to actually making code faster.
- Compulsory (cold) miss — the first-ever touch of a line. The data has simply never been loaded, so of course it is absent. Nothing prevents the very first access, but hardware prefetching can hide its latency by issuing it early, before you ask.
- Capacity miss — your working set (all the data you are actively reusing) is simply bigger than the cache, so older lines get evicted before you loop back to them, even in an ideal fully-associative cache. The cure is to shrink the working set: process data in cache-sized tiles or blocks.
- Conflict miss — lines that WOULD have fit in the cache nonetheless evict each other because they map to the same set under the cache's limited associativity. This is the power-of-two-stride trap from the last section. The cure is to change layout or stride so addresses spread across more sets, or to lean on higher associativity.
The practical workflow falls right out of this. Measure your miss rate with hardware performance counters, then reason about which C dominates from the access pattern — because a real counter reports only the total miss rate, not which C it was; the three C's are a model for thinking, not a hardware-reported breakdown. Compulsory-heavy code wants prefetching. Capacity-heavy code wants blocking and smaller data (the textbook example is tiling a matrix multiply into B-by-B blocks that fit in L1, turning streaming capacity misses into reuse hits). Conflict-heavy code wants padding and stride changes. Diagnose the cause and the fix names itself.
What happens when you write?
We have been talking about reads. Writing raises its own pair of questions, and the answers — the cache write policy — explain real performance behavior even though you rarely choose them yourself. The first question is when to push a change down to memory. A write-through cache forwards every write to the next level immediately: memory is always current, but the write traffic is heavy. A write-back cache — what nearly every modern L1, L2 and L3 uses — instead updates only the cached line and marks it dirty, writing it down to memory lazily, only when the line is evicted. That collapses many writes to the same line into one eventual memory write, which is exactly why write-back is the performance default.
The second question is what to do when you write an address that is not even cached yet. A write-allocate policy first pulls the line into cache (so this write, and the nearby future writes it expects, become fast cache writes); a no-write-allocate policy writes straight past to memory without caching. The common pairing — the one you can assume unless told otherwise — is write-back with write-allocate. Two real consequences follow. First, because write-back caches hold dirty data, DRAM can lag behind what the CPU has actually computed until eviction, which is why memory-mapped device registers and DMA buffers must be handled carefully (often marked uncacheable or flushed explicitly). Second, write-allocate is wasteful when you write a fresh buffer you will never read back: the hardware dutifully loads each line's old contents just to overwrite them — which is precisely why non-temporal (streaming) store instructions exist, to bypass the cache when you know you will not read the data back soon.
Many caches, one truth: the MESI protocol
Everything so far assumed one cache. But each core has its own L1 (and usually L2), so the same memory line can be copied into several caches at once. Picture four colleagues each holding a photocopy of one spreadsheet: the instant one of them edits a cell, every other copy is silently wrong. The job of a cache-coherence protocol is the bookkeeping that prevents this — it guarantees no core ever reads a stale copy of a line after another core has changed it. MESI is the classic protocol that does this, and its name is simply the four states a cached line can be in.
Each line in each cache carries one of four states. Modified (M): this core holds the only copy and it has been changed (dirty); memory is stale, and this core must write it back before anyone else may read it. Exclusive (E): this core holds the only copy and it matches memory (clean); it can be written silently, sliding straight to M with no message to anyone. Shared (S): this core holds a clean copy and other cores may hold clean copies too; reading is free, but writing first requires invalidating the others. Invalid (I): this entry is empty or out of date and must be refetched. The cores talk over an interconnect: to write a line that others hold in S, a core broadcasts an invalidate and waits for the others to drop their copies to I — only then may it move the line to M and write. Reading a line another core holds in M forces that core to write back and downgrade. (Variants tune this: MESIF adds a Forward state so one sharer answers requests; MOESI adds an Owned state so a dirty line can be shared without first writing it back.) This is the full shape of the MESI coherence protocol.
This protocol is the hidden machinery behind two costs every concurrent programmer eventually meets. The first is false sharing: two cores writing two different variables that happen to share one 64-byte line keep bouncing that line between their M states, each invalidating the other on the interconnect — even though they never touch the same byte. A clean-looking loop is silently serialized into invalidate-and-refetch, and you can see a hundredfold slowdown from coherence traffic alone. The fix is to pad the variables onto separate lines (one per 64 bytes) so the two cores stop fighting. The second cost is the atomic read-modify-write: by definition it must acquire the line in an exclusive-like state so no other core can interleave, which is why an uncontended atomic is cheap but a heavily-contended one serializes on coherence — every core queues to own the same line. The line, once again, is the unit of contention.