compulsory, capacity and conflict misses

A cache miss is simply the moment the CPU asks for data that is not in the cache it checked, so it must go to a slower level (and stall, waiting). Not all misses are the same, though, and a famous classification — the three C's — sorts them by their root cause, because each cause has a different cure. Knowing which kind you are suffering tells you what to change.

A compulsory miss (also called a cold miss) is the first-ever access to a line: the data has never been loaded, so of course it is not cached. Nothing can prevent the very first touch, though prefetching can hide its latency by issuing it early. A capacity miss happens because your working set — all the data you are actively reusing — is simply bigger than the cache, so older lines get evicted before you come back to them, even in an ideal fully-associative cache. The cure is to shrink the working set: process data in cache-sized tiles or blocks. A conflict miss happens when lines that WOULD fit in the cache nonetheless evict each other because they map to the same set under the cache's limited associativity. The cure is to change layout or stride so addresses spread across more sets, or rely on higher associativity.

These three account for misses in a single cache, and the practical workflow is: measure your miss rate with hardware performance counters, then ask which C dominates. Compulsory-heavy code wants prefetching; capacity-heavy code wants blocking and smaller data; conflict-heavy code wants padding and stride changes. A fourth C — coherence misses, where another core invalidates your line — is added once you go multi-threaded; that one is the cost behind false sharing.