CPU caches and the memory hierarchy

Deep dive

How it works

In: a stream of load and store addresses · Out: the data, served from the nearest level that holds its 64 B or 128 B line · State: cached lines with their coherence state, prefetcher stream trackers · Cost: L1 hit 4-5 cycles; DRAM order of 70-150 ns.

1. Line: the unit of transfer and coherence. One byte read pulls in the whole line. x86 lines are 64 B. Apple M-series reports hw.cachelinesize = 128.
2. Levels (typical current parts; check yours):

E-cores on M4 Pro have 64 KiB L1d and a 4 MiB shared L2. 3. Associativity: each address maps to one set of N ways. Power-of-two strides (for example walking a column of a 4096-wide f32 matrix) hit the same set and evict each other long before the cache is full. 4. Prefetchers spot sequential and strided streams and fetch ahead. Intel's L2 streamer does not cross 4 KiB page boundaries. Pointer chasing and hash probes defeat them. 5. Memory-level parallelism: a core tracks a bounded number of outstanding L1 misses (order of 10-20 fill buffers on x86). Little's law gives per-core bandwidth ≈ outstanding misses × line size / latency, for example 12 × 64 B / 80 ns ≈ 9.6 GB/s before L2 prefetching helps. Independent misses overlap; dependent ones (linked lists) do not. 6. Coherence: writes invalidate the line in other cores' caches (MESI-family protocols). Two cores writing different fields of one line ping-pong it: false sharing.

Decision table

Code

Pointer-chase benchmark. Each load's address depends on the previous load, so it measures latency per level. The sequential walk shows prefetching.

use std::hint::black_box;
use std::time::Instant;

// One node per 128 B: its own line on x86 (64 B) and on Apple (128 B).
#[repr(C, align(128))]
#[derive(Clone, Copy)]
struct Node { next: u32 }

fn xorshift(s: &mut u64) -> u64 { *s ^= *s << 13; *s ^= *s >> 7; *s ^= *s << 17; *s }

/// Random single-cycle permutation (Sattolo): following `next` visits every node once.
fn build(n: usize, seed: u64) -> Vec<Node> {
    let mut order: Vec<u32> = (0..n as u32).collect();
    let mut s = seed;
    for i in (1..n).rev() {
        let j = (xorshift(&mut s) % i as u64) as usize; // j < i, not <= i: one cycle
        order.swap(i, j);
    }
    let mut nodes = vec![Node { next: 0 }; n];
    for i in 0..n { nodes[order[i] as usize].next = order[(i + 1) % n]; }
    nodes
}

/// Average ns per dependent load: out-of-order execution and prefetchers cannot help.
fn chase_ns(nodes: &[Node], steps: usize) -> f64 {
    let mut i = 0u32;
    for _ in 0..nodes.len().min(steps) { i = nodes[i as usize].next; } // warm caches and TLB
    let t = Instant::now();
    for _ in 0..steps { i = unsafe { nodes.get_unchecked(i as usize) }.next; }
    black_box(i);
    t.elapsed().as_nanos() as f64 / steps as f64
}

/// Same nodes in address order: prefetchers stream them, latency mostly hidden.
fn sequential_ns(nodes: &[Node], steps: usize) -> f64 {
    let t = Instant::now();
    let mut acc = 0u32;
    for k in 0..steps { acc = acc.wrapping_add(nodes[k % nodes.len()].next); }
    black_box(acc);
    t.elapsed().as_nanos() as f64 / steps as f64
}

fn main() {
    let steps = 20_000_000;
    println!("{:>11} {:>10} {:>8}", "working set", "random ns", "seq ns");
    let mut kib = 16usize;
    while kib <= 1 << 20 { // 16 KiB .. 1 GiB
        let n = kib * 1024 / std::mem::size_of::<Node>();
        let nodes = build(n, 0x9E37_79B9_7F4A_7C15);
        println!("{:>8}KiB {:>10.2} {:>8.2}", kib, chase_ns(&nodes, steps), sequential_ns(&nodes, steps));
        kib *= 4;
    }
}

Build with --release. On an M4 Pro this prints about 2 ns up to 64 KiB, about 9-13 ns from 256 KiB to 4 MiB, and 105-135 ns from 16 MiB up. The sequential column stays at 1-3 ns per 128 B node.

Complexity and constants

• Peak L1 bandwidth: 2-3 loads per cycle of up to 32 B (AVX2) or 64 B (AVX-512) on x86. That is hundreds of GB/s per core.
• DRAM per channel: DDR5-4800 = 4800 MT/s × 8 B = 38.4 GB/s. Apple unified memory per chip: M1 about 68 GB/s (LPDDR4X-4266, 128-bit), M2 100 GB/s, M4 120 GB/s, M4 Max up to 546 GB/s.
• A random lookup in a 1 GiB table costs a cache miss and a TLB miss with 4 KiB pages. See virtual memory and TLB.
• Rule of thumb: 1 DRAM miss ≈ the time of several hundred simple instructions.

Efficiency

• Cost: an L1 hit takes 4-5 cycles; a DRAM miss takes order of 70-100 ns on client parts, 100-150 ns on servers, roughly the time of several hundred simple instructions. Independent misses overlap: 12 outstanding × 64 B / 80 ns ≈ 9.6 GB/s per core. A DDR5-4800 channel peaks at 38.4 GB/s. Bound: latency for dependent loads, bandwidth for streams.
• Levers:
  • struct of arrays — lines carry only used bytes — loops that read few fields of many records
  • batch independent lookups, issue all loads before using any — overlaps misses (Little's law above) — many random lookups
  • shrink items (u32 indices, f16/i8, bit packing) — crossing a cache level costs 3-10× latency — working set just above L2 or L3
  • nodes of 1-2 lines with keys first — one miss per node — trees and hash tables
• Naive → standard → state of the art:
• naive: linked list or Vec<Box<T>> traversal · one dependent miss, order of 100 ns, per element
• standard: contiguous array scan with the hardware prefetcher · limited by bandwidth, 38.4 GB/s per DDR5-4800 channel
• state of the art: compact layout with batched or prefetched lookups · misses overlap, per-core ceiling order of 10 GB/s

Implementation notes

• Query sizes. Linux: lscpu -C, getconf LEVEL1_DCACHE_LINESIZE, /sys/devices/system/cpu/cpu0/cache/index*/{level,size,coherency_line_size}. macOS: sysctl hw.cachelinesize hw.perflevel0.l1dcachesize hw.perflevel0.l2cachesize.
• Alignment: #[repr(align(128))] for hot shared data. crossbeam's CachePadded uses 128 B on x86_64 and aarch64 for the reasons above.
• Software prefetch: core::arch::x86_64::_mm_prefetch::<_MM_HINT_T0>(p) order of 10-20 iterations ahead of use. Useful only for addresses the hardware cannot predict (hash probes, tree descents in batches).
• Non-temporal stores (_mm256_stream_ps + _mm_sfence) skip the read-for-ownership on large write-only outputs that will not be read soon.
• Measure with perf stat -e cache-misses,LLC-load-misses on Linux. On macOS, use Instruments' CPU Counters.

Pitfalls

• Benchmarking a working set that fits in L2 and extrapolating to production sizes.
• Linked lists, Vec<Box<T>>, and HashMap<K, Box<V>> add one dependent miss per hop.
• Power-of-two row pitches causing set conflicts. Pad rows by one line.
• Assuming 64 B lines on Apple Silicon and padding per-core data only to 64 B.
• Random-access microbenchmarks that silently include TLB misses. Report the page size.

Implementations

Sources

• Ulrich Drepper, What Every Programmer Should Know About Memory, 2007. pdf
• John L. Hennessy, David A. Patterson, Computer Architecture: A Quantitative Approach, 6th ed., 2017, ch. 2.
• Intel, Intel 64 and IA-32 Architectures Optimization Reference Manual.