Set-Associative Caches: Trading Global Optimality for Predictable Speed

Set-Associative Caches: Trading Global Optimality for Predictable Speed Caches are everywhere in modern systems: CPU L1/L2 caches, database buffer caches, storage-engine object caches, and application-level LRU maps. They do not all make the same trade-offs. A set-associative cache sits at a particular point in the design space: it gives up global replacement freedom in exchange for bounded probing, compact layout, and predictable cache-line-friendly access. This post walks through what that means, why Tige