Cache Line and Eviction

Definition: A cache line is the fixed-size block of memory, typically 64 bytes, transferred between main RAM and CPU cache as one unit; eviction policies select which cached lines to discard when the cache is full and a new line needs space.

How It Works

When a CPU requests a single byte, the memory controller doesn’t fetch just that byte; it loads the entire 64-byte cache line containing it, exploiting spatial locality (nearby addresses are likely to be accessed soon)
Cache mapping decides where in the cache a given memory address can live: Direct-Mapped (each address maps to exactly one cache slot), Fully Associative (an address can go in any slot, requiring a full search to check for a hit), and Set-Associative (a middle ground: an address maps to one set of N slots, N-way associative, and can occupy any slot within that set)
Eviction policies choose which line to discard when a set is full and a new line must be loaded: LRU (Least Recently Used) evicts the line unused for the longest time, Pseudo-LRU approximates true LRU cheaply in hardware using a few bits instead of a full access-order list, FIFO evicts the oldest-loaded line regardless of recent use, and Random simply picks a victim, which is surprisingly competitive with LRU on some workloads and far cheaper in hardware
Write policies govern what happens on a write: Write-Through updates both cache and RAM immediately (simpler, more memory traffic), Write-Back updates only the cache and marks the line dirty, deferring the RAM write until the line is evicted (less memory traffic, more complex correctness)
A memory address splits into a tag (identifies which block of memory this line holds), an index (which set it belongs to), and an offset (which byte within the 64-byte line); a cache lookup compares the tag of the requested address against the tags stored in the relevant set
Cache coherence protocols (MESI: Modified, Exclusive, Shared, Invalid) keep multiple cores’ caches consistent when they cache overlapping memory, since each core has its own private L1/L2 cache but shares the same underlying memory
Under MESI, a line is Modified (dirty, only this core has it), Exclusive (clean, only this core has it), Shared (clean, multiple cores may have it read-only), or Invalid (not present/stale); a core writing to a Shared line must first broadcast an invalidation so every other core’s copy becomes Invalid before the write proceeds
Prefetching hardware watches access patterns (e.g. sequential stride) and speculatively loads lines before they’re explicitly requested, hiding miss latency for predictable access patterns without any software change
Associativity and eviction interact: a direct-mapped cache has no eviction policy to speak of, since each address has exactly one possible slot, so “eviction” there just means unconditionally overwriting whatever was in that slot

Under the Hood

Given: a 4-way set-associative L1 cache, 64-byte lines, and a set that already holds lines A, B, C, D with access order A (oldest) then C then D then B (most recent). Step 1: the CPU requests address X, which maps to this same set but isn’t currently cached, a miss. Step 2: the set is full (4 lines in a 4-way set), so LRU eviction picks the least recently used line, A. Step 3: if A is dirty (modified since loaded), it’s written back to the next cache level or RAM before being discarded; if clean, it’s simply dropped. Step 4: the new line for X is loaded into A’s now-free slot. Answer: one miss costs a full line fetch (tens of nanoseconds) plus, if the evicted line was dirty, an extra writeback, versus roughly 1 nanosecond for a hit.

Given: row-major traversal of a 1000x1000 int matrix (for i: for j: sum += m[i][j]) versus column-major traversal (for j: for i: sum += m[i][j]) of the same array. Step 1: row-major access touches consecutive memory addresses, so each 64-byte line (16 ints) serves 16 consecutive accesses before the next line is needed, a cache hit almost every time. Step 2: column-major access jumps 4000 bytes (1000 ints) between consecutive accesses, landing in a different cache line, and often a different page, on nearly every single access. Answer: row-major traversal can run several times faster, commonly cited around 5-10x on large matrices, purely from cache-line utilization, with no change to the algorithm’s actual operation count.

Given: two threads on separate cores, one incrementing counters[0], the other incrementing counters[1], where counters is an int[8] array (32 bytes, well inside one 64-byte line). Step 1: both variables physically share the same cache line, so each thread’s write invalidates the other core’s cached copy of that line under MESI, even though the threads never touch each other’s variable. Step 2: every write forces a coherence round-trip, the line ping-pongs between “Modified on core A” and “Modified on core B” states, a phenomenon called false sharing. Answer: padding each counter to its own 64-byte-aligned cache line (e.g. alignas(64) in C++) eliminates the false sharing and can turn a badly-scaling parallel loop into one that scales close to linearly with core count.

Real Numbers

L1 cache hit: roughly 1-4 cycles (~1 ns on a multi-GHz core)
L2 cache hit: roughly 10-20 cycles (~3-5 ns)
L3 cache hit: roughly 30-70 cycles (~10-20 ns)
Main memory (DRAM) access on a miss all the way through the hierarchy: roughly 200-400 cycles (~50-100 ns)
These numbers mean a single L1 miss that goes all the way to DRAM can cost the CPU 100-400x longer than a hit, which is why cache behavior, not raw instruction count, dominates real-world performance for memory-bound code

Why It Matters

Writing cache-friendly code dramatically outperforms algorithmic micro-optimizations in real-world software performance, since a cache miss costs tens to hundreds of cycles that no amount of clever arithmetic can avoid once it happens
Data structure layout decisions (array-of-structs vs struct-of-arrays, padding, alignment) exist almost entirely because of cache-line behavior, not correctness
Eviction policy choice is a real hardware tradeoff: true LRU is expensive to implement exactly at high associativity, which is why most real CPUs use pseudo-LRU approximations rather than perfect LRU

Common Pitfalls

False sharing: two independent threads on separate cores writing to different variables that happen to sit in the same 64-byte cache line force constant cache-coherence invalidation traffic between cores, even though the threads never touch the same variable, silently serializing what should be parallel work
Assuming a bigger cache always helps: a workload with a poor access pattern (heavy pointer-chasing, random access) can thrash a cache of any reasonable size, since the problem is locality, not capacity
Ignoring alignment: a data structure that straddles two cache lines can require two separate line fetches for what should be a single access
Forgetting that eviction and dirty writebacks aren’t free: a write-heavy workload with poor locality generates extra memory bus traffic from evicting dirty lines, not just from the original misses
Manually “optimizing” for cache behavior without measuring: guessing at access patterns is unreliable; tools like perf stat -e cache-misses,cache-references or a hardware profiler should confirm the theory before restructuring code around it

Comparison

Mapping	Hit search cost	Conflict misses	Hardware complexity
Direct-Mapped	O(1), one slot to check	High	Low
Set-Associative (e.g. 8-way)	Check N slots in a set	Moderate	Moderate
Fully Associative	Check every slot	Low	High

Eviction policy	Accuracy	Hardware cost
True LRU	Best	Expensive at high associativity
Pseudo-LRU	Close approximation	Cheap, a few bits per set
FIFO	Ignores recent reuse	Cheap
Random	Surprisingly competitive	Cheapest

Write policy	RAM traffic	Complexity	Typical use
Write-Through	Every write hits RAM	Simple	Caches needing strong consistency guarantees
Write-Back	Only on eviction of dirty lines	More complex, needs dirty bits	Most modern CPU data caches

Example

x86-64 CPUs (Intel, AMD) use a 64-byte cache line size, and typical L1 data caches are 8-way set-associative. Apple’s M-series (ARM64) chips also use 64-byte lines. std::hardware_destructive_interference_size in C++17 exposes this line size to code specifically so developers can pad structures to avoid false sharing between threads. Tools like perf stat -e cache-misses on Linux or Intel VTune let engineers directly measure cache miss rates against the theory described here.

Database engines lean on this heavily too: PostgreSQL and MySQL’s InnoDB both organize on-disk B-tree pages to align with cache-friendly access patterns, and in-memory databases like Redis are explicitly designed around keeping hot data structures compact enough to stay resident in L2/L3 cache rather than spilling to main memory.

Given: a game engine’s entity system stores each entity as a large struct with position, velocity, health, AI state, and rendering data all together (array-of-structs), then a physics update touches only position and velocity for thousands of entities per frame. Step 1: iterating the array-of-structs pulls every field of every entity into cache, even the fields (AI state, rendering data) the physics pass never touches, wasting most of each fetched cache line. Step 2: restructuring to a struct-of-arrays, separate contiguous arrays for position, velocity, health, and so on, means the physics pass streams only through the position/velocity arrays, using every byte of every fetched cache line. Answer: this “data-oriented design” pattern, common in game engines and high-performance simulation code, is a direct, deliberate application of cache-line theory to data layout, often yielding multi-x speedups on hot loops with no algorithmic change at all.

Referenced by

Dig deeper

Spot an error in this note?