The Memory Hierarchy & Caches

a cache miss

You reach for the pen — and it is not on the desk. Now you have to open the drawer, find it, and bring it over, which takes real time. A cache miss is this less lucky moment: the data the CPU asked for is NOT in the cache, so the hardware must go down to the slower level (the next cache or main memory) to fetch it before the access can complete.

On a miss, the cache requests the missing line from the level below and waits — this wait is the miss penalty, often tens to hundreds of cycles. When the line arrives it is placed in the cache (evicting some existing line if the spot is occupied, per the replacement policy), so that future accesses to it hit. Misses come in three flavours, the three C's: compulsory (the very first reference to a block, unavoidable), capacity (the working set is bigger than the cache, so useful data was evicted to make room), and conflict (in a non-fully-associative cache, several hot blocks compete for the same set and keep knocking each other out, even though the cache as a whole is not full).

Misses are not a malfunction — every access to brand-new data must miss at least once — but they are where almost all of memory's cost hides, because each one drops to the slow level. Reducing misses is the main game of performance tuning: better locality shrinks capacity and conflict misses, larger or smarter caches help too, and prefetching tries to turn a miss into a hit by fetching data before it is asked for. Honest caveat: you can never drive misses to zero, because compulsory misses are inherent to touching data for the first time.

Reading a never-before-touched array element forces a compulsory miss: the line is pulled from DRAM, costing the miss penalty. Reading a column-major 2D array in a row-major language strides far each step, defeats the line, and turns nearly every access into a miss — same answer, many times slower.

The data is not in the cache, so the access drops to a slower level and pays the miss penalty.

You cannot eliminate all misses: a block's FIRST access (a compulsory miss) is unavoidable. Tuning targets capacity and conflict misses, which come from too small a cache and from collisions — not from touching data for the first time.

Also called
miss未命中