Same work, different speed
Here are two ways to add up every number in a large two-dimensional array: row by row, or column by column. They do exactly the same additions, the same number of times, and both are . Yet on a real computer one of them can be several times slower than the other, and in a compiled language the gap can be ten times or more. Big-O notation, from Complexity, counts operations and assumes every memory access costs the same. On real hardware that assumption is false by orders of magnitude.
The reason is physical. A modern processor core can start several instructions every third of a nanosecond, but fetching a value from main memory takes on the order of 100 nanoseconds, the time for several hundred instructions. If the processor really had to wait for main memory on every load, it would sit idle almost all of the time. It does not, because between the core and main memory sit several layers of smaller, faster memories, the caches, that keep copies of recently used data. When a program's accesses follow predictable patterns, the caches hide nearly all of the waiting. When they do not, the program runs at the speed of memory, not of the processor.
This lesson explains that hierarchy, simulates a cache in Python, and shows how the order in which you touch data decides which kind of program you have written.
The levels, and how far away each one is
Each level of the hierarchy is larger, slower and cheaper per byte than the one above it. The numbers below are rough orders of magnitude for a typical laptop or server in the mid-2020s. Exact values vary severalfold between processors and change over the years, so learn the ratios, not the digits.
| Level | Typical size | Typical latency | If 1 ns were 1 second |
|---|---|---|---|
| Registers | hundreds of bytes to a few KB per core | under 1 ns (one cycle) | under a second |
| L1 cache | 32–64 KB per core | about 1 ns (a few cycles) | about a second |
| L2 cache | 0.25–2 MB per core | a few ns | a few seconds |
| L3 cache | several MB to 100+ MB, shared | 10–20 ns | 10–20 seconds |
| Main memory (DRAM) | gigabytes | 50–100 ns | 1–2 minutes |
| NVMe SSD, random read | terabytes | tens of µs | about a day |
| Round trip within a data centre | – | hundreds of µs | several days |
| Hard disk seek | terabytes | several ms | a few months |
| Round trip between continents | – | 100–200 ms | several years |
Two lessons hide in this table. First, the jumps are enormous: from L1 to DRAM is about a hundredfold, from DRAM to SSD a thousandfold, from SSD to a disk seek a hundredfold. Second, the bottom rows are set by physics that engineering cannot beat. Light in optical fibre travels at about 200,000 km per second, so every 1,000 km between two machines adds at least 10 ms to a round trip, whatever the hardware.
Latency is not bandwidth. Latency is how long until the first byte arrives; bandwidth is how many bytes per second flow once data is streaming. DRAM delivers on the order of ten gigabytes per second or more to a single core once a stream is going, even though each individual miss takes about 100 ns. Much of the art of fast code is turning latency-bound access (one unpredictable address at a time) into bandwidth-bound access (long predictable streams).
Why not make all memory fast? Because the fast kinds are expensive and the big kinds are slow. The SRAM in caches uses six transistors per bit and must sit close to the core; DRAM uses one transistor and a capacitor per bit, is far denser, but needs refreshing and sits centimetres away on separate chips; flash is denser still and keeps data without power, but reads take microseconds and writes longer. Even within one technology, a bigger memory is slower, because signals must travel further and more entries must be searched. So designers build a pyramid and rely on programs to cooperate.
Locality: why caches work at all
A cache helps only if data you used recently is likely to be needed again soon. Remarkably often, it is. Programs exhibit locality of reference:
Definition— temporal and spatial locality
Temporal locality: an item accessed now is likely to be accessed again soon (a loop counter, a running total, the instructions of a loop body). Spatial locality: an item near one accessed now is likely to be accessed soon (the next element of an array, the next instruction, the other fields of the same object).
Caches exploit temporal locality by keeping recently used data, and spatial locality by moving data in blocks: when you read one byte, the hardware fetches the whole surrounding cache line, 64 bytes on most current x86-64 and Arm processors (some designs use 128). Reading one 8-byte number from an array therefore brings in the next seven for free. Hardware prefetchers go further: when they notice a steady stride, they fetch lines before the program asks for them.
Analogy, not a formal construction
You are writing an essay in a library. Your desk holds the few books you are using right now (registers and L1); the trolley beside you holds the dozen you have used today (L2 and L3); the shelves hold everything else (main memory), and the off-site store needs a day's notice (the disk). You work quickly as long as you mostly reach for books on the desk, and when you do fetch from the shelves, you bring back the neighbouring volumes too, because you will probably want them. A student who needs one sentence from each of a thousand different books, in random order, will spend the day walking.
Peter Denning's working set idea (1968) sharpens this: at any moment a program is actively using some set of data. If the working set fits in a level of the hierarchy, the program runs at roughly that level's speed. Much performance work consists of shrinking the working set or reordering the computation so that it fits.
How a cache works, and a simulator
A cache holds a fixed number of lines. When the processor requests an address, the cache must find out quickly whether it holds the line containing that address. It does so by splitting the address into three fields.
Definition— offset, index, tag; associativity
With lines of bytes, the low bits of an address are the offset within the line. The lines of the cache are grouped into sets; the next bits, the index, say which set a line must go in. The remaining high bits, the tag, are stored with the line to tell apart the many memory lines that share a set. A cache whose sets hold lines each is -way set-associative; with it is direct-mapped (each line has exactly one possible place), and with a single set it is fully associative (any line can go anywhere). When a set is full and a new line arrives, a replacement policy, usually an approximation of least recently used (LRU), chooses the victim.
Example— Splitting an address
A 32 KiB, 8-way cache with 64-byte lines has lines in sets. So the offset is the low 6 bits and the index the next 6 bits. For the address 0x12345: the offset is 0x12345 & 0x3F ; the line number is 0x12345 >> 6 ; the index is ; the tag is , rounded down, . The hardware compares the tag 18 against the eight tags stored in set 13, all at once.
Misses come in three kinds, a classification due to Mark Hill:
- Compulsory (cold) misses: the first access to a line can never hit.
- Capacity misses: the working set is larger than the cache, so lines are evicted before they are reused.
- Conflict misses: the cache has room, but too many lines in use map to the same set and evict each other.
Writes add one more decision. Most caches are write-back: a write updates only the cached copy and marks the line dirty, and the line is written to memory when it is evicted. That turns many writes to the same line into one memory transfer.
The simulator below models exactly this: it tracks which lines are in each set (not the data itself) and counts hits and misses. It then replays the addresses touched by traversing an array of 8-byte numbers stored row by row, as C arrays and NumPy arrays are by default.
from collections import OrderedDict
class Cache:
"""A set-associative cache with LRU replacement. It tracks only which lines are present."""
def __init__(self, size_bytes=32 * 1024, line_bytes=64, ways=8):
self.line_bytes, self.ways = line_bytes, ways
self.num_sets = size_bytes // (line_bytes * ways)
self.sets = [OrderedDict() for _ in range(self.num_sets)]
self.hits = self.misses = 0
def access(self, address):
line = address // self.line_bytes # which 64-byte block of memory
index = line % self.num_sets # which set it must live in
tag = line // self.num_sets # tells apart the lines that share a set
s = self.sets[index]
if tag in s:
self.hits += 1
s.move_to_end(tag) # now the most recently used
else:
self.misses += 1
if len(s) == self.ways:
s.popitem(last=False) # evict the least recently used
s[tag] = True
def report(self, label):
total = self.hits + self.misses
print(f"{label:34} {total:>8,} accesses {self.misses:>8,} misses ({self.misses / total:6.1%})")
def traverse(n, order, cache, elem=8):
"""Visit every element of an n x n array of 8-byte numbers stored row by row (C order)."""
for a in range(n):
for b in range(n):
i, j = (a, b) if order == "row" else (b, a)
cache.access((i * n + j) * elem)
for n, order in [(512, "row"), (512, "column"), (520, "column"), (64, "column")]:
c = Cache()
traverse(n, order, c)
c.report(f"{n} x {n}, {order} by {order}")Four results, four lessons.
- Row by row: 12.5% misses. Each 64-byte line holds 8 numbers; the first access to a line misses and the next seven hit. These are all compulsory misses, and a hardware prefetcher would hide most of them too.
- Column by column, 512 × 512: every access misses. Consecutive accesses are 4,096 bytes apart, so each touches a new line, and by the time the traversal comes back for the neighbouring number in the same line, the line is long gone. Worse, a stride of 4,096 bytes is a multiple of , so every element of a column maps to the same set: only 8 of the cache's 512 lines are usable. Those are conflict misses.
- Column by column, 520 × 520: about 25%. Padding each row by eight numbers spreads a column across all the sets, and much of each line survives until it is reused. Power-of-two array sizes are a classic trap, and padding is the classic fix.
- A 64 × 64 array, column by column: 12.5%. The whole array is 32 KiB and fits in the cache, so order barely matters. Traversal order matters once the working set outgrows the cache.
Why traversal order matters
Row-major and column-major
A two-dimensional array is stored in one-dimensional memory, so a language must choose. C, C++ and NumPy (by default) store row-major: the elements of a row are adjacent. Fortran, MATLAB, Julia and R store column-major. The cache-friendly loop runs its innermost index over adjacent elements: for i: for j: a[i][j] in C or NumPy, the opposite in Fortran or Julia. (Python's own list of lists is different again: each row is a separate object holding pointers to separately allocated numbers, so even row-by-row access chases pointers. This is one reason NumPy exists.)
Loop order in matrix multiplication
Matrix multiplication with the textbook loop order i, j, k computes each as a dot product of row of with column of , so its innermost loop walks down a column of . Swapping the loops to i, k, j computes the same sums in a different order: the inner loop now walks along a row of and a row of . Better still is tiling (or blocking): split the matrices into small square tiles that fit in the cache together, and finish all the work on one set of tiles before moving on.
from collections import OrderedDict
class Cache:
def __init__(self, size_bytes, line_bytes, ways):
self.line_bytes, self.ways = line_bytes, ways
self.num_sets = size_bytes // (line_bytes * ways)
self.sets = [OrderedDict() for _ in range(self.num_sets)]
self.hits = self.misses = 0
def access(self, address):
line = address // self.line_bytes
s, tag = self.sets[line % self.num_sets], line // self.num_sets
if tag in s:
self.hits += 1
s.move_to_end(tag)
else:
self.misses += 1
if len(s) == self.ways:
s.popitem(last=False)
s[tag] = True
def matmul_trace(n, order, cache, tile=16):
"""Feed the cache the memory accesses of C = A x B (n x n doubles, row-major) in a given loop order."""
A, B, C = 0, n * n * 8, 2 * n * n * 8 # three arrays, one after another in memory
at = lambda base, r, c: base + (r * n + c) * 8
if order == "ijk":
for i in range(n):
for j in range(n):
for k in range(n):
cache.access(at(A, i, k)); cache.access(at(B, k, j))
cache.access(at(C, i, j))
elif order == "ikj":
for i in range(n):
for k in range(n):
cache.access(at(A, i, k))
for j in range(n):
cache.access(at(B, k, j)); cache.access(at(C, i, j))
elif order == "tiled":
for kk in range(0, n, tile):
for jj in range(0, n, tile):
for i in range(n):
for k in range(kk, kk + tile):
cache.access(at(A, i, k))
for j in range(jj, jj + tile):
cache.access(at(B, k, j)); cache.access(at(C, i, j))
n = 64
for order in ["ijk", "ikj", "tiled"]:
c = Cache(size_bytes=8 * 1024, line_bytes=64, ways=4) # a small cache, so the effect shows at small n
matmul_trace(n, order, c)
total = c.hits + c.misses
print(f"C = A x B, n={n}, loop order {order:5}: {total:>7,} accesses, {c.misses:>7,} misses ({c.misses / total:5.1%})")Same arithmetic, same result, and the miss rate drops from about one access in two to a few per cent. Optimised linear-algebra libraries (the BLAS implementations that NumPy calls) apply tiling at every level, registers, L1, L2 and L3, which is a large part of why a @ b in NumPy can be thousands of times faster than a triple loop in Python (the rest is avoiding the interpreter and using vector instructions). The same thinking drives the design of GPU kernels for machine learning, as you will see in Accelerators and parallelism.
Measuring it for real
Simulations count misses; the real question is time. The block below times NumPy summing a 2000 × 2000 array of floats (32 MB, larger than most caches) row by row and column by column, and then reads 4 million elements in order and in a random order. Your numbers will differ from anyone else's: they depend on your processor's caches and prefetchers, and on the browser if you run it there.
import time
import numpy as np
n = 2000
a = np.arange(n * n, dtype=np.float64).reshape(n, n) # 32 MB, stored row by row (C order)
def timed(label, f, repeat=3):
best = float("inf")
for _ in range(repeat):
t0 = time.perf_counter()
result = f()
best = min(best, time.perf_counter() - t0)
print(f"{label:38} {best * 1000:8.1f} ms")
return best, result
t_rows, s1 = timed("sum each row (contiguous slices)", lambda: sum(a[i, :].sum() for i in range(n)))
t_cols, s2 = timed("sum each column (stride of 16,000 B)", lambda: sum(a[:, j].sum() for j in range(n)))
assert s1 == s2
print(f"same arithmetic, same answer; columns took {t_cols / t_rows:.1f} times as long")
flat = a.ravel()
rng = np.random.default_rng(0)
perm = rng.permutation(flat.size)
t_seq, _ = timed("gather 4M elements in order", lambda: flat[np.arange(flat.size)].sum())
t_rand, _ = timed("gather 4M elements in random order", lambda: flat[perm].sum())
print(f"random order took {t_rand / t_seq:.1f} times as long")When this lesson was tested, columns took a little over twice as long as rows, and random order took between one and a half and four times as long as sequential order, depending on whether the code ran natively or in a browser. Large modern caches and prefetchers soften the effect for an array of this size; push the array well beyond your L3 cache, or write the loops in C, and the gaps grow to many times.
Data layout beyond arrays
The same reasoning applies to every data structure. A linked list scatters its nodes across memory, so traversing it is a chain of dependent loads, each possibly a cache miss: this is called pointer chasing, and it is why an array (a Python list of references, or better a NumPy array of values) usually beats a linked list in practice even where their big-O costs match. When you process one field of many records, an array of structures drags every record's other fields through the cache, while a structure of arrays (one array per field) touches only what you need; column-oriented databases and data-frame libraries are built on that idea.
The same idea at every level
Caching is not only a hardware trick. The same pattern, a small fast store in front of a big slow one, exploiting locality, recurs at every layer you will study:
- Virtual memory. Every address a program uses is translated by the hardware to a physical address, using page tables kept in memory, and a small cache of recent translations called the TLB. Main memory itself acts as a cache for disk. That is the next lesson, Operating systems.
- The operating system's page cache keeps recently read file contents in spare RAM, which is why the second time you open a big file is much faster than the first, and why "free" memory on a busy Linux machine is usually small.
- Databases keep a buffer pool of disk pages in memory and choose data layouts (B-trees, column stores) for locality; see Databases.
- The web relies on browser caches, content delivery networks with servers near users, and in-memory caches such as Redis or Memcached in front of databases.
In every case the questions are the same ones you have just asked: what is the working set, does it fit, how are items placed and evicted, and what happens on a miss?
Tools for the real thing. On Linux, lscpu and the files under /sys/devices/system/cpu/cpu0/cache/ describe your caches; perf stat -e cache-references,cache-misses ./program counts real misses with the processor's hardware counters; and Valgrind's cachegrind simulates the caches instruction by instruction, much like our simulator but for whole programs.
Common misconceptions
Misconception
"Two algorithms with the same big-O run at the same speed." Big-O hides constant factors, and memory behaviour is often the biggest of them. An algorithm with good locality can beat an one that misses the cache on every step for all practical .
Misconception
"A bigger cache is simply better." Bigger caches are slower to search and further away, which is why there are several levels instead of one large one. Each level balances size against latency.
Misconception
"Memory access costs the same everywhere." The RAM model of complexity theory assumes so; hardware does not. An access can cost one cycle or several hundred depending on where the data happens to be.
Misconception
"An SSD is just slow RAM." It is a block device: data moves in pages of kilobytes, through the operating system, with latencies of tens of microseconds, about a thousand times DRAM's. Code that treats storage like memory (many small random reads) pays for every one.
Exercises
1. The memory hierarchy
Warm-upHumanA processor has a 48 KiB, 12-way set-associative L1 data cache with 64-byte lines. How many bits of an address form the index?
2. The memory hierarchy
Warm-upHumanA program sums an array of 1,024 eight-byte floats that starts at an address divisible by 64. The cache starts empty, has 64-byte lines, and is large enough to hold the whole array. Ignoring prefetching, how many cache misses does one pass over the array cause?
3. The memory hierarchy
CoreHumana is a large NumPy array with shape (n, n) in the default (C, row-major) order. Each version below visits every element once. Which loop structure has the best spatial locality?
4. The memory hierarchy
CoreComputationalWrite count_misses(addresses, num_lines, line_bytes) for a direct-mapped cache: each memory line can live only in cache slot line % num_lines, where line = address // line_bytes. A slot holds one memory line at a time; a miss replaces whatever was there. Return the number of misses for the given sequence of byte addresses, starting from an empty cache.
5. The memory hierarchy
CoreHumanIn the lesson's simulation, traversing a 512 × 512 array of doubles column by column missed on every access, while a 520 × 520 array missed on only about a quarter. What kind of misses did padding the rows to 520 mostly remove?
6. The memory hierarchy
Warm-upHumanTwo data centres are connected by 3,000 km of optical fibre, in which light travels at about 200,000 km/s. Ignoring every delay except the speed of light, what is the minimum round-trip time between them, in milliseconds?
7. The memory hierarchy
StretchComputationalTransposing a matrix, B[j][i] = A[i][j], reads along rows but writes down columns, so one of the two always has poor locality. Tiling fixes this: process the matrix in tile × tile blocks, finishing each block before moving on. Write tiled_order(n, tile) returning a list of every pair (i, j) with 0 <= i, j < n, each exactly once, in tiled order. The tests replay the accesses (read A[i][j], write B[j][i]) through the lesson's cache simulator and require far fewer misses than the plain row-by-row order. Your function should work when tile does not divide n.
Further reading and resources
- What every programmer should know about memory · Ulrich Drepper · 2007A long, detailed tour of caches, DRAM and how to program for them (LWN series; a PDF version is also available).
- Latency numbers every programmer should know (interactive) · Colin ScottAn interactive chart of approximate latencies by year; treat the numbers as orders of magnitude.
- Designs, lessons and advice from building large distributed systems · Jeff Dean · 2009The keynote slides that popularised a table of "numbers everyone should know".
- Evaluating associativity in CPU caches · Mark D. Hill and Alan Jay Smith · 1989The source of the compulsory, capacity and conflict classification of misses.
- The working set model for program behavior · Peter J. Denning · 1968