sdlc.dev

Computer science fundamentals for working engineers path · Inside the machine · Topic 2 of 13

The memory hierarchy and caches

Not started

A CPU core can do several operations per nanosecond, but fetching a value from main memory (DRAM) takes on the order of 100 nanoseconds. Without help, the core would spend almost all its time waiting. The help is a hierarchy of caches: small, fast memories next to the core that keep copies of recently used data. When the data is in cache, a load takes a few cycles; when it isn't, the core stalls. Whether your code is fast is often decided by how it walks through memory.

Why it matters: Most code is limited by memory, not arithmetic. Knowing how caches work explains why arrays beat linked lists and why the loop order can change speed several times over.

  1. 1A ladder of speeds

    Registers, then L1, L2 and L3 cache, then main memory, then SSD and network. Each step down is bigger and slower, by up to orders of magnitude.

  2. 2Cache lines

    Memory moves in blocks of 64 bytes on most current CPUs. Reading one byte brings its neighbours along for free.

  3. 3Locality wins

    Code that touches nearby addresses (spatial locality) or the same data again soon (temporal locality) mostly hits the cache.

  4. 4Prefetching rewards patterns

    The hardware spots sequential or strided access and fetches ahead. Pointer chasing defeats it, because the next address isn't known until the load finishes.

1

How it works

The explanation, with examples you can run.

The ladder

Approximate figures for a current desktop or server core (they vary by chip and change slowly):

LevelTypical sizeTypical latency
Registersa few hundred bytes0 to 1 cycle
L1 cache (per core)32 to 64 KB of dataabout 1 ns (4 to 5 cycles)
L2 cache (per core)1 to 2 MBabout 3 to 5 ns
L3 cache (shared)tens of MBabout 10 to 20 ns
Main memoryGBsabout 80 to 120 ns
NVMe SSD readTBstens of microseconds
Round trip in one data centreabout 0.5 ms

The jump from cache to RAM is the one that matters for ordinary code. Two more facts make it manageable. Memory moves in cache lines, usually 64 bytes: load one double and the next seven come with it. And hardware prefetchers watch the addresses you load; if they see a sequential or regular stride, they fetch lines before you ask.

Locality, measured

A 2048 × 2048 grid of doubles stored row after row in one array is 32 MB, larger than the caches. Summing it in two orders:

⌘/Ctrl + Enter
OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

On a Mac laptop with Node 22, row order took 3 to 5 ms and column order 10 to 14 ms over several runs. The arithmetic is identical. Row order uses all 8 values of every cache line it loads and gives the prefetcher a simple pattern; column order uses one value per line and jumps 16 KB at a time. The gap depends on the machine (big caches and clever prefetchers narrow it), so run it yourself.

Why arrays beat linked lists

A linked list stores each node in its own allocation, wherever the allocator put it. Walking the list means loading a node to learn the address of the next one, so each step can be a full cache miss, and the prefetcher can't help because the next address isn't known until the current load completes. An array of the same values streams through memory at full speed. That is why dynamic arrays, hash tables with open addressing, and B-trees (wide nodes, few pointer hops) dominate real systems, as the data structures path shows.

The same ideas apply higher up the ladder: a database page cache, a CDN and an in-process memoisation map are all caches that pay off only when access has locality.

2

Check yourself

3 questions. Get them all right to finish this topic.

  1. 1.Roughly how much slower is a read from main memory than from L1 cache?
  2. 2.Summing a 2048 × 2048 grid stored row by row, why is the row-by-row loop faster than column-by-column?
  3. 3.Why does iterating a linked list usually lose to iterating an array of the same values, even though both are O(n)?

0 of 3 right so far. Get all three to finish this topic.

Go deeper