The Memory Hierarchy

No perfect memory

You’d want storage that’s huge, fast, and cheap. No device is all three: the fast ones are small and expensive, the big ones slow ¹. So every computer combines several kinds, arranged as the memory hierarchy, and moves data between them so that what’s needed now is usually somewhere fast ¹.

The hierarchy

Typical figures for a 2020 workstation ¹:

The numbers are too small to feel, so scale them up: if a register took one second to read, the cache would take 5 seconds, main memory nearly 2 minutes, an SSD a day or more, a hard disk months, and a round trip to a server across the internet years.

Two things set the speeds ¹:

• Distance. Registers sit right beside the ALU; data from a disk travels through several controllers and much longer wires. At these speeds, centimeters matter.
• Technology. Registers and caches are SRAM, a few gates per bit; main memory is DRAM, capacitors that need refreshing; SSDs are flash; hard disks have a spinning platter and a moving arm, which is why they’re slowest.

The cache itself is layered: a small, very fast L1 cache next to each core, a bigger L2, and often a large L3 shared by all the cores ¹. lscpu shows their sizes (last lesson).

Locality

Caches only help if the data a program needs next is already in them. Luckily, programs are predictable in two ways ¹:

• Temporal locality: data used recently tends to be used again soon. A loop’s counter, the current line of a document.
• Spatial locality: data near something just used tends to be used next. The next item in a list, the next bytes of a file.

So when the CPU needs a byte from memory, the cache fetches a whole block around it, typically 16 to 64 bytes, and keeps recently used blocks close ¹. Programs that walk through data in order get the next several values for free; programs that jump around keep waiting for main memory.

An experiment

This program adds up the same ten million numbers twice: once in order, once in a shuffled order. The work is identical; only the order of reading changes. Save it as locality.py:

# locality.py: read the same numbers in order, then in a random order.
import array
import random
import time

N = 10_000_000
data = array.array("q", range(N))       # 10 million 8-byte integers, side by side
in_order = list(range(N))
shuffled = in_order[:]
random.shuffle(shuffled)

def total(indexes):
    s = 0
    for i in indexes:
        s += data[i]
    return s

for name, order in [("in order", in_order), ("random order", shuffled)]:
    start = time.perf_counter()
    total(order)
    print(f"{name:<13} {time.perf_counter() - start:.2f} s")

array.array("q", ...) stores the numbers as plain 8-byte integers packed side by side in memory, like a C array, so neighbors really are neighbors. On a desktop PC:

me@linuxbox:~$ python3 locality.py
in order      0.29 s
random order  1.66 s

Almost six times slower, for exactly the same additions. Reading in order, each cache block brings in the next few numbers; in a random order, nearly every read lands somewhere not yet in the cache, and the processor waits for main memory. Your numbers will differ by machine; the gap won’t go away.

What it means in practice

• Reading files in order is fast, and the system helps: Linux keeps recently used file data in otherwise unused memory as a cache. That’s why free -h shows a large buff/cache figure; that memory is handed back to programs whenever they need it ^{2 3}.
• SSDs changed everything for random access: a hard disk has to swing its arm to each new spot, milliseconds each time, so an SSD makes a laptop feel faster than any processor upgrade ¹.
• The network is the slowest layer of all. A program that makes hundreds of small requests to a server spends almost all its time waiting.
• When something is unexpectedly slow, ask which layer it’s waiting on.

Your turn

So

Storage comes in layers, each bigger, cheaper, and slower than the one above: registers (under a nanosecond), caches (nanoseconds), main memory (about 100 ns), SSDs (a tenth of a millisecond and up), hard disks (milliseconds), and the network (tens to hundreds of milliseconds). Caches keep recently used data (temporal locality) and blocks of nearby data (spatial locality) close to the CPU, so programs that read in order run far faster than ones that jump around: the same sum took 0.29 s in order and 1.66 s shuffled. Linux uses spare memory the same way, as a cache for files.