Lesson 3 of 7

The Memory Hierarchy & Caches

Reading from RAM takes around 200 CPU cycles, so CPUs keep copies of recently used in small, fast . You'll learn how caches work and how to write code that uses them well.

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- 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];

Common question

Do all memory accesses cost the same?

Memory is layered: registers, then several levels of cache, then main memory, then storage. Each level is bigger and much slower than the one above. The hardware moves data between levels in fixed-size chunks called lines, betting that a program will soon reuse what it just touched and touch what sits next to it.

Write code that makes that bet pay off. Prefer contiguous arrays to scattered structures, walk data in the order it is stored, keep the data you are working on small, and do work in one pass instead of many. For data that fits in memory, these choices often matter more than Big O.

Source: A clock cycle on a modern processor is under a nanosecond; a trip to main memory takes around eighty. The processor could run hundreds of instructions in the time one cache miss takes.

Common mix-ups

Each of these sounds reasonable. Think about why it is wrong, then open the explanation.

  • Reading any is a single instruction, so every read costs the same.

  • More memory makes a program faster.

  • The cache is managed by the operating system.

Finished reading?Mark it done to track your progress.

Tip: use the ← and → keys to move between lessons.