20. Prefetching and branch prediction

Same data, different order

Here are two loops over the same million particles. The first goes in order. The second visits them in a shuffled order, given by an index array idx:

// in order
for (let i = 0; i < n; i++) {
  s += x[i] + vx[i];
}
// shuffled
for (let i = 0; i < n; i++) {
  const j = idx[i];
  s += x[j] + vx[j];
}

Both read every particle exactly once, so they fetch essentially the same cache lines (the shuffled one also reads idx). Chapter 19 says they should cost about the same. They don’t. This book’s benchmark has a shuffled loop like the second one (random-x) and an in-order loop over the same particles that does more work per particle (update-xy reads four fields and writes two):

Less work, more time. Order matters, and the reason is that the CPU is quietly guessing what you will do next.

The prefetcher

It also answers a question chapter 19 left open. If each line had cost a full trip to memory, around a hundred nanoseconds, the every-8th loop over a million lines would have needed about a tenth of a second. It usually takes far less, because the prefetcher was running ahead. A shuffled order gives it nothing to follow, so every miss is paid in full.

Try it. This reads every element of one big Float64Array exactly once, first in order and then in a shuffled order:

const n = 1 << 22; // 4M doubles: 32 MB
const x = new Float64Array(n);
const inOrder = new Int32Array(n);
for (let i = 0; i < n; i++) {
  inOrder[i] = i;
}

// shuffle a copy (Fisher-Yates)
const shuffled = inOrder.slice();
for (let i = n - 1; i > 0; i--) {
  const r = Math.random() * (i + 1);
  const j = Math.floor(r);
  const t = shuffled[i];
  shuffled[i] = shuffled[j];
  shuffled[j] = t;
}

function sum(order) {
  const t0 = performance.now();
  let s = 0;
  for (let i = 0; i < n; i++) {
    s += x[order[i]];
  }
  return performance.now() - t0;
}

sum(inOrder);
sum(shuffled); // warm up
const a = sum(inOrder).toFixed(1);
const b = sum(shuffled).toFixed(1);
console.log('in order, ms:', a);
console.log('shuffled, ms:', b);

Pointer chasing

Arrays of objects have a second problem, and the chart shows it: the shuffled loop hurts objects far more than typed arrays. With typed arrays, the CPU computes the address of x[j] from j straight away, so it can send off several reads and wait for them all at once^[3]. With objects, the address of ps[j].x is stored inside memory: first load the pointer from the array, then follow it.

The linked list you summed in chapter 17 is the purest example. Each node tells you where the next one is, so you can only ever be at one node at a time.

The pipeline

A CPU does the same with instructions. Step through it:

What makes a branch easy to guess?

Branch predictors learn from history. Branches that almost always go one way, like a loop’s i < n, are guessed right nearly every time. Branches with no consistent pattern are where they go wrong^[6]. Step through a toy predictor that always guesses “same as last time”:

for (const v of xs) {
  if (v < 50) s += v;
}

Real predictors find far subtler patterns than this toy. But they share its blind spot: random data. A well-known experiment sums the elements below 50 of an array of random numbers. In compiled C++ on a modern CPU, sorting the array first made the loop several times faster, because the branch became predictable^[5]. How much of this shows up in JavaScript depends on the machine code the engine generates, so measure before you rely on it.

Your turn

function mispredicts(outs) {
  // your code here
}

const xs = [12, 30, 71, 5, 88];
const outs = xs.map((v) => v < 50);
console.log(mispredicts(outs));

function findStride(xs) {
  // your code here
}

console.log(findStride([0, 8, 16, 24]));

What you learned

• The prefetcher fetches lines before you ask, when your reads follow a simple pattern: in order, backwards, or a steady stride.
• Pointer chasing defeats it: each address is only known once the previous load arrives, so every miss is paid in full.
• A pipeline works on many instructions at once, like an assembly line.
• To keep it full, the CPU uses branch prediction: it guesses which way each if goes. Wrong guesses throw work away.
• Predictable data (sorted, or rarely-taken checks) keeps guesses right. Random data doesn’t.

That’s the end of Day 5. Tomorrow: SIMD, how JavaScript stores numbers and objects, and AoS against SoA, measured.