Cache lines
Memory moves between the cache and main memory in blocks of 64 bytes, never one byte at a time, and that single fact explains a surprising amount of performance.
When a program reads one byte that is not in the cache, the processor does not fetch one byte. It fetches the whole aligned block of 64 bytes that contains it, a cache line, and keeps the line in the cache. The next 63 bytes are then free: they arrived with the first. A program that reads memory in order pays for one trip to memory per 64 bytes. A program that jumps around pays for one trip per byte it reads, and gets 63 bytes it never looks at.
Why memory moves in lines
Every trip to main memory has a large fixed cost and a small cost per byte. The fixed cost is the time to send an address out across the chip, open a row inside the memory chips, and bring the answer back: tens of nanoseconds before the first byte arrives. Once the row is open, the following bytes stream out quickly, many bytes per nanosecond. So the expensive part is starting a transfer, not continuing one.
A cache that fetched single bytes would pay the fixed cost every time. A cache that fetches lines pays it once and gets the neighbours for almost nothing. That is a good bet because of spatial locality: programs that use an address tend to use the addresses next to it soon after. Arrays are read in order, the fields of a record sit together, and instructions run one after another.
The cache keeps track of whole lines, not bytes. Each line has one tag, which records which 64-byte block of memory the line holds, and the line is either present in the cache or not. There is no such thing as half a line being cached.
One touch costs a line
The consequence is easy to state and easy to forget: the cost of a memory access depends on how many lines it touches, not on how many bytes it uses. Touching one byte of a line costs the same trip to memory as touching all 64.
The experiment below shows it on a real machine. It takes a buffer of 256 MiB, far larger than any cache, and adds one to every k-th byte, for strides k from 1 byte to 256 bytes. The work done per pass shrinks by half each time the stride doubles. If the cost were per byte touched, the time per pass would halve too. Watch the middle column.
ran on: Intel(R) Core(TM) i9-10900K CPU @ 3.70GHz, 16 GB RAM, Windows 10
...
stride touches ms per pass ns per touch
1 B 268435456 77.2 0.29
2 B 134217728 41.4 0.31
4 B 67108864 24.8 0.37
8 B 33554432 18.5 0.55
16 B 16777216 15.7 0.94
32 B 8388608 15.0 1.79
64 B 4194304 16.6 3.95
128 B 2097152 12.0 5.72
256 B 1048576 8.0 7.66
From a stride of 8 bytes to a stride of 64, the number of bytes touched falls by a factor of eight and the time per pass hardly moves: about 15 to 18 milliseconds each time. In every one of those passes the processor brings in every line of the buffer, all 4,194,304 of them, because every line contains at least one byte the loop touches. The time is the time to move 256 MiB through the cache, and the loop’s own work hardly matters. Measured per touch, the cost climbs from half a nanosecond to four, which is what it looks like when a fixed cost per line is shared among fewer and fewer touches.
The two ends of the table are different stories. At strides of 1 to 4 bytes the loop does hundreds of millions of additions, and the processor’s own work, not memory, sets the pace. Past 64 bytes the loop skips whole lines, so less memory moves and the pass gets faster; it does not get twice as fast at 128 because the processor fetches some lines it was not asked for, betting that they will be wanted next.
Counting lines instead of bytes
Thinking in lines turns many performance questions into arithmetic. Ask of a loop how many of each line’s 64 bytes it actually uses before the line is thrown out of the cache. That fraction is the share of the memory traffic doing useful work.
| Loop | Bytes used per line | Useful share |
|---|---|---|
| Sum an array of 32-bit integers in order | Bytes used per line 64 | Useful share 100% |
| Read one 8-byte field from each 64-byte record | Bytes used per line 8 | Useful share 12.5% |
| Read every 16th 32-bit integer of an array | Bytes used per line 4 | Useful share 6.25% |
| Walk a column of a large row-major matrix of 8-byte floats | Bytes used per line 8 | Useful share 12.5% |
| Follow a linked list of 16-byte nodes scattered in memory | Bytes used per line 16 | Useful share 25% |
The second row is common in real programs and easy to miss. An object with a dozen fields, of which a hot loop reads one, costs the loop the whole object every time. Reorganising the data so that the field the loop reads sits in its own array, packed tightly, can make such a loop several times faster without changing a line of its logic. Data layout returns to that idea.
What wc does with its lines
The book’s running example, wc, reads its file from start to end, one byte after another. That is the best possible pattern for lines: every byte of every line it fetches is used, and the processor’s prefetcher, seeing the steady march through memory, fetches the next lines before they are asked for. A loop like this one is limited by how fast it can examine bytes, not by memory:
words, inside = 0, False
for byte in data:
if byte in b" \n\t":
inside = False
elif not inside:
words, inside = words + 1, True
If wc instead built a list of every word as a separate Python object and then counted them, the same file would be scattered across thousands of small allocations, and each would cost a line of its own. The work would be the same; the memory traffic would not.