CPU Caches

The 30-second version

A modern CPU core ticks about 3 billion times a second, so one clock cycleCPU cycleOne tick of the processor's clock. At 3 GHz a cycle is a third of a nanosecond; a simple instruction takes about one cycle, a read from RAM a few hundred. is roughly 0.3 nanoseconds (a nanosecond, ns, is a billionth of a second). Fetching one value from RAMRAM (main memory)The computer's working memory: fast (~100 ns per access) but lost when the power goes off. Programs and their data live here while running. takes around 100 ns. That's about 300 cycles of waiting for a single read — time in which the core could have done hundreds of additions.

This gap is called the memory wallMemory wallThe gap between how fast a CPU can compute and how slowly main memory answers. CPUs got much faster over the decades; RAM latency barely moved. Caches exist to hide that gap.. Over the decades CPUs got far faster; RAM got bigger and cheaper, but not much quicker to answer. So chip makers put small, very fast memories right next to each core: the CPU cachesCPU cacheSmall, very fast memory on the CPU chip (L1, L2, L3) that keeps copies of recently used data. Reading from cache takes ~1–10 ns; reading from RAM takes ~100 ns..

Here are the rough numbers. Flip the toggle to scale them up a billion times, so that one L1 read takes one second:

Look at the gap between L1 and RAM: a 100× difference, and in the human-scaled version, one second versus almost two minutes. Every time your code reads something that isn't in a cache — a cache missCache hit / cache missA hit means the data asked for was already in the cache — fast. A miss means it wasn't, so it must be fetched from the slower source: for a CPU cache the next cache level or RAM, for an app cache the database or another service. — the core mostly sits and waits.

What you'll learn

1. How the caches are organised, and why memory moves in 64-byte cache lines (§02).
2. Locality: why the order you visit data in can change speed by 7× (§03–§07), with real measurements in Go and JavaScript.
3. What happens when several cores write to the same memory: coherence and false sharing (§08–§09).
4. How this changes which data structures you pick (§10), the staff-level extras — branch prediction, NUMA, the TLB (§11) — and how to measure, and when to care (§12).

L1, L2, L3 and the 64-byte cache line

Three layers

When a core needs a value, it checks the closest cache first and works outward. The first one that has it answers — a hit. If none do, the value comes from RAM, and copies are left in the caches on the way back, in case it's needed again soon.

These are the cache levelsL1 / L2 / L3 cacheThe layers of CPU cache. L1 is the smallest and fastest (tens of KB, ~1 ns) and private to one core; L2 is bigger and a bit slower, usually per core; L3 is the largest (many MB) and shared by all cores.:

• L1 is split in two: L1d for data and L1i for instructions (your compiled code). It's tiny and answers in a few cycles.
• L2 is private to one core too, bigger and a few times slower.
• L3 is shared by every core on the chip. It's the last stop before RAM.

You can read your own machine's sizes. This is the real output from the machine that ran this page's benchmarks:

$ lscpu | grep -i cache
L1d cache:                               192 KiB (4 instances)
L1i cache:                               128 KiB (4 instances)
L2 cache:                                8 MiB (4 instances)
L3 cache:                                260 MiB (1 instance)

$ cd /sys/devices/system/cpu/cpu0/cache
$ for i in index*; do echo "L$(cat $i/level) $(cat $i/type) $(cat $i/size) ways=$(cat $i/ways_of_associativity) line=$(cat $i/coherency_line_size)"; done
L1 Data 48K ways=12 line=64
L1 Instruction 32K ways=8 line=64
L2 Unified 2048K ways=16 line=64
L3 Unified 266240K ways=20 line=64

“4 instances” means one per core: 192 KB of L1d in total is 48 KB per core. The 260 MB L3 is what this cloud virtual machine reports; it's shared with other customers' machines, so the amount we really get is smaller (you'll see that in §07). On a Mac, sysctl -a | grep cachelinesize and sysctl hw.l1dcachesize give similar answers.

The cache line: memory moves in chunks

Caches don't store single bytes or single variables. They store cache linesCache lineThe chunk of memory (usually 64 bytes) that a CPU core copies into its own fast cache. When two cores write to the same cache line, it has to bounce between them, which is slow.: 64-byte blocks of memory that each start at an address that's a multiple of 64 (the last field above, line=64). Ask for one int64 (8 bytes) and the CPU fetches the whole 64-byte line around it — its 7 neighbours come along for free.

That's the library trip from §01: you bring back the whole chapter. Two consequences drive the rest of this topic:

1. Reading neighbours is nearly free. If your next read is in the same line, it's an L1 hit. (§03)
2. Cores share whole lines, not variables. If two cores write to different variables in the same line, the hardware still treats it as sharing. (Locks §07 showed one counter's line bouncing between cores; §08–§09 here explain exactly why it happens and how to measure it.)

What gets thrown out

Caches are small, so loading a new line usually means throwing an old one out — evictionEviction (cache)Throwing a cache line out to make room for a new one. CPUs evict roughly the least recently used line (LRU) — so data you haven't touched in a while is the first to go.. CPUs evict roughly the least recently used line. That's why data you use again soon tends to stay cached, and data you touched once, long ago, doesn't.

Locality: why order matters

Those two bets have names:

• Spatial localitySpatial localityIf a program reads one address, it will probably read the addresses right next to it soon (like walking through an array). Caches exploit it by loading a whole 64-byte line at once. — nearby in space. You read a[0], then a[1], then a[2]… The 64-byte cache line (§02) already brought them in.
• Temporal localityTemporal localityIf a program used some data recently, it will probably use it again soon (like a loop counter or a hot config). Caches exploit it by keeping recently used lines around. — nearby in time. You read the same thing again soon: a loop counter, a lookup table, a config. It's still in cache because it was used recently.

The classic: summing a grid

A 2D grid in Go — a slice of slices, [][]int64 — stores each row as one contiguous block of memory. That layout is called row-majorRow-major orderStoring a 2D grid row by row: all of row 0, then all of row 1, and so on. Go slices of slices, C arrays and a flat JS typed array indexed as r * width + c are all row-major.: all of row 0, then all of row 1, and so on. Now sum it two ways:

func sumRows(g [][]int64) (s int64) {
    for r := 0; r < len(g); r++ {
        for c := 0; c < len(g[r]); c++ {
            s += g[r][c] // ← next read is the neighbour: same cache line
        }
    }
    return s
}

func sumCols(g [][]int64) (s int64) {
    for c := 0; c < len(g[0]); c++ {
        for r := 0; r < len(g); r++ {
            s += g[r][c] // ← next read is one whole row (32 KB) away
        }
    }
    return s
}

Both functions do exactly the same 16.7 million additions on a 4096 × 4096 grid (128 MB). Only the order differs. Before reading the numbers, watch what each order does to a cache on a small grid:

Row order misses once per line and gets 7 hits for free. Column order lands on a different line every read, and by the time it comes back to a line, it's been evicted. Here's the real thing:

func BenchmarkSumRows(b *testing.B) {
    for b.Loop() {             // Go 1.24+: runs the body enough times to time it
        sink = sumRows(grid)   // store the result so the compiler can't delete the work (§12)
    }
}
// BenchmarkSumCols is the same with sumCols.

$ go test -bench 'Sum(Rows|Cols)'
BenchmarkSumRows-4   	      42	  25250921 ns/op
BenchmarkSumCols-4   	       6	 194562810 ns/op

~25 ms vs ~195 ms on this machine: almost 8× slower, for the same additions on the same data. (-4 is the number of cores Go used; the middle column is how many times it ran the loop. Across several runs the column version ranged from ~165 to ~310 ms — this machine was busy.)

JavaScript has the same physics. A Float64Array is one flat block of numbers, so we store row r starting at index r * N:

const N = 4096;
const grid = new Float64Array(N * N);       // one contiguous block, row-major
for (let i = 0; i < grid.length; i++) grid[i] = i % 10;

function sumRows() {
  let s = 0;
  for (let r = 0; r < N; r++)
    for (let c = 0; c < N; c++) s += grid[r * N + c]; // ← neighbour
  return s;
}
function sumCols() {
  let s = 0;
  for (let c = 0; c < N; c++)
    for (let r = 0; r < N; r++) s += grid[r * N + c]; // ← 32 KB jump
  return s;
}

for (const f of [sumRows, sumCols]) {
  f();                                  // warm up, so V8 compiles it to fast code first
  const t = performance.now();
  f();
  console.log(f.name, (performance.now() - t).toFixed(0), "ms");
}

$ node grid.mjs
sumRows 45 ms
sumCols 161 ms

About 3.6× slower in Node 22 on this machine. The rule doesn't care about the language: make the inner loop walk memory in order.

Pointer chasing: slices vs linked lists

A linked listLinked listA list where each item (a “node”) stores a value plus a pointer to the next node. Nodes can be anywhere in memory, so walking the list jumps around. stores each value in its own small object, a node, together with a PointerPointer (*T, &v)A value that holds the memory address of another value instead of a copy of it. In Go, &v takes v's address and *T is the type “pointer to T”; changes made through a pointer are seen by everyone holding it. JS objects behave like this automatically. to the next node:

type Node struct {
    Val  int64
    Next *Node // address of the next node, or nil at the end
}

func sumList(head *Node) (s int64) {
    for n := head; n != nil; n = n.Next { // ← must load n before we know n.Next
        s += n.Val
    }
    return s
}

func sumSlice(vals []int64) (s int64) {
    for _, v := range vals { // ← next address is simply "+8 bytes"
        s += v
    }
    return s
}

The difference that matters is in the comments. For the slice, the CPU knows the next address in advance (it's just 8 bytes further), so the prefetcherHardware prefetcherA circuit in the CPU that watches your memory accesses, spots a pattern (e.g. “address +64 every time”), and starts loading the next cache lines before you ask for them. — a circuit that loads lines ahead of you, more in §06 — can fetch lines before the loop gets there. For the list, the next address is inside the node you're still waiting for.

Misses can wait together — unless they depend on each other

To see why that matters, you need one fact about CPUs: a core doesn't stop at a cache miss. Thanks to out-of-order executionOut-of-order executionThe CPU keeps running later instructions while an earlier one waits (for example on a cache miss), as long as they don't need its result. That's what lets several misses wait at the same time., it keeps going with later instructions that don't need the missing value. If those include more reads whose addresses it already knows, it sends those requests too. A modern core can have 10 or more RAM requests in flight at once, so their ~100 ns waits overlap. That's called memory-level parallelismMemory-level parallelismA core can have many memory reads in flight at once (often 10 or more) when it already knows their addresses, so their waits overlap. Pointer chasing prevents this: each address is only known when the previous read arrives..

Pointer chasing takes that away: the next address is only known when the current read arrives, so there's nothing else to send. Press play and compare the two lanes:

Following a chain like this is called pointer chasingPointer chasingFollowing a chain of pointers (a linked list, a tree) where you can't know the next address until you've loaded the current item. Each hop can be a full cache miss, and the CPU can't overlap them., and it forces the misses to happen strictly one after another. Here's what that looks like in memory:

Measured

Four million int64s, summed three ways on this machine. “In order” means the nodes were allocated one after another, so they happen to sit next to each other in memory. “Shuffled” is the same list after its nodes were linked in random order — which is what a long-lived list looks like after many inserts and deletes:

Even the in-order list is ~10× slower than the slice: nodes are twice as big (value + pointer), and each step still has to wait for the previous load before it knows where to go next.

The everyday version: []*T

You rarely write linked lists, but you write this all the time:

users := []*User{}       // each element: 8-byte address
for _, u := range users {
    total += u.Balance   // ← jump to wherever *u lives
}

users := []User{}        // elements stored inline
for i := range users {
    total += users[i].Balance // ← next one is right after
}

A []*User is a contiguous array of addresses; the User structs themselves live wherever they were allocated on the HeapHeapMemory for data that must outlive a single function call. Unlike the call stack, nothing is thrown away automatically when a function returns.. Walking it is a mild form of pointer chasing. A []User keeps the structs themselves side by side.

JavaScript arrays of objects are the same story: the array holds references, and each object lives on the heap. V8 often places objects allocated together near each other, so a freshly built array is usually fine — but there's no guarantee once the garbage collector has moved things around. For big numeric data, typed arrays (§05) give you real contiguity.

Data layout: struct of arrays, hot/cold fields, padding

Array of structs vs struct of arrays

The natural way to store a million particles in a game or simulation is a slice of structs:

// Array of structs (AoS): each element holds every field.
type Particle struct {
    X, Y, Z    float64
    VX, VY, VZ float64
    Mass       float64
    Alive      bool
}                        // 7×8 + 1 = 57 bytes, padded to 64
var ps []Particle

// Struct of arrays (SoA): one slice per field.
type Particles struct {
    X, Y, Z    []float64
    VX, VY, VZ []float64
    Mass       []float64
    Alive      []bool
}

Both hold the same data. They differ in what sits next to what in memory — the topic of AoS vs SoAAoS vs SoAArray of structs (AoS): []Particle, each element holds all fields side by side. Struct of arrays (SoA): one slice per field (all Xs together, all Ys together). SoA wins when a loop reads only a few fields.. Now a loop that only needs one field, say to compute the average X position:

var s float64
for i := range ps { s += ps[i].X } // AoS: X is 8 bytes out of every 64
for _, x := range p.X { s += x }   // SoA (p is a Particles): nothing but Xs

Toggle between the two layouts to see what each loop drags through the cache:

The measured numbers on this machine (1,048,576 particles, sum of every X):

$ go test -bench 'SumX'
BenchmarkAoSSumX-4   	     373	   3170259 ns/op
BenchmarkSoASumX-4   	    1880	    612061 ns/op

That's ~3.2 ms vs ~0.61 ms (over several runs, AoS ranged 2.7–4.6 ms; SoA stayed at ~0.6 ms).

About 5× faster with SoA, because the loop moves 8 MB through the caches instead of 64 MB. The same thing in JavaScript: an array of objects versus one Float64Array per field.

const P = 1 << 20;                                   // 1,048,576
const objs = Array.from({ length: P }, (_, i) =>
  ({ x: i, y: i, z: i, vx: i, vy: i, vz: i, mass: i }));
const xs = new Float64Array(P).map((_, i) => i);     // just the x column

function sumObjs() { let s = 0; for (let i = 0; i < P; i++) s += objs[i].x; return s; }
function sumXs()   { let s = 0; for (let i = 0; i < P; i++) s += xs[i];     return s; }
// warmed up, then averaged over 10 calls: sumObjs ~4.4–5.7 ms, sumXs ~1.0–1.1 ms (Node 22, this machine)

This way of thinking — design the data around how the hot loops read it — is called data-oriented designData-oriented designDesigning data structures around how the hot loops actually read memory — contiguous arrays, only the needed fields, processed in batches — rather than around object hierarchies.. Game engines (entity-component systems), columnar databases (§10) and machine-learning libraries are built on it.

Field order and padding in Go

A smaller struct also means more per cache line. Go lays out fields in the order you write them, and adds paddingAlignment / paddingCPUs read values fastest at addresses that are multiples of their size, so compilers insert unused “padding” bytes between struct fields. Field order changes a struct's size. so that each field starts at an address that's a multiple of its size (on 64-bit machines, an int64 must start on an 8-byte boundary):

type Bad struct {
    Active bool  // 1 byte
    ID     int64 // 8 bytes
    Admin  bool  // 1 byte
    Score  int64 // 8 bytes
}

type Good struct {
    ID     int64
    Score  int64
    Active bool
    Admin  bool
}

fmt.Println("Bad: ", unsafe.Sizeof(Bad{}))
fmt.Println("Good:", unsafe.Sizeof(Good{}))
fmt.Println("offset of Bad.ID:", unsafe.Offsetof(Bad{}.ID))

$ go run sizes.go
Bad:  32
Good: 24
offset of Bad.ID: 8

The rule: order fields from largest to smallest and padding mostly disappears. A million Bads is 32 MB; a million Goods is 24 MB — 25% less memory to move. The fieldalignment analyzer (from golang.org/x/tools) can find such structs for you.

Don't reorder everything on sight, though: the order you write fields in is also documentation. Do it for structs you keep millions of, or that sit in a hot loop.

Prefetching: why big arrays can still be fast

Here's a puzzle from §03. The row-order sum read a 128 MB grid — way bigger than L1 or L2 — yet averaged about 1.5 ns per number. If every new cache line cost a full RAM trip (~100+ ns), that would be impossible: 100 ns ÷ 8 numbers per line is already 12 ns each.

Part of the answer is memory-level parallelismMemory-level parallelismA core can have many memory reads in flight at once (often 10 or more) when it already knows their addresses, so their waits overlap. Pointer chasing prevents this: each address is only known when the previous read arrives. from §04: the loop's addresses are known in advance, so many misses wait at the same time. The other part is the hardware prefetcherHardware prefetcherA circuit in the CPU that watches your memory accesses, spots a pattern (e.g. “address +64 every time”), and starts loading the next cache lines before you ask for them.. It watches the stream of misses, notices “line 1000, 1001, 1002…”, and starts requesting 1003, 1004, 1005 while your loop is still busy with 1002. The waiting overlaps with the work, so the loop is limited by memory bandwidthMemory bandwidthHow many bytes per second can flow between RAM and the CPU (tens of GB/s on a typical server core). Streaming through a big array is limited by bandwidth; jumping around is limited by latency. (how many bytes per second can flow) instead of latency (how long one read takes).

Measured: what stride costs

To see the prefetcher at work, read every k-th element of a 256 MB []int64 in a single pass, and divide the time by the number of reads:

var sink int64 // package-level, so the compiler can't drop the loop (§12)

func pass(big []int64, stride int) {
    var s int64
    for i := 0; i < len(big); i += stride { // stride is in elements; ×8 = bytes
        s += big[i]
    }
    sink += s
}

How to read it, left to right:

1. 8 → 64 bytes: the cost per read grows because fewer reads share each line. At 8 bytes, 8 reads split one line's cost; at 64 bytes, every read pays for a whole line by itself.
2. At 64 bytes every read needs a fresh line — yet it's only ~5 ns, not 100+. The prefetcher is loading ahead.
3. Beyond ~256 bytes it plateaus around 10–17 ns. Each read now costs about one full line transfer, but many transfers are in flight at once (the addresses are known in advance, and the prefetcher helps too), so each read pays only a fraction of the ~100 ns RAM latency.

Random isn't the problem. Dependent is.

It's tempting to conclude “sequential = fast, random = slow”. The real dividing line is whether the CPU knows the next address before the current read finishes. Here are four ways of reading the same 256 MB array on this machine:

for i := range big { s += big[i] }      // sequential
for i := 0; i < len(big); i += 8 { s += big[i] } // fixed stride, one read per line (the chart above)
for _, k := range idx { s += big[k] }   // independent random: idx is a pre-shuffled list of positions
for i := 0; i < hops; i++ { p = big[p] } // dependent random: each value is the next position

So a loop that gathers many unrelated positions from a big array is much less bad than you might fear — around 20 ns per miss here — while walking a linked list or a tree through RAM really does pay the full ~100–250 ns on every hop.

Hash maps sit in between. One lookup is several reads in a row — find the key's group, then compare keys, then read the value — and each step needs the previous one's result, plus a hard-to-predict branch or two. Measured on this machine: random lookups in a Go 1.24 map[int64]int64 with 8 million entries took ~80–100 ns each. Still cheaper than a full pointer chase per lookup, but ~4× the array gather.

The practical lesson is the same as §03, one level up: sequential is king. A plain loop over a slice is the fastest way to visit a lot of data, even data far bigger than the cache. And when access must be random, keep the reads independent — gather the positions first, then read — instead of chaining them through pointers.

Working set: the cache staircase

The memory a piece of code keeps touching is its working setWorking setThe memory a piece of code actively touches during some stretch of time. If it fits in a cache level, the code runs at that level's speed.. A loop over a 20 KB lookup table has a 20 KB working set: it fits in L1, so every read is ~1 ns. Grow the table to 20 MB and the very same code reads from L3 or RAM.

Measuring the staircase

To see each cache level's full latency, we need reads that can't be prefetched or overlapped (§04, §06) — otherwise several misses would wait together and hide it. So we make every read dependent on the previous one: build one random cycle through the array, where each 64-byte line stores the index of the next line to visit. Then just follow it:

// Setup (not shown): shuffle the line numbers 0..n-1, then make each line
// point to the next one in the shuffled order, and the last back to the first.
// buf[p*16] is the next line's index; 16 uint32s = 64 bytes = one line per hop.
p := uint32(0)
for i := 0; i < hops; i++ {
    p = buf[p*16] // ← can't start until the previous load finishes
}

This is pointer chasing (§04) on purpose: each address depends on the previous read, so we time one full miss at a time. Repeat for arrays from 4 KB to 512 MB and plot the time per hop:

The steps line up with the cache sizes from §02:

(Best of 3 runs on this machine. The L2 step comes a little before 2 MB because the array shares L2 with everything else the program touches.)

These are worst-case, one-miss-at-a-time numbers: right for linked lists, trees and hash chains. Independent reads overlap their misses, so they pay much less — §06 measured ~21 ns per independent random read against ~240 ns per dependent one in the same 256 MB array. The positions of the steps are the same either way; only their height changes.

What this means for your code

• Small and hot beats big and clever. A 64 KB lookup table that fits in L2 can beat a “smarter” algorithm whose 50 MB of data lives in RAM.
• Shrink the element, grow the hit rate. Halving your struct size (§05) doubles how many fit in each cache level.
• Look at the cliff, not the average. A service whose hot data is 1.5 MB runs happily; let it grow to 3 MB and pointer-heavy operations can get ~8× slower overnight, with no code change.

Cache coherence: MESI in plain words

Every core has its own L1 and L2 (§02). So what happens when core 1 changes x while core 2 has an old copy of x in its cache? Without help, core 2 would keep reading the stale value forever.

The CPU prevents this in hardware with cache coherenceCache coherenceThe hardware protocol that keeps every core's private cache consistent, so two cores never keep different values for the same address forever. It's automatic, but it costs time when cores write to the same cache line.: a protocol that tracks, for every line in every core's cache, who has a copy and whether it's been changed. The textbook version is MESIMESIThe classic cache-coherence protocol. Every cache line in every core is in one of four states: Modified (only I have it, and I changed it), Exclusive (only I have it, unchanged), Shared (others may have a copy, read-only) or Invalid (my copy is stale — don't use it)., named after the four states a line can be in, from one core's point of view:

The rule that follows: a write needs exclusive ownership. To write a Shared line, a core sends an “invalidate” message to all the others and waits until they've dropped their copies. Step through it:

Why this matters to you

Coherence is automatic and always correct; you never call it. But it has a cost model you can design around:

• Many readers, no writers: free. Every core keeps a Shared copy. That's why read-only data (a config loaded once, a lookup table) scales perfectly across cores.
• One writer, mostly alone: cheap. The line stays Modified in that core.
• Several cores writing the same line: expensive. Each switch of writer moves the line between cores — tens of nanoseconds instead of one. This is the cache-line ping-pong you met in Locks §07, and it's why a single hot atomic counter or mutex stops scaling.

The surprising part — that this happens even when the cores write different variables — is §09.

False sharing, measured

Locks §10 warned about this in one paragraph. Now that you know MESI (§08), here's the full picture, with numbers.

The setup

Four goroutines each count events into their own counter. No counter is shared, so there's no race and no lock. It should scale perfectly across 4 cores:

const workers = 4
const perWorker = 5_000_000

type Adjacent struct {
    n [workers]atomic.Int64 // 4 × 8 bytes = 32 bytes: one cache line
}

func BenchmarkAdjacent(b *testing.B) {
    for b.Loop() {
        var c Adjacent
        var wg sync.WaitGroup
        for w := range workers {
            wg.Add(1)
            go func() {
                defer wg.Done()
                for range perWorker {
                    c.n[w].Add(1) // ← each goroutine touches only its own counter
                }
            }()
        }
        wg.Wait()
    }
}

All four counters sit inside one 64-byte line. Every Add needs that line in Modified state (§08), which steals it from whichever core had it. The cores spend most of their time waiting for the line to come back. Run the toy model:

The fix: give each counter its own line

type paddedInt struct {
    atomic.Int64          // the counter (8 bytes)
    _ [56]byte            // filler: 8 + 56 = 64 bytes, one cache line each
}

type Padded struct {
    n [workers]paddedInt  // c.n[w].Add(1) works exactly the same
}

$ go test -bench . -count 3
BenchmarkAdjacent-4   	       4	 271592000 ns/op
BenchmarkAdjacent-4   	       4	 321379632 ns/op
BenchmarkAdjacent-4   	       4	 302258801 ns/op
BenchmarkPadded-4     	      20	  54321745 ns/op
BenchmarkPadded-4     	      24	  56908313 ns/op
BenchmarkPadded-4     	      27	  46028901 ns/op

~300 ms vs ~54 ms: about 5.5× faster, from adding 224 bytes of nothing (4 × 56). And it gets worse the more cores fight. An earlier run on this machine with 1, 2 and 4 workers:

(Each worker always does 5 million adds, so with perfect scaling every bar would stay at ~34 ms. This machine was also running other jobs, so “padded” doesn't reach the ideal.)

Where it hides in real code

• Per-worker stats in an array or slice: stats []WorkerStats where each worker updates stats[i]. Small structs → several per line.
• Sharded locks: [16]struct{ mu sync.Mutex; m map[K]V } from Locks §10 — each shard is only 16 bytes, so 4 shards share each line.
• A hot field next to a read-mostly field in one struct: a request counter that's incremented constantly sits next to a config pointer every goroutine reads. The reads now keep missing, because every increment invalidates their copies.

The other fix is not to share at all: let each goroutine count in a local variable and add it to the shared total once at the end — the “one counter per core” idea from Locks §07. A local lives in a register or on that goroutine's own stack, never next to another core's data.

JavaScript: only with real shared memory

Plain JavaScript can't false-share, because each worker thread has its own memory and messages are copied (Threads & Processes). It appears the moment you use a SharedArrayBuffer + AtomicsSharedArrayBuffer + AtomicsA block of raw bytes that several JS threads can see at the same time (real shared memory). Atomics gives safe operations on it, like an increment that can't be interrupted halfway.:

const PAD = 16;                                            // 16 × 4 bytes = 64 bytes
const shared = new Int32Array(new SharedArrayBuffer(4 * 4 * PAD));

// in worker number `id` (0–3):
Atomics.add(shared, id * PAD, 1); // ← counters 64 bytes apart: one line each
// Atomics.add(shared, id, 1);    // ← all four in one line: false sharing

Same physics, same fix: space the indices one cache line apart. (How to share the buffer with workers and use Atomics safely is in Locks §09.)

Choosing data structures with caches in mind

Small N: a slice can tie a map

A hash mapHash mapA key → value table (Go's map, JS's Map) that turns each key into a number with a hash function and uses it to jump straight to a slot. Lookups take about the same time however big it gets. lookup is O(1): hash the key, jump to a slot. A linear scan of a slice is O(n). So the map always wins? Here's a real benchmark looking up int keys on this machine (Go 1.24):

_, ok = m[key]                        // map[int]bool
ok = slices.Contains(keys, key)       // linear scan of []int
_, ok = slices.BinarySearch(keys, key) // keys is sorted

Two honest lessons:

• Up to a handful of keys, the slice ties. 8 ints are 64 bytes: one cache line. Scanning it costs about as much as hashing. If the data is tiny and mostly read, a sorted slice is simpler, uses less memory and iterates in a fixed order.
• Go's map is very cache-friendly. Since Go 1.24, maps are “Swiss tables”, which keep keys in compact groups and check 8 slots at once. The linear scan loses badly by 128 keys. Don't replace maps with slices on a hunch — measure.

Why databases use B-trees, not binary trees

A binary search treeBinary search tree (BST)A sorted tree where every node holds one key and two pointers (smaller keys to the left, bigger to the right). Finding a key among a million takes ~20 hops — each one a pointer to chase. holding a million keys is about 20 levels deep. Every level is a separate node somewhere on the heap — 20 rounds of pointer chasing (§04), most of them cache misses.

A B-treeB-treeA wide, shallow, always-sorted tree that most databases use for tables and indexes. Each node fills one disk page and holds hundreds of keys, so finding one row among millions takes only 3–4 page reads. stores hundreds of sorted keys per node. The same million keys fit in a tree only 3 levels deep. Inside each node the keys are contiguous, so searching them reads neighbouring cache lines (or neighbouring bytes of one disk page) — cheap. You trade a few extra comparisons for far fewer jumps.

That's exactly why databases use them on disk (Indexes §03), and why in-memory B-tree libraries (like github.com/google/btree in Go) often beat red-black trees for big sorted sets.

Sequential beats random, all the way down

The same idea repeats at every level of the storage stack, with bigger numbers. Disks and SSDs, like caches, are much faster at Sequential vs random I/OSequential vs random I/OSequential I/O reads or writes one long run of neighbouring bytes; random I/O touches small pieces scattered all over the disk. Disks (especially spinning ones) are many times faster at sequential I/O. than at jumping around:

• LSM trees turn random writes into sequential ones: buffer in memory, then write sorted files in one long stream. That's the whole design of LSM Trees.
• Columnar formats (Parquet, ClickHouse, DuckDB) are SoA (§05) for tables: columnar storageColumnar storageStoring a table column by column (all prices together, all dates together) instead of row by row. Analytics queries that read a few columns of millions of rows then scan one tight, contiguous run of bytes. Parquet, ClickHouse and DuckDB work this way. keeps each column contiguous, so SELECT avg(price) streams one column through the cache and skips the rest.

Staff-level: branch prediction, the TLB and NUMA

Branch prediction: sorted data is faster data

A core works on many instructions at once, like an assembly line. When it reaches an if, it doesn't wait to find out which way it goes: branch predictionBranch predictionThe CPU guesses which way an if will go and starts working on that path before it knows for sure. A right guess is free; a wrong guess throws away the work, costing roughly 15–20 clock cycles. guesses, and the core keeps going down that path. Guess right: free. Guess wrong: throw away the half-done work and restart — roughly 15–20 cyclesCPU cycleOne tick of the processor's clock. At 3 GHz a cycle is a third of a nanosecond; a simple instruction takes about one cycle, a read from RAM a few hundred..

Predictors learn patterns. If the condition follows a pattern (“always true”, “false, then true from here on”), they're nearly always right. If it's random, they're wrong about half the time. The same loop over the same numbers, sorted vs not:

func countBig(v []int64) (s int64) {
    for _, x := range v {
        if x >= 128 {      // ← random data: a coin flip the predictor can't learn
            s += x
            s ^= s << 1    // a bit of extra work (see the callout below)
        }
    }
    return s
}

About 5× faster, from sorting. The general lesson: grouping similar items (all the active ones, then the inactive ones) helps the branch predictor and the cache.

The TLB: a cache for addresses

Your program's addresses are virtual: the CPU translates each one to a physical address through the page tablePage table (and pages)Memory is handled in chunks called pages (usually 4 KB). A page table is the per-process lookup table that says “virtual page X lives at physical RAM spot Y”. The CPU consults it on every memory access., page by page (pages are usually 4 KB). Doing that lookup on every access would be slow, so the CPU caches recent translations in the TLBTLBTranslation lookaside buffer: a small cache inside the CPU that remembers recent page-table lookups, so translating an address is usually instant. — typically a few thousand entries, covering only a few MB of 4 KB pages.

So jumping around a big working set misses twice: once in the data cache, once in the TLB. That's part of why the staircase in §07 kept rising past ~16 MB. The fixes are the same as for caches — touch fewer pages, more sequentially — plus huge pages (2 MB instead of 4 KB, so each TLB entry covers 512× more). Linux can use them automatically (“transparent huge pages”) for big heaps. The full story of pages and translation is in Virtual Memory §04, and huge pages and NUMA from the OS side in Virtual Memory §11.

NUMA: memory has a location

On a laptop, all RAM is equally far from every core. Big servers often have two or more CPU sockets, each with its own RAM attached. A core reading memory attached to its own socket is fast (“local”); reading memory attached to the other socket goes over a link between the chips and is noticeably slower (“remote”, often ~1.5–2× the latency). That's NUMANUMA (non-uniform memory access)On big servers with several CPU sockets, each socket has its own RAM. Memory attached to your own socket is “local” and fast; memory attached to another socket is “remote” and noticeably slower..

$ lscpu | grep -i numa      # the machine used for this page: one node, so no NUMA effects
NUMA node(s):                            1
NUMA node0 CPU(s):                       0-3

On a multi-socket box, numactl --hardware shows the nodes and the relative distances between them. What changes in practice:

• Linux allocates memory on the node of the core that first touches it (“first touch”). Data initialised by one thread and then processed by threads on the other socket is remote for all of them.
• Databases and JVM-style runtimes have NUMA settings (interleave memory, pin threads per socket). Go and Node don't do anything NUMA-specific; the usual production answer is to run one process per socket, pinned with numactl --cpunodebind=0 --membind=0 ./app or with container CPU sets, or simply to use smaller VMs that fit in one socket.
• Cloud VMs larger than one socket expose NUMA too. If a 96-core VM scales worse than two 48-core ones, check lscpu.

Pitfalls, measuring, and when to care

Five design pitfalls

Three ways benchmarks lied while writing this page

All three happened for real while measuring the numbers in this topic.

Finding the hot loop: pprof

The Go ProfilerProfilerA tool that measures where a program spends its time or memory (e.g. Go's pprof, Chrome DevTools, perf), usually by sampling what's running many times per second. tells you where time goes, not why. Cache misses show up as surprising amounts of time on lines that do almost nothing — a simple load or add:

$ go test -bench SumCols -run '^$' -cpuprofile cpu.out
$ go tool pprof -list 'sumCols' cpu.out
ROUTINE ======================== cc.sumCols in …/cache_test.go
     1.01s      1.01s (flat, cum) 27.30% of Total
         .          .     38:	for c := 0; c < len(g[0]); c++ {
     970ms      970ms     39:		for r := 0; r < len(g); r++ {
      40ms       40ms     40:			s += g[r][c]

(Real output, path shortened. -run '^$' matches no test names, so only the benchmark runs. This profile came from an earlier version of §03's code in a file called cache_test.go, where sumCols starts on line 36.) Notice that the time lands on line 39, the loop header, not on the load in line 40. Sampling profilers often charge a slow instruction's cost to a neighbouring line (“skid”). Read pprof's line numbers as “around here”. In Node, node --cpu-prof app.js or Chrome DevTools' Performance panel gives the same kind of view for JavaScript.

Finding out why: perf stat

On Linux, perfperf (Linux)A Linux command-line profiler that can read the CPU's hardware counters — cache misses, branch misses, instructions per cycle — for any program, e.g. perf stat -e cache-misses ./app. reads the CPU's hardware counters, which count cache misses, branch misses and instructions per cycle directly:

$ perf stat -e cycles,instructions,cache-references,cache-misses,branch-misses ./app

The machine used for this page doesn't have perf (and many cloud VMs and containers don't expose hardware counters at all), so there's no real output to show. What to look at when you can run it: instructions per cycle (below ~1 on a hot loop usually means it's waiting for memory), the cache-miss rate, and branch-misses. perf c2c goes further and points at cache lines bouncing between cores — the tool for confirming false sharing (§09).

When it matters — and when it doesn't

The habits that are always free — iterate slices in order, prefer []T over []*T for small structs in big collections, keep hot structs small, don't share written data between goroutines — are worth doing by default. Everything else waits for a profile.

Check yourself

Predict the answer before you click. Q1 is covered in §03, Q2 in §09, Q3 in §04, Q4 in §05, Q5 in §07 and Q6 in §12.

// A
for r := 0; r < 4096; r++ {
    for c := 0; c < 4096; c++ { s += grid[r][c] }
}
// B
for c := 0; c < 4096; c++ {
    for r := 0; r < 4096; r++ { s += grid[r][c] }
}

type A struct { ok bool; id int64; on bool }
type B struct { id int64; ok bool; on bool }

var s int64
for i := 0; i < len(big); i += stride {
    s += big[i]
}
// s is never used after this

Cheat sheet