Week 0 · Lesson 2
Memory and caches
Two loops can do exactly the same arithmetic and differ in speed by ten times or more. The difference is the order they touch memory. From week 6 on, your grade depends on getting that order right.
Memory is far away
The CPU can add two numbers in well under a nanosecond. Fetching a number from main memory (DRAM) takes something like 100 nanoseconds. If every load went all the way out to DRAM, the CPU would spend almost all its time waiting.
So there are caches: small, fast memories that keep copies of recently used data close to the core. Rough, typical numbers for a modern desktop chip:
| level | typical size | typical latency | |
|---|---|---|---|
| register | a few hundred bytes | 0 cycles | |
| L1 cache | 32 to 64 KB per core | ~1 ns (4 to 5 cycles) | |
| L2 cache | 256 KB to 2 MB per core | ~4 ns | |
| L3 cache | 8 to 64 MB shared | ~10 to 20 ns | |
| DRAM | gigabytes | ~80 to 100 ns |
These vary by chip. Only the ratios matter here: each level is several times slower than the one above it. A nanosecond (ns) is a billionth of a second. A cycle is one tick of the CPU's clock, about 0.25 ns at 4 GHz. A register is one of a few dozen named slots inside the CPU where arithmetic actually happens, and a core is one of the CPU's independent processors.
Caches move whole lines
A cache never fetches just one byte. It fetches a cache line, which is 64 bytes on x86 and most ARM chips (Apple M-series chips use 128). Load one float and you get the other 15 floats in that line for free, as long as you use them before the line gets evicted (thrown out of the cache to make room for another line).
That means the order you walk an array matters. Reading consecutive addresses uses every byte of every line you fetch. Jumping around fetches a whole line and uses 4 bytes of it.
2D arrays are rows laid end to end
C stores int m[R][C] in row-major order: all of row 0, then all of row 1, and so on. So m[i][j] lives at
base + (i * C + j) * sizeof(int)Neighbors along j are neighbors in memory. Neighbors along i are C * 4 bytes apart. That's the base-plus-offset formula from lesson 1 again, with the offset now built from two indices.
The distance in memory from one access to the next is called the stride. Walking along j has stride 1 element, and walking along i has stride C elements.
Code quiz: the row-major index
Write int flat_index(int i, int j, int C): the position of m[i][j] in the flat array of a row-major matrix with C columns. Element positions, not bytes.
Watch it happen
Here's a toy machine so the picture fits on screen: int m[4][4] (64 bytes), toy cache lines of 16 bytes (4 ints), and a cache that holds only 2 lines. When it's full, the least recently used line gets kicked out (this policy is called LRU, "least recently used"). Step through both loops and count the misses.
Same 16 additions, same answer. Row order misses 4 times, once per line. Column order misses all 16 times, because by the time it comes back to a line, that line has been evicted. On a real machine with a large array, that's the difference between using every byte of each 64-byte line and using one 4-byte element of it.
Make the innermost loop walk the last index of the array, so it moves through memory with stride 1.
Code quiz: how many lines does a walk touch?
Write long long lines_touched(long long start, int n). You read n consecutive 4-byte ints starting at byte address start. Return how many distinct 64-byte cache lines those bytes fall in. Line k holds bytes 64k to 64k + 63. n can be 0.
An aligned walk of 16 ints touches 1 line. Shift it by 4 bytes and it touches 2.
Real CPUs also have hardware prefetchers that spot regular strides and fetch lines early. Column order on a small array can look less awful than this toy suggests. Don't trust intuition here. Measure. Starting in week 6, you'll time everything.
Why a compiler course cares
You won't write these loops by hand. Your compiler will generate them. In week 3 it prints loops as nested for loops in C. In week 4 it turns whole-array operations into loops by itself, and decides whether an intermediate result gets written to memory or recomputed where it's used. Once kernels are timed, from week 6, it can tile loops: split a big matrix into blocks small enough to stay in cache while they're reused. Every one of those decisions is about the picture above: keep the data you need close, and use every byte of each line you pay for.
Transpose a row-major matrix
Write void transpose(const int *src, int *dst, int rows, int cols). src is a rows x cols matrix stored row-major. Fill dst, a cols x rows row-major matrix, so that dst[j][i] == src[i][j].
Both arrays are flat, so you compute every index yourself with the formula from this lesson. The tests check 1 x 1, single rows, single columns, and that transposing twice gives back the original.
Which loop order is cache friendly here?
Neither, fully. If the inner loop walks j, reads of src are stride 1 but writes to dst jump by rows. Swap the loops and the problem swaps sides. Fast transposes work on small square tiles that fit in cache, which is the tiling idea in miniature.
The examples print dst through some helper code. Only your transpose matters.
Check yourself
How many 4-byte floats fit in one 64-byte cache line?
A float is 4 bytes. Divide the line size by the element size.
64 / 4 = 16.
int m[4][4] starts at address 0. What's the byte address of m[2][3]?
Row-major: first count how many ints come before m[2][3], then turn that count into bytes.
Two full rows of 4, plus 3 more. Each int is 4 bytes.
(2 × 4 + 3) × 4 = 11 × 4 = 44.
For float a[N][N] in C, which loop nest walks memory with stride 1 in the inner loop?
Which two elements are neighbors in memory: a[i][j] and a[i][j+1], or a[i][j] and a[i+1][j]?
The inner loop should move the last index, j, because a[i][j] and a[i][j+1] are adjacent in memory.
You sum float a[1024] front to back, and a starts on a line boundary. How many distinct 64-byte cache lines do you touch?
Work out the total bytes first, then how many 64-byte lines that many bytes fill.
1024 × 4 = 4096 bytes, and 4096 / 64 = 64 lines. Each line is fetched once and fully used.
A loop reads a[0], a[16], a[32], ... from a float array (stride 16 floats). What fraction of each fetched 64-byte line does it use?
A stride of 16 floats is 64 bytes. Where does each access land relative to the previous one?
Stride 16 floats is 64 bytes, so every access lands on a new line and uses 4 of its 64 bytes.
On the toy machine above, change the cache to hold 4 lines. How many misses does column order have now?
Column order misses because rows get evicted before the next column comes back to them.
If the cache can hold every line of the matrix at once, does anything ever get evicted?
All 4 lines of m fit at once, so after the first column brings them in, nothing is evicted. 4 misses, same as row order. That's the idea behind tiling: make the working set fit.