The idea: same work, different order, different misses
Two loops can do exactly the same additions and multiplications and still run at very different speeds. The difference is the order in which they touch memory. A cache does not fetch single numbers: on a miss it loads a whole block (cache line) of neighbouring bytes. A loop that uses all of a block before moving on pays one miss per block. A loop that jumps around pays a miss on almost every access.
The page has three 8×8 matrices of doubles, A, B and C, and a tiny cache. The Memory panel shows every element; a cell turns red when its access missed in the current step, green when it hit, and light blue while its block sits in the cache. The Cache panel lists the blocks in the cache, most recently used first. Pick a loop and a cache size and press Run Loop. The first four accesses go one at a time; after that each step plays a whole inner loop or more. The Results table keeps every run until you press Reset, so you can compare the loops.
Row-major layout and the block
C, C++, Java and NumPy (by default) store a 2-D array row by row: this is row-major order. For an 8×8 array of 8-byte doubles,
address of A[i][j] = base + (i·8 + j)·8
so A[0][1] is 8 bytes after A[0][0], but A[1][0] is 64 bytes after it. The page's cache has 32-byte blocks, 4 doubles: each row is 2 blocks and each matrix 16 blocks. The cache is fully associative with LRU replacement and 4, 8 or 16 lines, and every run starts empty. So the fewest misses any loop can have is one per block it uses, the cold misses: 16 for one matrix, 48 for three. The counters show this number as "fewest possible". How a real cache cuts an address into tag, index and offset is on Cache Address Breakdown; direct-mapped and set-associative caches and the three kinds of misses are on CPU Cache.
Walking a matrix: row order vs column order
Sum all 64 elements of A, first row by row (for i, for j), then column by column (for j, for i). Same 64 additions.
- Row by row moves 8 bytes per step. A[0][0] misses and brings A[0][0..3]; the next three hit; A[0][4] misses and brings the rest of the row. 16 misses of 64, 25 % (Demo 1). That is the fewest possible.
- Column by column moves 64 bytes per step, so every access is in a new block. With 4 lines, A[0][0]'s block is thrown out after 4 more rows, long before the walk comes back for A[0][1]. All 64 accesses miss (Demo 2).
- With 8 lines the column walk costs only 16 misses (Demo 3): column 0 loads one block of each of the 8 rows, and they all stay until columns 1 to 3 use them.
So column order is only safe when the cache can hold one block for every row. A real matrix of 1000 × 1000 doubles with 64-byte lines needs 1000 lines, 64 KB, for that: more than a typical 32 or 48 KB L1 data cache. Walk along the last index. A transposed NumPy view (NumPy Views and Strides) reads memory column by column even when the code looks like a row loop.
Matrix multiply and loop interchange
The schoolbook product C = A·B (Matrix Multiplication) is three nested loops over i, j and k, and the loops can go in any of 6 orders: every order adds the same products into each C[i][j]. Swapping two loops is called loop interchange. The innermost loop decides which matrices are walked along a row and which down a column. The page counts each access once, keeps the running sum sum or the reused value r in a register, and counts C[i][j] += as one access, as in Bryant and O'Hallaron's analysis.
| order | inner loop reads | misses, 8 lines (A, B, C) | misses per inner iteration, large n |
|---|---|---|---|
| ijk (Demo 4) | A along a row, B down a column | 592 of 1088 (16, 512, 64) | 1.25 |
| ikj (Demo 5) | B and C along rows | 160 of 1088 (16, 128, 16) | 0.5 |
| jki (Demo 6) | A and C down columns | 1088 of 1088 (512, 64, 512) | 2.0 |
In ijk, B[k][j] for k = 0..7 is in 8 different blocks. Together with A's row and C they need more than 8 lines, so the blocks are gone before j + 1 could use their other elements: all 512 reads of B miss. In ikj the inner loop reads B[k][0..7] and C[i][0..7] along rows: one miss per block. jki is the mirror of ikj: A and C are read down columns and every single access misses. The last column is the classic result for 32-byte blocks and matrices much bigger than the cache: the other three orders behave like these (jik like ijk, kij like ikj, kji like jki).
Tiling (blocking)
ikj is still not good enough when the matrices do not fit. Every row i of C needs all of B, 16 blocks, and the cache has 8 lines. So B is loaded again for each of the 8 rows: 8 × 16 = 128 misses for B alone. Loop tiling (also called blocking) cuts each loop into pieces of size T and adds three outer loops over the pieces: ii, kk, jj. Inside, the work is a small T×T product: one tile of A times one tile of B, added into one tile of C.
With T = 4 a tile is 4×4 doubles, 4 blocks. While i runs over the 4 rows of a tile, the loop needs B's tile (4 blocks), one block of A and one of C: 6 blocks, which fit in 8 lines. Each tile of B is loaded once per ii, that is 8 / 4 = 2 times, and the same goes for A (once per jj) and C (once per kk): 16 × 2 = 32 misses each, 96 in all, against 160 for ikj and 592 for ijk (Demo 7). Tiling adds a few accesses: r = A[i][k] is now loaded once per tile, 1152 accesses instead of 1088.
Choosing the tile size
Make the tile small enough that the data it reuses stays in the cache, and at least one block wide. T = 2 breaks the second rule: a 2-wide tile uses only half of each 4-element block, so the other half is loaded again for the next tile. It costs 144 misses and 1280 accesses, worse than T = 4 (Demo 8). T = 8 is the whole matrix, so it is plain ikj again: 160. A common rule of thumb asks that the three tiles fit together, 3 · T² · 8 bytes ≤ cache size. For a 32 KB L1 that gives T ≤ 36. Fast libraries such as BLAS tile several times over, for registers, L1, L2 and L3.
| loop | cache | misses / accesses | miss rate |
|---|---|---|---|
| row by row | 4 lines | 16 / 64 | 25 % |
| column by column | 4 lines | 64 / 64 | 100 % |
| column by column | 8 lines | 16 / 64 | 25 % |
| ijk | 8 lines | 592 / 1088 | 54.4 % |
| ikj | 8 lines | 160 / 1088 | 14.7 % |
| jki | 8 lines | 1088 / 1088 | 100 % |
| tiled, T = 4 | 8 lines | 96 / 1152 | 8.3 % |
| tiled, T = 2 | 8 lines | 144 / 1280 | 11.3 % |
Try the 16-line cache too: ikj still reloads B (19 blocks are needed per row i), while the tiled loop drops to 80.
Habits for cache-friendly loops
- Make the innermost loop run over the last index in C-like languages (the first index in Fortran and in column-major MATLAB arrays).
- If it does not, interchange the loops when the result stays the same. GCC can do this itself at
-O3(-floop-interchange), but only when it can prove the swap is safe. - When the data you reuse is bigger than the cache, tile the loops so the reused part fits.
- Keep values that the inner loop reuses in local variables (
sum,r): the compiler can keep them in registers.
A miss here simply counts as a block loaded from memory. What it costs in cycles, and how L2 and L3 soften it, is on One Load Through the Memory Hierarchy; what happens when the loop writes, as C does here, is on Cache Write Policies.
What the page leaves out
The cache is fully associative, so there are no conflict misses; a real 8-way cache with a power-of-two matrix size can map a whole column to one set, and padding each row by a block fixes it. Writes count like reads, with no write-back cost. There is only one cache level, no TLB and no hardware prefetcher, which in a real CPU hides much of the cost of a steady column walk. The page does not show the other three loop orders, register tiling and SIMD, copying tiles into a contiguous buffer (packing), cache-oblivious recursive multiplication, or that a different order of additions can change floating-point results in the last bits.