The lookup problem: where could a byte be hiding?
The previous guides earned us the idea that a small, fast cache near the processor pays off because programs reuse the same addresses (temporal locality) and touch neighbours soon after (spatial locality). That is the why. This guide is the how: when the CPU asks for the byte at some address, the cache must answer one question astonishingly fast — 'do I already have it, yes or no?' Get that answer in a cycle or two and you score a hit; get it wrong and you pay the miss penalty by trudging to the next level. The whole art of cache organization is making that yes-or-no decision cheap.
Think of the cache as a small desk beside you, holding photocopies of pages from a huge library down the hall. The naive plan — search every slot on the desk for the page you want — would be far too slow if the desk held even a few hundred slots, because you would compare your address against all of them at once. The clever plan is to give every library page a fixed home on the desk, so you only ever look in one place (or a small handful of places). That single design choice — how an address maps to a slot — is what separates the three classic cache organizations we are about to meet.
Splitting the address: tag, index, offset
Here is the key trick. A cache stores data in chunks called cache lines (or blocks) — not one byte but a whole run of neighbouring bytes, say 64 of them, because spatial locality says if you touch one you will likely want its neighbours. So the cache reads in fixed-size lines, and every address gets carved into three fields by simply slicing its bits. The low bits pick a byte within a line (the offset); the middle bits pick which slot the line lives in (the index); and the high bits are kept as a tag that records which of the many library pages that map to this slot is actually parked here right now. This is the tag/index/offset split, and it is the heart of every cache.
Let us do it concretely. Take a 32-bit address feeding a cache with 64-byte lines and 64 sets. Sixty-four bytes need 6 bits to address a byte inside a line (since 2^6 = 64), so the bottom 6 bits are the offset. Sixty-four sets need 6 bits to pick a set (2^6 = 64 again), so the next 6 bits are the index. That uses 12 bits; the remaining 32 - 6 - 6 = 20 high bits are the tag. The beauty is that this slicing is free — no arithmetic, just looking at different bit ranges of the same address, which hardware does with bare wires.
32-bit address, 64-byte lines, 64 sets:
31 12 11 6 5 0
+-------------------------+-----------+-----------+
| TAG (20) | INDEX (6) | OFFSET(6) |
+-------------------------+-----------+-----------+
| | |
| | +--> which byte in the line (0..63)
| +---------------> which set to look in (0..63)
+---------------------------------------> compare against stored tag(s)
Example: address 0x0001_2A40
binary = 0000 0000 0000 0001 0010 1010 0100 0000
offset = bits[5:0] = 000000 -> byte 0 of the line
index = bits[11:6] = 101001 -> set 41
tag = bits[31:12] = 0x00012 -> stored & comparedThree layouts: one home, a few homes, or anywhere
The simplest layout is the direct-mapped cache: every memory line has exactly one slot it is allowed to occupy, chosen by its index bits. Lookup is a dream — go straight to that one set, read its stored tag, compare it against your address's tag, and if they match (and the line is valid) it is a hit. One comparison, no searching. The catch is collisions: because many addresses share the same index, two hot lines that happen to map to the same slot keep evicting each other even while the rest of the cache sits empty. It is like a coat-check where your ticket number forces you into one specific hook — fast to find, but useless if a friend's coat already hangs there.
The fix is the set-associative cache: give each index not one slot but a small group of slots — say four — called a set, and let a line live in any slot within its set. A four-way cache means each set has four 'ways'. Now the index still picks the set in one step, but inside the set you compare your tag against all four stored tags in parallel (four small comparators running at once), and a hit is declared if any one matches. Our two colliding hot lines can now coexist in the same set, peacefully, in different ways. The price is more hardware: more comparators and a multiplexer to select the matching way's data.
At the far extreme is the fully associative cache: there is no index at all, so a line may live in any slot. Lookup must compare your tag against every stored tag at once — maximum flexibility, zero collisions of the index kind, but ruinously expensive comparators if the cache is large, so it is reserved for small structures (a TLB, which we meet later, is often fully associative). Notice the unifying view: direct-mapped is just one-way set-associative, and fully associative is set-associative with a single set holding everything. Associativity is one dial running from 'one home' to 'anywhere', trading hardware cost for fewer of the conflict misses we will catalogue next.
Walking one lookup, and choosing what to evict
Let us trace a single load through a four-way set-associative cache, using our 64-byte lines and 64 sets. The CPU asks for the byte at some address; the cache must decide hit or miss and, on a miss, decide which existing line to throw out to make room. Watch how the three address fields do their three jobs in turn.
- Index in: take the middle 6 bits as the index and go straight to that one set — say set 41. This selects four ways' worth of stored tags and valid bits, all read out together.
- Compare tags: line up your address's 20-bit tag against all four stored tags at once, with four comparators. A way matches only if its tag equals yours and its valid bit is set.
- Hit path: if exactly one way matches, it is a hit. A multiplexer selects that way's 64-byte line, and the offset bits pick the requested byte out of the line. The whole thing finished in a couple of cycles — no trip down the hierarchy.
- Miss path: if no way matches it is a miss, so fetch the whole line from the next level and install it into one of the four ways of set 41. If all four ways are already full, a replacement policy must choose a victim to evict first.
That last step is the replacement policy, and it only exists when there is a choice — a direct-mapped cache has no choice, since each line has exactly one home. The classic policy is LRU, least recently used: evict whichever line in the set has gone untouched the longest, betting on temporal locality (a line used recently is likely to be used again soon). True LRU is expensive to track for many ways, so real caches often approximate it — a 'pseudo-LRU' tree of bits, or even just random replacement, which is cheaper and surprisingly competitive at high associativity. The honest point is that no policy is clairvoyant: the theoretical optimum would evict the line used furthest in the future, but a real cache cannot see the future, so it guesses from the past.
Why the layout matters to your code
All this hardware bookkeeping is invisible to a program — and that is exactly the trap. Two loops can produce identical results yet differ many times over in speed, purely because one respects the cache layout and the other fights it. Suppose you stride through memory hitting addresses that all share the same index bits (a power-of-two stride is the classic offender): in a direct-mapped or low-associativity cache they all land in the same set and evict each other endlessly, a parade of misses even though the cache as a whole is mostly empty. This is the conflict miss, one of the three C's the next guide will name, and it is born directly from the index field of the tag/index/offset split.
The line size matters just as much. Because the cache always loads a whole line, data laid out so that neighbours are used together gets carried in for free — touch one byte and its 63 line-mates ride along, so the next accesses are hits. This is why walking a 2D array along the direction it is stored in memory (row by row, if rows are contiguous) flies, while walking it across that grain — jumping a full row between each access — wastes most of every line it drags in and crawls. Same data, same result, wildly different miss counts. Higher associativity and larger lines and bigger caches all push misses down, but only locality-aware code lets you collect the reward.