03 · Cache & Memory Hierarchy

Everything you thought was slow in your code is fast. Everything you thought was fast is a lie. On a modern CPU, a floating-point multiply takes ~4 cycles; a DRAM miss takes ~300. If you cannot make your data live in cache, you cannot make your kernel fast — the ALU will spend 98% of its life waiting. This file gives you the latencies, the geometry, the anti-patterns, and the one mental model (the roofline) that lets you predict a kernel’s ceiling in under a minute.

The latency table you must memorize

Approximate cycle costs on a modern (2024–2026) x86 or Apple Silicon core running at ~3–4 GHz:

Access	Latency (cycles)	Wall-clock @ 3 GHz	Size
Register	0	—	~1 KB per core
L1 data cache hit	4–5	~1.5 ns	32–64 KB / core
L2 cache hit	12–15	~4 ns	256 KB – 2 MB / core
L3 cache hit	30–75	~15 ns	4–64 MB shared
DRAM	200–300	~80 ns	GB
Cross-socket / NUMA-remote DRAM	400+	~150 ns	GB
SSD (NVMe) read	—	~20,000 ns (20 µs)	TB
Network round-trip datacenter	—	~500,000 ns (500 µs)	—

Read the DRAM line again. 300 cycles. Your CPU can retire ~4 instructions per cycle. A single DRAM miss is 1,200 lost instructions. That is the number that makes cache-blocking a religion.

Source for the specific numbers: Ulrich Drepper’s “What Every Programmer Should Know About Memory” (2007, still the canonical reference; updated numbers from Intel Optimization Manual 2024, Apple Silicon numbers from Anandtech M-series microarch deep dives). See Phase 7 · 06_the_c_expert_reading_list.md.

Cache-line geometry

All modern x86 and ARM CPUs use a 64-byte cache line. This is the unit of transfer between cache levels and between cache and DRAM. Load one byte, and 63 more come along for the ride — free if you use them, wasted if you don’t. This single fact drives:

• Struct layout. Put fields accessed together on the same line. Padding is not waste; it is alignment.

• False sharing. Two threads writing to two different variables on the same cache line will ping-pong the line between their L1s at DRAM-miss cost. Use alignas(64) or _Alignas(64) in C11 to separate hot per-thread counters.

• Row-major vs column-major. A row-major float matrix accessed by column skips 4 bytes but forces a new cache line every 16 elements — devastating for GEMM. This is the reason cache-blocked matmul exists.

Prefetching (know it exists, rarely write it)

Modern cores have hardware prefetchers that recognize sequential and strided access patterns and pull the next line before you ask. They cover ~80% of cases. For the other 20% — pointer chasing, indirect indexing — you can use __builtin_prefetch(ptr, rw, locality) in GCC/Clang or _mm_prefetch() in x86 intrinsics. Only insert prefetches after you have measured the miss rate and confirmed the hardware isn’t already handling it. Blind prefetching hurts as often as it helps. perf stat -e L1-dcache-load-misses is your friend.

The roofline model in 60 seconds

A kernel’s peak achievable performance is bounded by two ceilings:

1. Peak compute (GFLOPS): how many multiply-adds/sec the ALUs can retire.

2. Peak bandwidth (GB/s): how many bytes/sec DRAM can deliver.

Define arithmetic intensity = FLOPs performed per byte loaded from DRAM. Plot GFLOPS on the y-axis vs arithmetic intensity on the x-axis, log-log. You get:

• A diagonal ramp on the left (bandwidth-bound region: GFLOPS = bandwidth × intensity).

• A horizontal cap on the right (compute-bound region: GFLOPS = peak_compute).

• The corner between them is the ridge point.

Every kernel lives on one of those two ceilings. Your job as a kernel writer is (a) know which side you’re on, (b) if you’re on the ramp, either raise the intensity by cache-blocking or accept the bandwidth limit and stop optimizing FLOPs.

Worked example — LLM decode with Q4_K weights:

• Model: ~7B params = ~7 GB at FP16, ~3.8 GB at Q4_K.

• Per token: read all weights once from DRAM = 3.8 GB.

• DRAM bandwidth on a Ryzen 7950X: ~80 GB/s.

• Ceiling: 80 / 3.8 = ~21 tokens/sec. That is what you should see, and roughly what you do see on llama.cpp for a 7B Q4_K model on that chip.

• Doubling FLOPs would change nothing. Doubling bandwidth would double tokens/sec. This is why Apple’s M3 Max (~400 GB/s unified memory) tokens/sec dominates any Intel desktop for LLM inference.

That one calculation is what an infra engineer at Anthropic does in their head. Learn to do it.

Anti-patterns to grep out of your code

Pattern	Why it dies	Fix
struct Point { float x, y, z; } array iterated by .x only	3× the bandwidth used	SoA: three parallel arrays
Two threads incrementing counter[thread_id] in a shared array	False sharing on same 64-byte line	Pad each counter to its own line
for (col = 0; col < N; col++) for (row = 0; row < M; row++) a[row][col]	Strided access, cache line thrashing	Transpose loops or transpose matrix
Random pointer chasing in a linked list	Every node is a miss	Flatten into an array; use indices, not pointers
mallocing 1 million tiny nodes	Cache-hostile placement, TLB misses	Pool allocator, arena

Tools to actually measure this

• Linux: perf stat -e cache-misses,cache-references,cycles,instructions ./a.out

• Linux: perf record -e L1-dcache-load-misses + perf report for hotspot line.

• Linux advanced: Intel VTune, AMD µProf, likwid-perfctr.

• Mac: Instruments’ “CPU Counters” template; enable the L1D_CACHE_MISS_LD PMC. Apple hides most PMCs on non-Pro chips; on M3 Pro and up you get real access.

• Universal: valgrind --tool=cachegrind ./a.out — simulated, slow, but portable.

What most people get wrong about this

They optimize the wrong loop. They see a triple-nested loop, assume the innermost is where the work is, and vectorize it. Meanwhile the middle loop is the one causing every third iteration to miss L2. The correct workflow is: measure first with perf stat, then look at the loop that owns the misses, not the loop that owns the FLOPs. The FLOPs will fall into place once the data lives in cache. Every senior kernel engineer has this reflex. You now know why.

---

Return to README.md · Next: 04_matmul_and_gemm.md