Page 4: Memory Hierarchy: CPU Caches, RAM Address Spaces, and Persistent Storage
A cache-friendly loop over a contiguous array can run 5x to 20x faster than traversing scattered objects across memory, even when both algorithms perform the exact same number of steps.
A fundamental physics constraint governs computer hardware: storage that is physically tiny and wired right next to the ALU is extraordinarily fast, whereas storage large enough to hold gigabytes or terabytes of data must sit further away on the motherboard and takes much longer to access. A CPU register access takes roughly 0.3 nanoseconds, while reading from main RAM takes roughly 60 to 100 nanoseconds—more than 200 times slower.
If the CPU had to wait 200 clock cycles every time it needed a variable from RAM, it would spend most of its time stalled. To bridge this speed gap, processors place tiered static-RAM caches (L1, L2, and L3) between the registers and main memory. Understanding how this memory hierarchy operates explains why data layout and access patterns often matter just as much as theoretical Big-O complexity.
4.1 Latency Numbers Every Engineer Should Understand
The memory hierarchy is organized as a pyramid. At the top sit CPU registers (tens of bytes, <0.5 ns latency). Below registers sit L1 cache (~32–64 KB per core, ~1 ns), L2 cache (~512 KB–1 MB per core, ~4 ns), and shared L3 cache (~16–64 MB, ~12 ns).
Main system RAM (DRAM) provides gigabytes of capacity at ~80 ns latency, but it is volatile—when power is lost, all RAM contents vanish. Persistent storage (NVMe SSDs at ~20,000–100,000 ns and network storage at millions of nanoseconds) retains data across power cycles.
4.2 Cache Lines, Spatial Locality, and Temporal Locality
When the CPU requests a single 8-byte number from RAM, the memory controller does not fetch just 8 bytes. Instead, it fetches an entire 64-byte chunk called a cache line into the L1 cache. If your program immediately reads the adjacent elements in an array, those values are already sitting in L1 cache!
Hardware caches exploit two predictable program behaviors: temporal locality (if you accessed a memory address recently, you are likely to access it again soon) and spatial locality (if you accessed address $X$, you are likely to access address $X + 1$ soon).