The Memory Hierarchy (cache, locality, the memory wall)

The small, fast copies of memory a CPU keeps close, stacked in front of the huge, slow warehouse everyone calls RAM. Follows The CPU (fetch-decode-execute, the ISA, assembly), which left open how far the fetch step reaches for its data; this lesson is that gap, and the one thing you control about it.

Before you start. The CPU (fetch-decode-execute, the ISA, assembly) gave you the loop: fetch, decode, execute, using registers built into the chip. Almost every step eventually needs data from outside the chip, and how far away that data lives is the whole subject here. If a linked list is new, Linked Lists, Stacks & Queues in DSA shows it in one read.

The idea in 30 seconds

RAM is far slower than the processor asking it for data, so a computer keeps a chain of small, fast copies in front of it, ending in the cache Wilkes proposed in 1965 and IBM first shipped in 1968.
A cache is fast because it is small, and small because fast memory is expensive; that is why there are several levels instead of one.
Memory moves in whole blocks, cache lines, never single bytes, so reading one value drags its neighbours along for free.
A hit answers from the fast rung; a miss drops down a rung, and one miss can cost a hundred times what one hit does.
Locality is the one thing you control: touch the same data again soon, or touch data sitting next to what you just touched, and the hierarchy rewards you; scatter your reads and it punishes you.
Where your data lives, not how clever your code is, decides most of what “slow” means in practice.

Read the story · Skip to the numbers