Tag, Index and Offset: How an Address Finds Its Line
A cache does not search. It slices the address into three fields — offset, index, tag — and each field's width is forced by the geometry rather than chosen. Once you can do the split, most cache behaviour stops being mysterious.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Three fields, derived rather than chosen
The widths are not design freedom; they fall out of two numbers. The offset must address every byte within a line, so it is log2(lineBytes) bits wide. The index must select one set, so it is log2(numSets) bits. Everything above them is the tag, stored in the cache next to the data so a hit can be distinguished from a different address that happens to share an index.
The number of sets is itself derived: numSets = capacity / (lineBytes × ways). So a single geometry — capacity, line size, associativity — determines the entire address split. Change the associativity while holding capacity and line size fixed and the index shrinks, the tag grows, and a completely different set of addresses starts colliding.
One consequence worth internalising immediately: the offset bits play no part in selecting a set. Every byte in a line shares one index and one tag, which is precisely why touching one byte brings in its neighbours and why Spatial Locality pays. The line, not the byte, is the unit the cache deals in (Memory Moves in Lines, Not Variables).
address bits: [ 63 ................ 12 | 11 ....... 6 | 5 ... 0 ]
TAG INDEX OFFSET
offset width = log2(line size)
index width = log2(number of sets)
tag width = address width - index - offset
number of sets = capacity / (line size x ways)
Only INDEX chooses the set.
Only TAG proves identity.
OFFSET never affects placement - it picks a byte inside the line.A worked split
Take a cache of 32 KiB capacity, 64-byte lines, 8-way set-associative — a plausible shape for a level close to the core, used here purely as an example. Line size gives a 6-bit offset. Sets come out at 32768 / (64 × 8) = 64, so the index is 6 bits. On a 64-bit address space the tag takes the remaining 52 bits.
Now the interesting part: which addresses collide? Two addresses share a set when their index bits match, and the index sits at bits [11:6]. That means addresses separated by any multiple of 2^12 = 4096 bytes land in the same set — the index and offset bits are identical and only the tag differs. Four kilobytes is a suspiciously familiar number, which is why array strides that are multiples of it are a classic way to manufacture conflicts.
Work through the three addresses below and the pattern that makes padding work becomes obvious. 0x1000 and 0x2000 share a set because they differ only above bit 11. Nudging the second by one line — 64 bytes — changes the index and separates them. That is the whole trick behind padding a matrix row to a non-power-of-two width.
| Address | Offset | Index (set) | Collides with previous? |
|---|---|---|---|
0x1000 | 0x00 (0) | 0x00 (set 0) | — |
0x1008 | 0x08 (8) | 0x00 (set 0) | Same line entirely — this is a hit |
0x1040 | 0x00 (0) | 0x01 (set 1) | No — next line, next set |
0x2000 | 0x00 (0) | 0x00 (set 0) | Yes — 4096 apart, index identical |
0x2040 | 0x00 (0) | 0x01 (set 1) | One line of padding moved it out of set 0 |
Why the index sits where it does
Putting the index immediately above the offset is deliberate: it means consecutive lines land in consecutive sets, so a sequential walk spreads itself evenly across the whole cache instead of hammering one set. Any other placement would make the common case — walking an array — behave badly.
The flip side is the stride sensitivity that follows directly. Because the index occupies a contiguous block of low-ish bits, any stride that is a multiple of numSets × lineBytes leaves those bits unchanged, and every access lands in one set. Power-of-two strides are exactly the ones that preserve low bit patterns, which is why they show up again and again in cache pathologies (Cache Thrashing: Load, Evict, Reload, Repeat).
Some designs mitigate this by hashing several address bits together to form the index rather than taking a raw slice, which scatters would-be conflicts. Whether a given cache does this is generally undocumented, so treat it as a reason not to over-fit layout tricks to a specific machine rather than as something to rely on.
set span = numSets x lineBytes = 64 x 64 = 4096 bytes
stride 4096: 0x1000 index 000000 set 0
0x2000 index 000000 set 0 <- same set
0x3000 index 000000 set 0 <- same set
... every access lands in set 0
after `ways` distinct lines, each one evicts the next
stride 4160: 0x1000 index 000000 set 0 (4096 + 64, one line of padding)
0x2040 index 000001 set 1
0x3080 index 000010 set 2
... walks across sets, all stay resident
The index sits directly above the offset so that consecutive lines
occupy consecutive sets - which is what makes a sequential walk
spread across the whole cache instead of hammering one set.
Caveat: some designs hash several address bits together to form the
index. Where they do, this arithmetic under-predicts how well the
cache copes, and the bad strides are not derivable from geometry.Key points
- Offset width is
log2(line size); index width islog2(number of sets); the tag is whatever remains. - Sets are derived:
capacity / (line size × ways)— so geometry alone fixes the whole split. - Offset bits never influence placement, which is exactly why a line is the unit of transfer.
- Addresses separated by
numSets × lineBytesshare a set — the arithmetic behind stride conflicts. - The index sits just above the offset so sequential access spreads across sets rather than piling into one.
Address → Tag, Index, Offset
Change an input and watch which number moves — and which one refuses to.
The index bits sit in the middle of the address, which is why addresses exactly 1024 bytes apart all land in the same set. That number — line size times set count — is the stride that thrashes a cache, and it is why a power-of-two array dimension can be pathologically slow.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Load → address: the effective address arrives as a plain integer.
- 2Address → offset: the low
log2(line)bits are set aside to pick a byte once the line is found. - 3Address → index: the next
log2(sets)bits select exactly one set, in constant time and with no search. - 4Set → tags: the stored tags of that set's ways are compared against the address's tag field.
- 5Match → data: the matching way supplies the line, and the offset selects the requested bytes within it.
- • "The tag identifies where the line goes" — the index does. The tag only confirms which of many possible addresses is present.
- • "Bigger cache means different collisions go away" — a larger cache usually means more sets, which changes which addresses collide rather than removing collisions.
- • "Offset bits matter for placement" — they cannot; every byte in a line shares one index by construction.
- • "I can compute exactly which addresses conflict on this CPU" — not if the design hashes the index, and whether it does is usually undocumented.
Consequences, controls and cost
- • Whether two addresses can coexist in cache is decided by a slice of their bits, not by how much cache is free.
- • Array strides that are multiples of the set span collapse onto one set and thrash regardless of capacity.
- • Padding an allocation by a single line can eliminate a conflict, because it perturbs the index field.
- • Everything within one line shares placement, so a single touch warms all of it — the basis of spatial locality.
- • Compute the set span for the geometry you care about (`sets × line size`) and avoid strides that are multiples of it.
- • Pad matrix rows and structure arrays to non-power-of-two widths when traversing them column-wise.
- • Keep fields accessed together within a line so one fill serves several accesses ([[aos-vs-soa]]).
- • Query the geometry at runtime rather than hard-coding it; the split changes between machines and levels.
- • Read the reported geometry for each level and compute the split by hand; the arithmetic takes a minute and settles most arguments.
- • Sweep stride across a synthetic traversal and look for miss spikes at multiples of the set span — that confirms raw-index behaviour.
- • If the expected spikes do not appear, suspect index hashing rather than assuming your arithmetic is wrong.
- • Verify a padding fix by miss count at the specific level, not by wall-clock alone, which mixes in unrelated effects.
- • Layout tuned to one geometry can be neutral or harmful on another, and the geometry is not part of any language contract.
- • Padding costs memory and can push a working set over a capacity threshold, trading a conflict miss for a capacity miss.
- • Reasoning at bit level is precise but brittle; access-pattern changes are usually more durable than address arithmetic.
Scope
§224 — what these claims are specific to.
- SIMPLIFIEDPresents the index as a raw slice of address bits. Some designs hash multiple bits together to scatter conflicts; where they do, which addresses collide is not derivable from the geometry alone.
- MICROARCH-SPECIFICCapacity, line size and associativity — and therefore the field widths — differ per cache level, vendor and generation.