18. The CPU and its caches

The same loop, two speeds

Here’s a loop you have written many times, run over the particles from chapter 3. It adds up every mass:

let s = 0;
for (let i = 0; i < ps.length; i++) {
  s += ps[i].mass;
}

This book’s benchmark ran exactly this loop on a thousand particles and on a million. The work per particle is identical: one read, one add. Yet the time per particle was not.

Nothing about the code changed. Only the amount of data did. To see why, you need to meet the machine that runs the loop.

The CPU: a very fast, very simple worker

Step through one turn of the loop. The instructions here are made up and simplified, but the shape is real.

load r1, [r2]    ; r1 = xs[i]
add  r0, r0, r1  ; s = s + r1
add  r2, r2, 8   ; next element

The warehouse problem

Adding two registers takes the CPU almost no time. Fetching a number from main memory takes a very long time by comparison. On the CPUs Apple describes, a read that has to go all the way to main memory is about fifty times slower than the fast path^[1]. A rough 2021 table for ordinary hardware tells the same story: about 2 nanoseconds for the fastest cache, about 100 for main memory^[2]. Exact figures differ from chip to chip. The gap of one to two orders of magnitude is what matters.

Nanoseconds are hard to feel. Stretch time so that an L1 hit takes one second, and see how long the other trips take:

// Rough 2021 latencies in ns (Slotin)
const levels = [
  { name: 'L1', ns: 2 },
  { name: 'L2', ns: 5 },
  { name: 'L3', ns: 20 },
  { name: 'RAM', ns: 100 },
];
for (const l of levels) {
  const secs = l.ns / 2;
  console.log(l.name, secs, 'seconds');
}

Hits and misses

Now follow one read through the ladder, then a second read of the same thing, then a read of something new.

s += a.x; // first time
s += a.x; // again, soon after
s += b.x; // somewhere new

You can do the arithmetic yourself. Say a hit costs 2 nanoseconds and a miss 100. If 1 read in 10 misses, what does an average read cost?

// 9 hits at 2 ns, 1 miss at 100 ns
const avg = (9 * 2 + 1 * 100) / 10;
console.log(avg); // 11.8

Even a 90% hit rate leaves reads several times slower than all hits. That is why the million-particle loop slowed down. A thousand particles fit in the caches, so once the loop has run, nearly every read hits. For a million particles, the six 8-byte numbers alone come to 48 megabytes, far more than the caches hold, so the loop keeps missing.

Your turn

function countMisses(addrs, n) {
  // your code here
}

// expect 1:
console.log(countMisses([5, 5, 5], 4));

function avgTime(rate, hit, miss) {
  // your code here
}

// expect 11.8:
console.log(avgTime(0.9, 2, 100));

What you learned

• The CPU fetches, decodes and executes one instruction after another, working on values held in registers.
• Main memory is far slower than the CPU, so a cache hierarchy (L1, L2, L3) keeps recently used data close by.
• Latency is how long one access takes. A hit in L1 takes a few nanoseconds; a trip to main memory takes around a hundred.
• A cache miss sends the CPU further down the hierarchy. A handful of misses can dominate a loop.
• When data outgrows the caches, the same loop gets slower per element.