Cache Locality: Why the Order of Reads Matters

An 8 × 8 matrix of ints sits in memory row after row, and between it and the processor is a cache of eight 16-byte lines. Add the matrix up by rows or by columns and step through the reads: each cell shows the one line its address may use, amber for a miss, green for a hit, pale for the neighbours a miss brought in.

Worked example — Cache Locality: Why the Order of Reads Matters

Reads, in either order	64
16-byte blocks the matrix touches	16
Most hits any order can get	48 of 64 (75.0%)
Hits by rows	48 of 64 (75.0%)
Hits by columns	0 of 64 (0.0%)
Cache lines column 0 lands on	4 of 8

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Cache Locality: Why the Order of Reads Matters

A cache is a small, fast memory that keeps copies of main memory in lines, each holding one aligned block of L bytes. A read whose block is already in a line is a hit; any other read is a miss, and the whole block is loaded. In a direct-mapped cache of S lines, the block holding address a may go in one line only, line ⌊a / L⌋ mod S. A loop that reads neighbouring addresses one after another gets several reads out of each block it loads, which is called spatial locality.

What each symbol means

L: the line size in bytes: 16 here, 64 on most desktop and server processors
S: the number of lines: 8 here

Assumes: A direct-mapped cache that starts empty, 4-byte ints, and a matrix stored row by row, as C stores it (Fortran stores by columns, and there the fast order is the other one). Only the matrix reads are counted. Real first-level data caches are larger and set-associative, typically 8-way: a block may go in any of 8 lines of its set, which removes most of the conflicts shown here but not a shortage of space. Hardware prefetching, which fetches the next line before it is asked for, is left out.

The same 64 additions get 48 hits or none 🖖

Press 8 × 8 by rows, then 8 × 8 by columns. Both read the same 64 ints at the same 64 addresses; only the order changes. By rows, the first read of each 16-byte line misses and loads four ints, so the next three are already there: 48 hits. By columns, the next read is one row on, 32 bytes away, in another line. A row here is exactly two lines long, so column 0 lands on lines 0, 2, 4 and 6 and nowhere else, and a[4][0] throws out the block that a[0][0] brought in. When the loop comes back for a[0][1], its block is gone. All 64 reads miss. Ulrich Drepper measured the full-sized version in 2007: a 1000 × 1000 matrix multiplication on an Intel Core 2 ran in 23.4% of the clock cycles once the matrix it had been reading by columns was transposed first, so that both were read by rows.

While the matrix fits in the cache, the order makes no difference 🖖

Set the size to 5 and switch orders: 18 hits of 25 either way. The matrix is 100 bytes against a 128-byte cache, its seven blocks land on seven different lines, and once a block is loaded nothing throws it out. Each block misses once, on its first read, whatever the order. At 6 × 6 the matrix is 144 bytes, two of its blocks must share a line, and the orders part: 27 hits by rows, 25 by columns. With no padding, column order stays behind at every size from there to 16 × 16.

Four unused ints per row turn 0 hits into 48 🖖

Press Padded rows. It is the same 8 × 8 matrix read by columns, but each row is followed by four ints that nothing reads, so a row is 48 bytes, three lines, instead of two. Three and eight have no common factor, so column 0 now lands on all eight lines, a column's eight blocks sit side by side, and the next three columns find them waiting: 48 hits of 64, as many as by rows. The price is 128 bytes that are never read. What the padding removes are conflict misses, two blocks fighting over one line while others stand empty. It cannot make room the cache does not have, and the worked problem ends with a matrix where that is the whole trouble.

Problem solved in full

How much memory traffic does the wrong order cost? 4 steps
Press 8 × 8 by columns and explain the 0 hits. Then take a 1024 × 1024 matrix of 4-byte ints and a direct-mapped 32 KiB cache with 64-byte lines. How many bytes move from memory when it is summed by rows, and how many by columns? Does padding each row by one line help?

Open this problem in the tool
1. On the page, a row is 8 × 4 = 32 bytes, two lines, so row i starts in line 2i mod 8 and column 0 uses lines 0, 2, 4 and 6 only. a[4][0] takes the line a[0][0] was in, and by the time the loop reaches a[0][1] its block has gone: 0 hits of 64. By rows there is one miss per 16-byte block, 16 of them, so 48 hits, 1 − 4/16 = 75%.
  
  $8 \times 4 = 32 bytes = 2 lines : 2 i mod 8 \in {0, 2, 4, 6}, 64 - 16 = 48 hits by rows$
2. The large cache has 32,768 / 64 = 512 lines. By rows, each 64-byte line holds 16 ints and only the first read of each misses: 1,048,576 / 16 = 65,536 misses, a hit rate of 1 − 4/64 = 93.75%, and 65,536 × 64 = 4,194,304 bytes moved, the matrix exactly once.
  
  $\frac{32 768}{64} = 512 lines, \frac{1 048 576}{16} = 65536 misses, 65536 \times 64 = 4194304$
3. By columns: a row is 4,096 bytes, 64 lines, so row i starts in line 64i mod 512 and a column uses only 8 of the 512 lines. a[8][0] throws out a[0][0]'s block, and long before the loop returns for a[0][1] it has gone. Every one of the 1,048,576 reads misses: 67,108,864 bytes, 16 times as much.
  
  $\frac{4 096}{64} = 64 : 64 i mod 512 takes 8 values, 1048576 \times 64 = 67108864$
4. Padding each row with 16 ints makes it 4,160 bytes, 65 lines. 65 and 512 have no common factor, so a column now spreads over all 512 lines. It still gets no hits: a column touches 1,024 blocks and the cache holds 512, so every block is gone before the next column wants it.
  
  $\frac{4 160}{64} = 65, g cd (65, 512) = 1, 1024 blocks > 512 lines$
Answer

4 MiB by rows, 64 MiB by columns. Padding spreads the column over the whole cache and still gets no hits: it cures conflicts, and each of this matrix's columns is bigger than the whole cache.

$4 MiB by rows, 64 MiB by columns (16 \times)$

Learning path

How a computer runs a program

References (1)

The first insight's measured case, the line size in the definition, and the 8-way first-level caches in `assumes`: Ulrich Drepper, "What Every Programmer Should Know About Memory," Red Hat, Inc., version 1.0, 21 November 2007. §3.2 (p. 15), §3.3.1 (pp. 17–18), §6.2.1 (pp. 49–50).

By the 42Math team · Reviewed against published sources. Corrections welcome.