Direct-Mapped Caches: One Address, One Home
The simplest way to build a cache: every memory address has exactly one line it is allowed to occupy. Lookup becomes trivial and the hardware stays cheap — but two hot addresses that happen to share an index evict each other forever, while the rest of the cache sits empty.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
The index picks the line, and nothing else gets a vote
A direct-mapped cache is a plain array of lines. To find where an address belongs, the hardware takes a slice of bits out of the middle of the address — the index — and uses it directly as the array subscript. There is no search and no choice: address A lives at line index(A) or it is not cached at all.
That is the entire appeal. A lookup is one array read plus one tag comparison, which is about as little work as a cache can do, and it can be done fast enough to sit in a tight load path. No candidate selection, no arbitration between ways, no replacement decision to make on a miss — the incoming line simply overwrites whatever was at that index.
The cost is equally direct. Two addresses whose index bits match are permanently in competition, and the hardware has no way to keep both. Memory is vastly larger than the cache, so this is not an edge case: an enormous number of addresses share every index. It only *matters* when two of them are hot at the same time — which is exactly what a loop over two arrays arranges.
| Address | Index bits | Cache line | Shares a line with |
|---|---|---|---|
0x0000 | 000 | line 0 | 0x0200, 0x0400, 0x0600, … |
0x0040 | 001 | line 1 | 0x0240, 0x0440, … |
0x0080 | 010 | line 2 | 0x0280, 0x0480, … |
0x0200 | 000 | line 0 | 0x0000 — collides with the first row |
0x0400 | 000 | line 0 | 0x0000, 0x0200 — three-way pile-up |
Free capacity does not help a conflict
The uncomfortable property of a direct-mapped cache is that a miss can happen while most of the cache is idle. The two loops below do the same arithmetic over the same amount of data. The first allocates the arrays a power-of-two distance apart, so element i of each maps to the same index; every iteration touches both, and every touch evicts the other. The second nudges one array along by a single line and the collisions disappear.
Nothing about the *quantity* of data changed. The working set was small enough to fit either way. What changed is the arithmetic relationship between two base addresses — a property no reader of the source could see, and one that an allocator, a linker, or a different compiler version might change underneath you.
This is what a conflict miss is: a miss that would not have occurred in a fully associative cache of the same capacity. It is the third category in Three Kinds of Miss, Three Different Fixes, and it is the only one that organisation — rather than size or access order — can fix.
1a = alloc(N * 8) // base 0x1000002b = alloc(N * 8) // base 0x110000 ← exactly 64 KiB later3 4for i in 0 .. N-1:5 sum += a[i] * b[i] // a[i] and b[i] share an index6 // each load evicts the other7 // ~2 misses per iteration, forever1a = alloc(N * 8) // base 0x1000002pad = alloc(64) // shove b along by one line3b = alloc(N * 8) // base 0x1100404 5for i in 0 .. N-1:6 sum += a[i] * b[i] // different indices now7 // both stay resident8 // misses only when a new line is neededThe fix is not more cache and not less data — it is changing the numeric distance between two base addresses so their index bits stop matching. That is a genuinely strange thing for program performance to depend on, and it is the reason essentially every modern cache is set-associative instead.
Why build one at all
Given that failure mode, direct-mapped caches look indefensible — but they are not extinct, and understanding why explains the whole design space. What they buy is the shortest possible hit path: no way-selection multiplexer, no parallel tag comparison, no replacement state to read or update. In a structure where hit latency is on the critical path of every single load, shaving a gate delay is worth real money.
So the historical pattern is that direct-mapped organisation shows up where lookups must be as cheap as possible and conflicts are tolerable — some older L1 designs, and some small auxiliary structures. As transistor budgets grew, the calculus shifted: comparators became cheap relative to the cost of a miss, and the industry moved to Set-Associative Caches: The Compromise That Won designs almost everywhere in the data path.
Read direct-mapped as one end of a spectrum rather than a design anyone would choose today. One way is cheapest to look up and worst at conflicts; fully associative is the opposite; the useful designs sit in between, and Set-Associative Caches: The Compromise That Won is the lesson about that middle.
| Property | Direct-mapped | Fully associative |
|---|---|---|
| Places a block may live | Exactly one | Anywhere |
| Tag comparisons per lookup | One | One per line |
| Replacement decision | None — overwrite the index | Choose a victim from all lines |
| Conflict misses | Common, and address-dependent | None by construction |
| Hit-path complexity | Minimal | Substantial |
| Where it fits | Small structures where lookup cost dominates | Very small structures where conflicts are intolerable |
Key points
- A direct-mapped cache assigns each address exactly one legal line, chosen by index bits taken from the address itself.
- Lookup is as cheap as a cache lookup can be: one array read, one tag comparison, no replacement decision.
- Two hot addresses sharing an index evict each other indefinitely, even when most of the cache is empty.
- That is a conflict miss — the only miss category that cache *organisation*, rather than size or access order, can remove.
- Direct-mapped is one end of the associativity spectrum, not a design modern data caches choose.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Load instruction → address generation: the effective address is computed and handed to the cache.
- 2Address → index extraction: a fixed slice of bits selects exactly one line; no other line is examined.
- 3Line → tag comparison: the stored tag is compared with the address's tag bits; equal means hit, otherwise miss.
- 4Miss → fill: the incoming line unconditionally overwrites whatever occupied that index, because there is nowhere else to put it.
- 5Evicted line → next access: if the displaced address is touched again, it misses and evicts the newcomer in turn.
- • "The data fits in cache, so it is cached" — capacity is necessary, not sufficient. A conflict miss happens with capacity to spare.
- • "The cache is 8-way, so this cannot be a conflict" — associativity raises the number of colliding addresses tolerated, it does not make conflicts impossible.
- • "Making the arrays smaller will fix it" — if the collision comes from the distance between bases, shrinking the arrays may leave that distance unchanged.
- • "This is a compiler bug" — the compiler is entitled to lay out allocations however it likes; the address relationship is not part of the language's contract.
Consequences, controls and cost
- • Performance becomes sensitive to the numeric addresses of allocations, which are not visible in the source and can shift between builds.
- • A loop over two or three arrays can miss on nearly every access despite a working set far smaller than the cache.
- • Adding cache capacity does not fix a conflict — the colliding addresses still map to one line.
- • Power-of-two strides and power-of-two array sizes are disproportionately likely to trigger it, because they preserve index bits.
- • Avoid power-of-two strides through large arrays; padding a row or an allocation by one line often removes the collision entirely.
- • Interleave data that is accessed together into one structure so it shares lines instead of competing for them.
- • Prefer blocked or tiled traversal so the hot set at any moment is small and contiguous ([[matrix-tiling]]).
- • Where the platform exposes it, measure conflict behaviour rather than reasoning about it — allocator and linker decisions move addresses under you.
- • Compare miss counts at two allocation offsets: pad one array by a single cache line and rerun. A large change with identical work points at conflicts.
- • Sweep the stride of a synthetic traversal and plot misses; conflict behaviour shows up as spikes at power-of-two strides rather than a smooth curve.
- • Read the cache-miss counters at the affected level rather than total misses, so a conflict at one level is not hidden by hits at another ([[performance-counters]]).
- • Print or log the base addresses of the hot allocations — the collision is usually obvious once the numbers are side by side.
- • Padding to break a collision wastes memory and can itself push a working set over a capacity limit.
- • Layout tricks are fragile: they encode assumptions about geometry that differ across machines and can be undone by an allocator change.
- • Reasoning about index bits is a deep rabbit hole for a problem that associativity mostly solves; spend the effort only when measurement says conflicts dominate.
Scope
§224 — what these claims are specific to.
- SIMPLIFIEDUses an 8-line cache so index collisions are visible in a table. Real caches have thousands of lines and are almost always set-associative.
- MICROARCH-SPECIFICWhich structures are direct-mapped, and the exact bit positions used for the index, are per-design choices that change between CPU generations.