CAComputer Architecture · Lesson 3 of 7

The Memory Hierarchy & Caches

RAM is ~200 cycles away from the CPU. That's an eternity when you execute 4 instructions per cycle — so CPUs keep copies of recently-used memory in caches. Cache behavior explains more real-world performance than algorithmic complexity does.

Text
The hierarchy (typical modern desktop):

  Registers      ~0 cycles      ~1 KB total
  L1 cache       ~4 cycles      32-64 KB per core
  L2 cache       ~12 cycles     512 KB - 2 MB per core
  L3 cache       ~40 cycles     16-64 MB shared
  RAM            ~200 cycles    16-64 GB
  SSD            ~100,000 cyc   1-4 TB
  Network        ~10,000,000+   the internet

Each level: ~10x bigger, ~4-10x slower.

Caches work because of locality. Temporal locality: memory you just used, you'll likely use again. Spatial locality: memory near what you just used, you'll likely use next. Caches exploit the second by loading memory in 64-byte cache lines — touch one byte and the surrounding 64 arrive for free. Code that walks memory in order rides this; code that jumps around fights it.

C
// Same work, wildly different speed — traversal order matters:
#define N 4096
int grid[N][N];

// Row-major: walks memory sequentially. Cache-friendly.
for (int row = 0; row < N; row++)
    for (int col = 0; col < N; col++)
        sum += grid[row][col];

// Column-major: jumps N*4 bytes every access.
// Each read misses cache. Often 5-10x SLOWER:
for (int col = 0; col < N; col++)
    for (int row = 0; row < N; row++)
        sum += grid[row][col];
✦ Tip
This is why arrays usually crush linked lists in practice even when big-O says they're equal: array elements are adjacent (cache lines full of useful data), list nodes are scattered (every next-pointer a likely cache miss). Data layout is a first-class performance decision.
◆ Note
Virtual memory: each process sees its own private address space; hardware (the MMU, using page tables) translates virtual addresses to physical RAM in 4KB pages. This gives isolation (one program can't read another's memory), and lets the OS swap unused pages to disk. A 'segmentation fault' is the MMU catching an access to a page you don't own.