Memory Hierarchy and CPU Cache¶

The numbers everything else is built on¶

Every design decision in a storage engine is a negotiation between layers of a hierarchy whose speeds differ by orders of magnitude.

The exact numbers vary by hardware; the ratios are what matter. A single cache miss to DRAM costs about as much as 100 L1 hits, and a single SSD read costs about as much as 1000 DRAM accesses. That is why an index structure is judged by how many cache misses or disk reads it takes per lookup, not by how many comparisons — the comparison count that CP complexity analysis cares about is close to free next to the memory accesses.

Cache lines: memory moves in 64-byte chunks¶

The CPU never reads one byte from DRAM. It reads a cache line — 64 bytes on x86 and most ARM servers (128 bytes on Apple M-series). Reading a[0] brings a[0..15] (for int32) into L1; reading a[1] right after is then nearly free.

That single fact explains the most important performance rule in systems code: contiguous memory is fast, pointer chasing is slow.

Worked example: summing an array vs. a linked list¶

type node struct {
    v    int64
    next *node
}

func sumSlice(v []int64) (s int64) {
    for _, x := range v { // sequential: 8 values per 64-byte line, prefetched
        s += x
    }
    return
}

func sumList(n *node) (s int64) {
    for ; n != nil; n = n.next { // each node is a separate object: a pointer chase
        s += n.v
    }
    return
}

Both are O(n) with the same number of additions. Measured in Go on an Apple M1 Pro with 1 M elements (CPU and Cache Efficiency):

The slice sum runs at memory bandwidth. The list is slower because each next pointer must be loaded before the CPU knows where the next node is, and once the nodes are scattered, every step is a cache miss. The CPU's hardware prefetcher recognizes sequential and strided access patterns and fetches lines before they are asked for; it cannot predict a pointer chase.

This is the reason:

• []T beats []*T and linked structures in Go for anything iterated.
• B+Trees have nodes the size of a disk page holding hundreds of keys (one miss brings in many keys) instead of binary nodes with two.
• LSM SSTables store keys in sorted, densely packed blocks.
• Skip lists are tolerated in memtables only because they enable lock-free concurrent reads; they are not cache-friendly.

Cache associativity, TLB, and huge pages¶

Caches are not fully flexible: an address can only be placed in a small set of slots (set-associative, e.g. 8-way or 12-way). Access patterns with a large power-of-two stride (every 4096 bytes, say) map to the same set and evict each other — a slowdown that looks mysterious until you know the cause.

Virtual addresses must also be translated to physical ones (see Virtual Memory and Paging). The TLB caches recent translations, but it has only a few thousand entries. With 4 KB pages, 1,536 TLB entries cover just 6 MB; a 50 GB block cache touched randomly misses the TLB on almost every access, each miss costing a page-table walk. Huge pages (2 MB) let each TLB entry cover 512x more memory, which is why databases often recommend enabling them for large buffer pools — and why many also recommend disabling Transparent Huge Pages, whose background compaction can cause latency spikes.

Writes and multiple cores: coherence and false sharing¶

Each core has its own L1/L2. When one core writes a cache line, every other core's copy of that line must be invalidated (the MESI coherence protocol). The line then bounces between cores' caches on every write — about as expensive as a DRAM access.

False sharing is when two threads write different variables that happen to sit on the same cache line:

type Counters struct {
    reads  atomic.Uint64 // written by goroutine A
    writes atomic.Uint64 // written by goroutine B — same cache line!
}

The two threads never touch each other's data, yet every increment invalidates the other core's line. The fix is to pad each hot variable onto its own line:

type Counters struct {
    reads  atomic.Uint64
    _      [120]byte // pad: 128 bytes covers both 64- and 128-byte lines
    writes atomic.Uint64
    _      [120]byte
}

Go has no alignment attribute; padding fields do the job. golang.org/x/sys/cpu.CacheLinePad is a portable padding type sized for the target architecture. Measured in Go with 8 goroutines each incrementing its own counter: 45x slower when the counters share lines than when each is padded (CPU and Cache Efficiency). Go's runtime pads its own per-P structures for the same reason.

Data layout: array of structs vs. struct of arrays¶

// Array of structs (AoS): one entry = key + value + metadata together.
type Entry struct {
    Key, Seq uint64
    Value    [48]byte
}
var entries []Entry // binary search touches a 64-byte entry per probe

// Struct of arrays (SoA): keys contiguous, separate from payload.
var keys   []uint64 // binary search touches only keys
var seqs   []uint64
var values [][48]byte

A binary search over entries loads a full 64-byte entry per probe but uses only 8 bytes of it. Over keys, the last several probes land in the same few lines. Measured in Go, 10 million entries, random lookups with sort.Search: 494 ns per lookup over entries, 284 ns over keys — 1.7x faster with the same number of comparisons. This is the same idea behind a B+Tree node storing its keys in one array and its child pointers in another, and behind columnar formats (Parquet, ClickHouse) storing each column contiguously.

Branch prediction¶

Modern CPUs guess which way a branch goes and execute ahead speculatively; a wrong guess costs ~15–20 cycles. Branches that follow data with no pattern (comparing random keys) mispredict about half the time. This is why tight inner loops — Bloom filter probing, binary search within a block — are sometimes written branch-free, and why sorted data is often faster to process than unsorted data for the same operations. Compilers can remove simple branches entirely: in Go, a conditional add compiled to a branch-free CSEL ran at the same speed on sorted and random data, while a slightly more complex loop body that kept its branch ran 3.2x slower on random data (CPU and Cache Efficiency).

How to measure, not guess¶

# Linux: count cache misses and branch mispredictions for a benchmark run
perf stat -e cycles,instructions,cache-misses,LLC-load-misses,branch-misses \
  ./kv.test -test.run='^$' -test.bench=Get

Instructions per cycle (IPC) is the single most useful summary: an IPC near 3–4 means the CPU is busy computing; an IPC below ~0.5 means it is mostly waiting on memory. See CPU and Cache Efficiency.

Common pitfall¶

Optimizing the comparison count of a data structure while ignoring its memory layout is the classic CP instinct that fails in systems code. A theoretically better structure that chases pointers — a balanced binary tree, a hash table with chaining — routinely loses to a "worse" structure over contiguous memory, such as a sorted array with binary search, or an open-addressing hash table. Before choosing a structure, count the cache lines touched per operation, and confirm with perf stat rather than with Big-O.