The same sum, several times slower
A company's nightly report adds up a large table of sales. A colleague swaps the two loops round, to go down the columns instead of along the rows.
The answer is the same, to the penny. The report now takes several times as long. Nothing about the work changed, only the order. The reason is the cache.
By the end of this lesson
Note
I can explain why a cache makes memory fast.
Key words
| Word | What it means | Example |
|---|---|---|
| Memory hierarchy | stores from small and fast to big and slow | |
| Cache | a small, fast memory holding copies of recently used data | |
| Cache line | the block of bytes a cache copies in one go | 64 bytes |
| Hit | the data wanted is already in the cache | |
| Miss | the data must be fetched from slower memory | |
| Locality | programs tend to reuse data, and data stored nearby |
The cells students fill in are left blank in this preview.
Memory comes in layers
A processor can do an add in well under a nanosecond. Reading main memory takes about a hundred times as long.
So computers keep a memory hierarchy. Close to the processor sit small, fast caches: L1, then L2, then often L3. Behind them is main memory, and behind that the disk. Each layer is bigger and slower than the one before.
Worked example: a typical laptop
| Layer | Typical size | Rough time to read |
|---|---|---|
| Registers | 32 of 8 bytes each | Under 1 nanosecond |
| L1 cache | 32 to 64 KB | About 1 nanosecond |
| L2 cache | Hundreds of KB to a few MB | A few nanoseconds |
| L3 cache | Several MB to tens of MB | 10 to 20 nanoseconds |
| Main memory | Several GB | About 100 nanoseconds |
| SSD | Hundreds of GB | Tens of thousands of nanoseconds |
The cells students fill in are left blank in this preview.
Go to the architecture folder
cd ~/archShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
How big is one cache line here?
getconf LEVEL1_DCACHE_LINESIZEShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A miss brings a whole line
A cache never copies just one byte. On a miss it copies a whole cache line, usually 64 bytes, from the layer below.
That pays off because of locality. A program soon reads data stored next to what it just read: spatial locality. It also reads the same data again: temporal locality. Either way, the next read is a hit.
Why row by row wins in loop.c
loop.c holds a table of 4096 rows of 4096 ints. An int is 4 bytes, so one row is 16384 bytes and one 64-byte line holds 16 numbers.
Row by row, one miss brings in the next 16 numbers, so 15 reads in 16 are hits. Column by column, each read is a whole row further on, in a different line. By the time the loop comes back to that line, it has gone.
Bytes in a row, numbers in a line
python3 -c "print(4096 * 4, 64 // 4)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Build the lab's loop program
gcc -O2 -o loop loop.cShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Time the two orders
./loopShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think the slower loop must be doing more work. It is not: both add the same 16777216 numbers and print the same sum. The difference is how often the processor waits for memory. When code is slow, count the misses as well as the steps.
Where a line goes in a direct-mapped cache
In a direct-mapped cache, each address has exactly one line it can go in. Split the address into three parts.
The offset is the address modulo the line size: which byte in the line. Divide by the line size to get the block number. The index is the block number modulo the number of lines: which line. The tag is what is left, and it says which block is in that line now.
Worked example: 4 lines of 16 bytes
| Address | Block | Index | Tag | Result |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | Miss: line 0 empty |
| 4 | 0 | 0 | 0 | Hit |
| 20 | 1 | 1 | 0 | Miss: line 1 empty |
| 64 | 4 | 0 | 1 | Miss: replaces block 0 |
| 0 | 0 | 0 | 0 | Miss: block 0 was replaced |
| 24 | 1 | 1 | 0 | Hit |
The cells students fill in are left blank in this preview.
Split 0x1234 for 8 lines of 64 bytes
python3 -c "print(0x1234 % 64, 0x1234 // 64 % 8, 0x1234 // 512)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Going further: a smaller table
Make a copy of loop.c with a table a quarter of the size by typing sed 's/4096/2048/' loop.c > half.c. Build it with gcc -O2 -o half half.c and run ./half a few times.
Before you run it, predict the sum. Then compare the gap between the two orders with the one for ./loop. Use your simulator to explain what you see.