Below the API

Cache-Friendly Data

Advanced Advanced 55 min Difficulty 4/5

Prerequisites II.04, IV.04, 01

The idea in one minute#

A CPU can execute several instructions per nanosecond, but fetching a value from main memory takes around a hundred nanoseconds. Between the two sit caches: small, fast copies of recently used memory, loaded 64 bytes — one cache line — at a time. A program that walks memory in order gets nearly every access from cache. One that hops around pays the full price again and again.

So the layout of your data often matters more than the number of instructions: contiguous beats scattered, compact beats padded, and two goroutines writing to the same cache line slow each other down even when they touch different variables (false sharing).

An analogy#

Cooking with ingredients on the counter versus in a cellar down the street. Whatever is on the counter is instant. Each trip to the cellar is slow, but you bring back a whole crate — so if the next thing you need was in the same crate, it is already on the counter. A recipe that uses neighbouring items from one crate is fast; one that needs a single item from each of a hundred crates is not.

A picture#

flowchart TB
  CPU["CPU core"] --> L1["L1: ~48 KB, ~1 ns"]
  L1 --> L2["L2: ~1-2 MB, ~4 ns"]
  L2 --> L3["L3: tens of MB, shared, ~15-40 ns"]
  L3 --> RAM["Main memory: ~80-120 ns"]
  subgraph AOS["Array of structs: 64 bytes each, you need one field"]
    direction LR
    P0["id, name, score, flags ..."] --- P1["id, name, score, flags ..."] --- P2["..."]
  end
  subgraph SOA["Struct of arrays: scores packed together"]
    direction LR
    S0["score score score score score score score score ..."]
  end
  AOS -->|"1 useful value per cache line"| SLOW["many misses"]
  SOA -->|"16 useful values per cache line"| FAST["few misses, prefetcher helps"]
  class CPU compute
  class L1,L2,L3,RAM memory
  class P0,P1,P2 neutral
  class S0 compute
  class SLOW warn
  class FAST queue

How it really works#

The numbers that matter#

AccessApproximate cost
L1 cache hit1 ns
L2 hit3–5 ns
L3 hit15–40 ns
Main memory80–120 ns
Mispredicted branch3–5 ns
Cache line64 bytes (128 on Apple silicon)

A sequential scan triggers the hardware prefetcher, which fetches the next lines before you ask. Random access defeats it. The difference between the two, over data larger than the cache, is commonly 10× or more for the same number of operations.

Rules that follow#

1. Prefer slices of values to slices of pointers. []Item is one contiguous block; []*Item is a block of addresses pointing at objects scattered across the heap — a potential miss per element, plus work for the garbage collector.

2. Flatten. A matrix as one []float32 with i*cols+j indexing is contiguous. As [][]float32 it is a pointer per row (II.01).

3. Keep hot fields together and cold fields apart. If a loop reads only score from a 64-byte struct, each cache line delivers one useful value. Options:

  • Struct of arrays (SoA): scores []float32, ids []int64 as parallel slices. Sixteen scores per line; ideal for scans and for vector instructions.
  • Hot/cold split: a compact struct with the fields the inner loop needs, and an index to the rest.

4. Shrink. int32 instead of int when values fit, float32 instead of float64, uint8 codes instead of strings, bit sets instead of []bool. Half the bytes is half the misses.

5. Walk in memory order. For a row-major matrix, loop rows outside and columns inside. In matrix multiplication the classic i, j, k order strides down a column of the second matrix — a miss per step; i, k, j walks both operands along rows.

6. Block (tile) large computations. Process a chunk that fits in cache completely before moving on. This is what turns a naive matrix multiply into a fast one (Inference Engineering IV.03).

7. Linear search beats clever structures at small sizes. Scanning 16 integers in a slice is faster than a map lookup or a tree walk: no hashing, no pointers, one cache line.

False sharing#

Cache lines are the unit of ownership between cores. When one core writes a line, every other core’s copy is invalidated. If two goroutines repeatedly write different variables that sit in the same line, the line bounces between cores on every write — each write becomes a cross-core transfer of tens of nanoseconds. Nothing is logically shared; the hardware disagrees.

Typical cases: per-worker counters in adjacent slice elements; two hot atomics declared next to each other in a struct; a mutex beside the data another goroutine reads constantly.

The fix is padding so that each writer’s data occupies its own line:

type counter struct {
    n atomic.Int64
    _ [56]byte           // 8 + 56 = 64: one line each
}

The standard library does this internally (sync.Pool’s per-P slots, the runtime’s per-P structures). Pad only what a profile shows is contended — padding everything wastes the cache you are trying to protect.

True sharing#

When goroutines really do write the same variable — a shared counter, a lock — the line bounces for a legitimate reason. That is why a contended atomic costs tens of nanoseconds instead of one (IV.04’s counter program). The remedy is the same as for any contention: stop sharing — per-goroutine or per-P state, merged occasionally.

Other effects, briefly#

  • Branch prediction. A branch that goes the same way, or follows a pattern, is nearly free. A data-dependent, unpredictable one costs a pipeline flush. Sorting data, or replacing a branch with arithmetic, can speed a loop several-fold.
  • TLB. Address translation is cached too. Huge heaps touched randomly miss the TLB; transparent huge pages help, and so does locality.
  • NUMA. On multi-socket servers, memory attached to the other socket is slower. Go’s runtime is not NUMA-aware; pin the process to one node when it matters.

In AI code#

Weights and activations are large []float32 arrays walked sequentially — the best case, as long as you keep it that way. The costs come from the surroundings: token IDs as []int (8 bytes) instead of []int32; per-token structs with a string and a pointer; [][]float32 embeddings; a vector index as a graph of heap nodes. Module VI’s tensor, tokenizer and vector index are all flat arrays for this reason.

Code#

// cache.go — sequential vs random access, AoS vs SoA, loop order, and false sharing.
package main

import (
	"fmt"
	"math/rand"
	"runtime"
	"sync"
	"sync/atomic"
	"time"
)

type Record struct { // 64 bytes: one cache line
	ID    int64
	Score float32
	_     [52]byte // the "cold" fields a scan does not need
}

func timeIt(f func()) time.Duration {
	start := time.Now()
	f()
	return time.Since(start)
}

func main() {
	rng := rand.New(rand.NewSource(1))

	// 1. Same additions, different order of access.
	const n = 1 << 23 // 8M int64 = 64 MB: far larger than the cache
	data := make([]int64, n)
	seq := make([]int32, n)
	for i := range seq {
		seq[i] = int32(i)
	}
	rnd := make([]int32, n)
	copy(rnd, seq)
	rng.Shuffle(n, func(i, j int) { rnd[i], rnd[j] = rnd[j], rnd[i] })
	var sum int64
	ts := timeIt(func() {
		for _, i := range seq {
			sum += data[i]
		}
	})
	tr := timeIt(func() {
		for _, i := range rnd {
			sum += data[i]
		}
	})
	fmt.Printf("sum 8M values: sequential %.1f ns/elem, random %.1f ns/elem  (%.0fx)\n",
		float64(ts.Nanoseconds())/n, float64(tr.Nanoseconds())/n, float64(tr)/float64(ts))

	// 2. Array of structs vs struct of arrays: scan one field.
	const m = 1 << 21
	aos := make([]Record, m)
	soa := make([]float32, m)
	var f float32
	ta := timeIt(func() {
		for i := range aos {
			f += aos[i].Score
		}
	})
	tb := timeIt(func() {
		for i := range soa {
			f += soa[i]
		}
	})
	fmt.Printf("scan 2M scores: array of 64-byte structs %.2f ns/elem, flat []float32 %.2f ns/elem  (%.1fx)\n",
		float64(ta.Nanoseconds())/m, float64(tb.Nanoseconds())/m, float64(ta)/float64(tb))

	// 3. Loop order over a flat matrix.
	const dim = 4096
	mat := make([]float32, dim*dim)
	trow := timeIt(func() {
		for i := 0; i < dim; i++ {
			for j := 0; j < dim; j++ {
				f += mat[i*dim+j]
			}
		}
	})
	tcol := timeIt(func() {
		for j := 0; j < dim; j++ {
			for i := 0; i < dim; i++ {
				f += mat[i*dim+j]
			}
		}
	})
	fmt.Printf("4096x4096 matrix: row order %d ms, column order %d ms  (%.1fx)\n",
		trow.Milliseconds(), tcol.Milliseconds(), float64(tcol)/float64(trow))

	// 4. False sharing: each goroutine has its OWN counter; only the spacing differs.
	workers := min(runtime.GOMAXPROCS(0), 8)
	const iters = 5_000_000
	share := func(stride int) time.Duration {
		counters := make([]atomic.Int64, workers*stride)
		var wg sync.WaitGroup
		start := time.Now()
		for w := 0; w < workers; w++ {
			wg.Add(1)
			go func() {
				defer wg.Done()
				c := &counters[w*stride]
				for i := 0; i < iters; i++ {
					c.Add(1)
				}
			}()
		}
		wg.Wait()
		return time.Since(start)
	}
	adjacent, spaced := share(1), share(16) // 16 x 8 bytes = 128 bytes apart
	fmt.Printf("%d goroutines, private counters: adjacent %d ms, 128 bytes apart %d ms  (%.1fx)\n",
		workers, adjacent.Milliseconds(), spaced.Milliseconds(), float64(adjacent)/float64(spaced))
	_, _ = sum, f
}

Remember this#

  • Memory is loaded 64 bytes at a time; a miss costs ~100 ns against ~1 ns for a hit.
  • Contiguous, compact, sequential: slices of values, flat matrices, struct of arrays, small types.
  • Walk data in the order it is stored; block large computations to fit the cache.
  • False sharing: independent variables on one cache line, written by different cores. Pad what a profile shows is contended.

Try it#

  1. Run cache.go. Which of the four effects was largest on your machine?
  2. Shrink Record to 16 bytes. What happens to the AoS-versus-SoA gap, and why?
  3. Write a naive matrix multiply with loop orders ijk and ikj for 512 × 512 and compare.

Check yourself#

  1. Why is a sequential scan so much faster than random access over the same data?
  2. When is struct-of-arrays better than array-of-structs?
  3. What is false sharing, and why does padding fix it?
esc

↑↓ navigate ↵ open