Cache lines, tags, index, offset: Visual walkthrough

We start from the most basic fact imaginable: memory is a row of numbered boxes. Everything else grows out of that.

Step 1 — What an address even is

WHAT. Picture main memory as one enormously long row of little boxes, each holding exactly one byte (8 bits). Every box has a number painted on it: box $0$ , box $1$ , box $2$ , … That painted number is the address. "Byte-addressable" just means each byte has its own address.

WHY. Before we can slice an address we must agree on what it counts. It counts bytes from the start of memory. Nothing more mystical than a house number on a very long street.

PICTURE. Below, the row of boxes with their addresses written underneath. If the address has $n$ bits, the biggest number we can write is $2^{n} - 1$ , so there are $2^{n}$ boxes total.

Figure — Cache lines, tags, index, offset

Step 2 — Group boxes into lines (blocks)

WHAT. We never move one byte between memory and cache — we move a whole line: a fixed run of $B$ neighbouring bytes. So mentally draw fences every $B$ boxes. Each fenced group is one line.

WHY. Because of spatial locality (Spatial and temporal locality): touch one byte and you will likely touch its neighbours soon, so hauling the whole neighbourhood at once pays off. Fences at regular intervals of $B$ mean the first line is bytes $0 \dots B - 1$ , the next is $B \dots 2 B - 1$ , etc.

PICTURE. Same row, now with red fences every $B = 4$ boxes (we use $B = 4$ in pictures so it fits; real hardware uses $B = 64$ ). Each line gets a line number written above it.

Step 3 — The offset field falls out of that remainder

WHAT. The remainder $A mod B$ names the byte inside the line. It ranges over $0, 1, \dots, B - 1$ — exactly $B$ values. To write a number that goes from $0$ to $B - 1$ in binary you need $lo g_{2} B$ bits. Those are the offset bits.

WHY THIS TOOL — why $lo g_{2}$ and not something else? $lo g_{2} B$ answers one precise question: "how many binary digits do I need to count $B$ different things?" One bit counts 2 things, two bits count 4, three bits count 8… $k$ bits count $2^{k}$ . Turn that around: to count $B$ things you need $k = lo g_{2} B$ bits. That is the whole reason $lo g_{2}$ appears everywhere on this page — it converts "how many items" into "how many bits."

PICTURE. Zoom into one line of $B = 4$ bytes. Under each byte we write its 2-bit offset ( $00, 01, 10, 11$ ). Notice: the offset is simply the low bits of the address, because dividing a binary number by $B = 2^{k}$ just chops off its lowest $k$ bits — and the chopped-off part is the remainder.

WHAT. The cache is a tiny shelf of $S$ sets (rows), numbered $0 \dots S - 1$ . Memory has far more lines than the shelf has sets, so we must decide: line number $\to$ which set? The rule is take the low bits of the line number: $set = (line number) mod S$ .

WHY the low bits, not the high bits? Watch what each choice does to a contiguous array (lines $0, 1, 2, 3, \dots$ ):

Low bits → set $= 0, 1, 2, 3, 0, 1, 2, 3, \dots$ — neighbours fan out across all sets. Good.
High bits → the first many lines all share the same low-changing pattern and pile into one set, evicting each other endlessly ("thrashing"). Bad.

So we pick low bits precisely to scatter neighbours. (More on what happens inside a set in Cache associativity & replacement policies.)

PICTURE. Left: memory's many line numbers, colour-coded by which set they land in. Right: the short cache shelf of $S = 4$ sets. Coloured arrows show low-bit lines fanning across sets; a greyed-out "high-bit" arrow bundle shows the bad alternative collapsing into one set.

Step 5 — The leftover bits become the tag

WHAT. Many line numbers share a set (that's the whole reason we needed a cache). So when we look in set $s$ , we must confirm the line sitting there is the one we asked for. The bits left over — everything above the index — are unique among all lines that map to the same set. Store them; on a lookup, compare them. Those are the tag bits.

WHY store only the leftover, not the whole address? The index already told us the row (no need to re-store it — it's implied by where the line sits). The offset picks a byte inside the fetched line (not part of identity). So only the top slice distinguishes the competing lines. Storing fewer bits saves silicon (Memory hierarchy and latency numbers cares about every transistor).

PICTURE. One set drawn as a slot holding: a valid bit, a stored tag, and the line's data bytes. An incoming address's tag field flows into a comparator ( $= ?$ ); green = hit, red = miss.

Step 6 — Slice a real address, watching the boundaries

WHAT. Take 0xDEADBEEF, a 32-bit address, on a cache with $B = 64$ ( $lo g_{2} 64 = 6$ offset bits) and $S = 256$ sets ( $lo g_{2} 256 = 8$ index bits). We peel the low 6 (offset), then the next 8 (index), then the rest is tag.

WHY the warning. Hex digits are 4-bit chunks, but $6$ and $8$ are not multiples of 4, so the fields do not line up with hex digits. You must think in bits, not nibbles.

PICTURE. The 32-bit string with two knives cutting at bit 6 and bit 14. The low 14 bits read 11 1110 1110 1111.

Offset = low 6 bits $=$ 101111 $=$ 0x2F $=$ byte 47 in the line.
Index = next 8 bits (bits 13..6) $=$ 11111011 $=$ 0xFB $=$ set 251.
Tag = top 18 bits, stored & compared in set 251.

Step 7 — The degenerate cases (never let the reader hit an unshown one)

WHAT & WHY & PICTURE — three extremes, all consistent with Step 5:

Fully associative ( $S = 1$ ). Index width $= lo g_{2} 1 = 0$ — no index bits at all. Any line may sit in any slot, so we compare the tag of every slot. Address $= [TAG ∣ OFFSET]$ .
Direct-mapped ( $S = L$ , one line per set). Maximum index bits, minimum tag bits. Each line has exactly one home slot; no choice, no search — fastest lookup, most collisions.
Line of one byte ( $B = 1$ ). Offset $= lo g_{2} 1 = 0$ — no offset bits. Then $[TAG ∣ INDEX]$ addresses bytes directly. Real caches never do this (kills spatial locality) but the formula still holds — a good sanity check that $lo g_{2} 1 = 0$ makes the field vanish.

The one-picture summary

One picture, whole derivation: the address on top, two cuts at $lo g_{2} B$ and $lo g_{2} B + lo g_{2} S$ , three arrows into three jobs — TAG "is it the right block?" → comparator; INDEX "which set?" → row selector; OFFSET "which byte?" → byte picker inside the fetched line.

Recall Feynman: the whole walkthrough in plain words

Memory is a mile-long row of numbered boxes; the address is the box number (Step 1). We fence the boxes into packs of $B$ — that's a line — because grabbing one box means we'll want its neighbours (Step 2). The bottom few bits of the address say which box inside the pack — the offset — and there are $B$ boxes so we need $lo g_{2} B$ bits (Step 3). Our little shelf only has $S$ cubbies, so the next bits pick which cubby — the index — and we deliberately use the low bits so neighbouring packs scatter instead of fighting over one cubby (Step 4). Whatever bits are left on top get written on a sticky note in the cubby — the tag — so later we can check the pack sitting there is really ours (Step 5). Then we practised on 0xDEADBEEF, being careful that $6$ -bit and $8$ -bit fields don't line up with hex digits (Step 6). Finally the extremes: no cubby choices at all (fully associative, zero index), one cubby per pack (direct-mapped, max index), and one-box packs (zero offset) — all still obeying $tag + index + offset = n$ (Step 7).

Recall Self-check clozes

The field that depends only on line size $B$ is the offset, width == $lo g_{2} B$ . The field that picks the row is the index, width $lo g_{2} S$ . The leftover top bits stored & compared are the tag, width $n - lo g_{2} S - lo g_{2} B$ ==. For 0xDEADBEEF with 6 offset + 8 index bits: offset ::: 0x2F (byte 47), set ::: 0xFB = 251.

Related building blocks: Spatial and temporal locality · Cache associativity & replacement policies · Memory hierarchy and latency numbers · Virtual vs physical addressing (VIPT/PIPT) · TLB and page tables · Cache coherence (MESI).