yeolyi.comSeongyeol's CS

Caches

Every time the CPU fetches a value from memory, it waits hundreds of clocks. But programs read clustered in narrow regions, so if we move just those regions into a small, fast store, most reads won’t have to wait.

The cache

The large, slow store we’ve been calling memory is usually called RAM. A small, fast memory placed between the CPU and RAM is a cache. When the CPU needs a value, it looks in the cache first.

Address to read
Cache
····
RAM
Holds every address
  1. Press one address twice.
  2. Press five different addresses.

At first the cache is empty, so it’s a miss; reading the same address again is a hit. The cache has only 4 slots, so when a fifth address comes in, the value used longest ago is evicted.

The fraction of all accesses that are hits is the hit rate. The higher the hit rate, the less time the CPU spends waiting for RAM.

Locality and the hit rate

Let’s change only the order of reads, with the same 4-slot cache. First, we read 0–3 twice, then 4–7 twice.

0123012345674567
Cache····
Hit rate 0% (0/0)

The cache is empty.

Press next to read one at a time. Filled slots are hits, faded ones are misses.

Only the first read of each address misses. An address read once is read again soon, thanks to temporal locality.

Next, we read 0 through 15 in order.

0123456789101112131415
Cache····
Hit rate 0% (0/0)

The cache is empty.

No address is read twice, so every read misses. But on a miss, instead of fetching just that address, we could fetch the whole block of four slots that contains it.

0123456789101112131415
Cache····
Hit rate 0% (0/0)

The cache is empty.

One miss brings in the 4 nearby slots, so the next three reads are hits, thanks to spatial locality. Real caches also fetch tens of nearby bytes as one block on a miss.

Finally, let’s read at random.

161341551461014713510910
Cache····
Hit rate 0% (0/0)

The cache is empty.

With no locality, the hit rate is low and the cache doesn’t help much.

Wrapping up

Even one small cache lets most reads finish without going all the way to RAM, thanks to locality. Then would a bigger cache be better? A bigger cache means a wider circuit, so signals travel farther to reach the slot they want, and it gets slower. In the next post, let’s look at how to get both size and speed.

Challenge

The cache has 4 slots, starts empty, and when full evicts the one used longest ago. We read addresses 0, 1, …, k − 1 in order, over and over for many rounds. What is the smallest k for which there is not a single hit from the second round on? Answer with a number.