CPU Cache Deep Dive: Why Cache Misses Kill Performance and How to Write Cache-Friendly Code

Many programmers focus on algorithmic complexity but overlook CPU cache effects. Two algorithms with identical O(n) complexity can differ by orders of magnitude in runtime due to cache behavior. This article builds from hardware fundamentals to practical C++ optimizations with measured results.

Why Cache Exists

Modern CPUs run at 3+ GHz (0.33 ns per cycle). Register access takes 1 cycle. DRAM latency is 70–100 ns (~200 cycles). Without cache, the CPU would stall waiting for data most of the time. Cache uses small, fast SRAM to hold recently used data so the CPU can fetch it in a few cycles.

Cache Hierarchy (Intel i7 Example)

Registers – Capacity: Dozens; Latency: 1 cycle; Scope: Current core

L1 Cache – Capacity: 32 KB data + 32 KB instruction; Latency: 4 cycles; Scope: Current core private

L2 Cache – Capacity: 256 KB–1 MB; Latency: 12 cycles; Scope: Current core private

L3 Cache – Capacity: 8 MB–64 MB; Latency: 40 cycles; Scope: All cores shared

Main Memory – Capacity: 16 GB+; Latency: 200+ cycles; Scope: All cores shared

L1 splits into L1i (instruction) and L1d (data). Performance issues mainly involve L1d and L2.

Cache Line and Address Breakdown

Data moves in fixed 64-byte cache lines (x86 and ARM servers). Reading a single 4-byte int pulls the entire 64-byte line. Sequential array access exploits this: the next 15 int s are already in cache.

A physical address splits into three fields:

Offset (6 bits) – byte index within the 64-byte line (2⁶ = 64).

Index – selects the cache set. For a 32 KB, 8-way cache with 64-byte lines: sets = 32 KB / (64 B × 8) = 64 sets → 6 index bits.

Tag – remaining high bits; distinguishes different lines mapping to the same set.

If two addresses share the same index but different tags, they contend for the same set. When associativity is exhausted, conflict misses occur — the hardware root of false sharing.

Cache Mapping Policies

Direct Mapped – each address maps to exactly one line (address modulo sets). Fastest lookup, but high conflict misses if hot addresses collide.

Fully Associative – any line can hold any address. Requires parallel tag comparison of all lines; expensive, only used for tiny caches (e.g., TLB).

Set Associative – compromise: address maps to a set, then any way within that set. Modern CPUs: L1d typically 8-way, L2 8–16-way, L3 12–16-way. More ways reduce conflicts but increase comparator complexity.

Direct Mapped – Hit Speed: Fastest; Conflict Rate: High; Hardware Cost: Lowest

Set Associative – Hit Speed: Medium; Conflict Rate: Medium; Hardware Cost: Medium

Fully Associative – Hit Speed: Slowest; Conflict Rate: Lowest; Hardware Cost: Highest

Write Policies

Write Hit:

Write-through – write to cache and memory simultaneously. Simple coherence but write bandwidth limited by memory speed.

Write-back – write only to cache, mark line dirty. Dirty line written back on eviction. Used by virtually all modern CPUs because most written data isn't immediately read by other cores.

Write Miss:

Write-allocate – fetch line into cache, then write. Subsequent writes hit. Paired with write-back.

No-write-allocate – write directly to memory, bypass cache. Suitable for large streaming writes never read again.

Code implication: Small writes trigger write-allocate, pulling the whole 64-byte line into cache. This explains why tiny structs waste bandwidth and why false sharing arises.

Multi-Core Coherence: MESI Protocol

Each cache line holds one of four states in its controller:

M (Modified) – line dirty in this core's cache; memory stale; no other core has it.

E (Exclusive) – line clean in this core's cache; no other core has it; memory up to date.

S (Shared) – line clean in multiple cores' caches; memory up to date.

I (Invalid) – line unusable.

Example transition: Core 0 reads address A → state E (fastest, exclusive). Core 1 reads A → bus broadcasts read; Core 0 changes to S, Core 1 loads S. Core 0 writes A → broadcasts invalidate; Core 1 changes to I and acknowledges; Core 0 changes to M and writes. This invalidate-acknowledge round-trip is the protocol-level cause of false sharing slowness. Atomic operations, mutexes, and spinlocks all rely on MESI state transitions; a contended atomic add can be dozens of times slower than a cache hit.

Practice 1: Array Traversal Order

C++ stores 2D arrays row-major. Row-major traversal (outer loop rows, inner loop columns) accesses memory sequentially. Column-major jumps 10,000 int s (40 KB) per iteration, far exceeding a cache line.

// Row-major (fast)
const int N = 10000;
std::vector<std::vector<int>> a(N, std::vector<int>(N, 1));
for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    sum += a[i][j];

// Column-major (slow)
for (int j = 0; j < N; j++)
  for (int i = 0; i < N; i++)
    sum += a[i][j];

Measured on x86: row-major ~0.1 s, column-major ~0.9–1.0 s (≈8× slower). Row-major: 1 miss per 16 accesses (64 B / 4 B). Column-major: miss every access.

Rule: match loop nesting to memory layout. C/C++ row-major → outer loop rows, inner loop columns. Fortran column-major → reverse.

Practice 2: Struct Layout and Cache Line Alignment

A 64-byte cache line holds one struct if size ≤ 64 B. Crossing a line boundary costs two loads.

// Bad: hot field straddles line boundary
struct Widget {
  char buf[60];
  int value; // falls on next cache line
};
void process(Widget* w) {
  for (int i = 0; i < 1000000; i++)
    w[i].value += 1; // each iteration loads two lines
}

Better: group hot fields, pad to 64 B, align.

struct alignas(64) Widget {
  int value;
  int count;
  char buf[56]; // cold data fills remainder
};
void process(Widget* w) {
  for (int i = 0; i < 1000000; i++) {
    w[i].value += 1;
    w[i].count += 1; // both in same line
  }
}

alignas(64)

(C++11) forces 64-byte alignment so each Widget occupies exactly one line. Also, order fields largest-to-smallest to minimize compiler-inserted padding.

Practice 3: False Sharing

Two threads modify distinct atomics that happen to share a cache line. Each write marks the line dirty and broadcasts invalidate; the other core's copy becomes I, forcing a reload on its next write. Ping-pong effect kills scalability.

struct Counter {
  std::atomic<long long> a{0};
  std::atomic<long long> b{0}; // 16 bytes total → same cache line
};
Counter cnt;
void worker_a() { for (long long i=0; i<100000000LL; i++) cnt.a.fetch_add(1, std::memory_order_relaxed); }
void worker_b() { for (long long i=0; i<100000000LL; i++) cnt.b.fetch_add(1, std::memory_order_relaxed); }

Fix: give each atomic its own cache line.

struct alignas(64) CounterA { std::atomic<long long> a{0}; char padding[56]; };
struct alignas(64) CounterB { std::atomic<long long> b{0}; char padding[56]; };
CounterA cnt_a; CounterB cnt_b;

C++17 provides a portable constant:

#include <new>
struct alignas(std::hardware_destructive_interference_size) CounterA { std::atomic<long long> a{0}; };
struct alignas(std::hardware_destructive_interference_size) CounterB { std::atomic<long long> b{0}; };

On x86, hardware_destructive_interference_size = 64. Use perf stat to watch L1-dcache-load-misses and LLC-load-misses; if parallel run is slower than sequential and L1d misses spike, false sharing is likely.