cache associativity

A cache is much smaller than the memory it stands in front of, so many different memory addresses must compete for the same shelf space. Associativity is the rule for which shelves a given address is allowed to sit on. Think of a coat-check with numbered hooks: if your ticket forces you to one specific hook (and you must evict whatever hangs there), that is restrictive but instant to look up; if your coat may go on any of several hooks, you get fewer fights but checking takes a little more work.

Three designs sit on a spectrum. In a direct-mapped cache, each memory address maps to exactly one line slot — fast to check, but two hot addresses that map to the same slot evict each other forever. In a fully-associative cache, any address may live in any slot — no forced collisions, but checking every slot on every access is expensive, so this is only used for tiny structures. The practical middle ground is set-associative: the cache is divided into sets, an address maps to exactly one set, and within that set it may occupy any of N ways (an N-way set-associative cache, commonly 4-, 8-, or 16-way). The hardware splits the address into three fields to do this: the lowest bits are the line offset (which byte within the 64-byte line), the next bits are the set index (which set), and the top bits are the tag (stored alongside the line to confirm which of the many addresses mapping to this set is actually present).

Why you should care: associativity is what turns a theoretically-big-enough cache into one that still thrashes. If your access pattern keeps landing addresses that all map to the same set — classically, striding through memory by a power-of-two that equals the set stride — you can evict live data while most of the cache sits empty, producing conflict misses. This is why a 1024-element stride can be dramatically slower than a 1023-element stride: the off-by-one breaks the power-of-two aliasing.