Skip to main content
Be Bitwise

Cache Hierarchy

Memory Fundamentals · Memory & Systems track

6 min read

Part ofSystems Programming Companion, week 7

In this module

The Speed Problem

Modern CPUs run billions of operations a second; main memory (DRAM) can't keep up. A single RAM access takes somewhere between 50 and 100 nanoseconds, and a 3 GHz processor could have ripped through 150 to 300 useful cycles in that gap. If the CPU had to wait on RAM for every memory reference it would spend most of its life twiddling its thumbs.

Cache is the answer. You park small amounts of very fast memory between the CPU and main RAM, and the CPU can usually find what it needs there.

L1, L2, and L3

Cache is organised in levels, each one trading capacity against speed:

LevelTypical SizeLatencyLocation
L132-64 KB per core~1 nsInside each CPU core
L2256 KB-1 MB per core~3-5 nsPer core, on chip
L34-64 MB shared~10-20 nsShared across all cores

When the CPU needs data it checks L1 first, then L2, then L3, then ultimately main memory. Finding what you wanted in cache is a cache hit. Striking out across every level and falling through to RAM is a cache miss.

Key Concept

Cache is a small, fast memory that sits between the CPU and RAM. It is organised in levels (L1, L2, L3) where each level is larger but slower. A cache hit finds data in cache; a cache miss forces a slower trip to main memory.

Why Caching Works: Locality

Cache works because real programmes touch memory in predictable patterns, not at random:

  • Temporal locality: if you used a piece of data recently, odds are good you'll use it again soon. The loop counter you read every iteration is the canonical example.
  • Spatial locality: if you touched one address, you'll probably touch nearby addresses next. Iterating an array one element at a time is the obvious case.

On a cache miss the system doesn't just grab the byte you asked for. It loads an entire cache line, usually 64 bytes, scooping up the neighbours along the way. That's spatial locality being cashed in: the next several accesses tend to hit data that's already in the cache.

Worked Example: Counting Misses

Take an array of one million ints, 4 bytes each, so 4 MB in total. Assume none of it is cached yet and lines are 64 bytes. Every line holds 16 ints.

Loop 1: sum every element in order. The first access to each line misses and drags in all 16 of its ints, then the next 15 accesses hit. One million accesses, roughly 62,500 misses: one in sixteen.

Loop 2: sum every sixteenth element (i += 16). Now every access lands in a different line, and nothing you load gets reused. 62,500 accesses, roughly 62,500 misses: every single one.

Loop 2 does one sixteenth of the arithmetic and makes the same number of trips to RAM. On real hardware it doesn't come close to running sixteen times faster, because those trips to memory were most of the cost all along. Hardware prefetchers soften this for simple, predictable strides, but the principle holds: you pay per line, not per byte.

You can run a shrunk-down copy of both loops on the simulators below. To keep the display readable, this cache has 16-byte lines instead of 64, so each line holds four ints and the ratios become one in four rather than one in sixteen. The first simulator reads 16 ints in order (byte addresses 0, 4, 8 and so on). Press Run and count: 4 misses, 12 hits.

Sequence [0/16]:
500ms
04812162024283236404448525660
Hits: 0Misses: 0Rate: 0.0%

Cache Contents(Direct-Mapped, 8 lines, 16B/line)

IndexVTagData
00--
10--
20--
30--
40--
50--
60--
70--

The second reads every fourth int, so each address is 16 bytes past the last and lands in a fresh line. Same 16 reads, 16 misses.

Sequence [0/16]:
500ms
0163248648096112128144160176192208224240
Hits: 0Misses: 0Rate: 0.0%

Cache Contents(Direct-Mapped, 8 lines, 16B/line)

IndexVTagData
00--
10--
20--
30--
40--
50--
60--
70--

The same effect bites two-dimensional arrays. C stores int grid[1024][1024] row by row, so grid[r][c] and grid[r][c+1] are neighbours, but grid[r][c] and grid[r+1][c] are 4 KB apart. Walk it row by row and you get the one-in-sixteen pattern. Walk it column by column and every access can miss.

Predict: an array of 16-byte structs, read in order from start to finish. Roughly what fraction of accesses miss?

About one in four. A 64-byte line holds four 16-byte structs, so each miss brings in that struct and the next three. Bigger elements mean fewer per line and more misses, which is why shrinking a hot struct can speed up code that never changed its algorithm.

Cache Performance Matters

The gap between cache-friendly and cache-hostile code is enormous. Walking an array in order (good spatial locality) can run 10 to 100 times faster than the same logic with random memory access patterns. That's why an intuition for cache behaviour pays off even when you never deal with cache hardware directly.

You can watch the worked example happen. This program sums a 32 MB array three ways: every element in order, every sixteenth element, and the same number of reads at random positions.

Try itChange STRIDE to 8: twice the reads, the same cache lines. Does the time double?
C (GCC 9.2.0)

Read the last column. The runner compiles without optimisation, so most of the sequential loop's cost is loop overhead, and the stride-16 loop should still take well over a sixteenth of its time, because it pulls in every cache line the sequential loop did. The random reads cost the most per access, since the prefetcher can't guess where the next one lands. Exact figures depend on whichever machine picks up the job and wobble from run to run; the ratios are the part to look at.

It also matters for security, in a way that surprised the industry. Whether a load hits or misses is visible in its timing, and timing can be measured. Spectre and Meltdown both use cache hits and misses as a side channel to read memory they had no right to see. You'll get there in CPU Pipeline & Microarchitecture and Side-Channel Attacks.

Curious what the machine running your code actually has? On Linux, glibc will tell you through sysconf:

Try itCompare the sizes with the table at the top of this lesson.
C (GCC 9.2.0)

Inside a virtual machine some of these can come back as zero or "not reported", because the hypervisor decides what the guest is told about its CPU. And if the L3 turns out to be 32 MB or more, part of the benchmark's array fits in it, which flatters the random reads.