Lesson 4 of 5
Memory Hierarchy, Cache and Why Loops Are Fast
Registers to cloud storage — and the cache maths that explains why one loop runs ten times faster than another.
Learn it
Fast memory is expensive and small; cheap memory is huge and slow. So computers use layers: registers, cache, RAM, SSD.
Cache holds copies of the data you used most recently, because programs tend to reuse the same data (temporal locality) and nearby data (spatial locality).
This is why looping across a row of a grid is far faster than looping down a column.
Key terms
- Temporal locality
- Recently accessed data is likely to be accessed again soon.
- Spatial locality
- Data near recently accessed data is likely to be accessed soon.
- Cache line
- The fixed-size block (often 64 bytes) that is transferred between cache and main memory.
- Hit rate
- The proportion of memory accesses that are satisfied by the cache.
Try it
Match each storage level to its realistic access time.
Challenge
Write two versions of a program that sums a 2000×2000 grid: one row-major, one column-major. Time both, then explain the difference using cache lines. Predict your answer before you run it.
Pick whichever way suits you — every mode earns the same bonus XP.
Write at least 40 more characters to submit.
Mark your own work
Guided walkthrough — 0/5 clues revealed
- Clue 1 locked — reveal it only if you get stuck.
- Clue 2 locked — reveal it only if you get stuck.
- Clue 3 locked — reveal it only if you get stuck.
- Clue 4 locked — reveal it only if you get stuck.
- Clue 5 locked — reveal it only if you get stuck.
Each clue costs 7 XP (never below 33 XP). You'd earn 65 XP right now.
Extension: Calculate the required hit rate for an average access time of 10 ns given a 2 ns cache and 90 ns RAM.