19. Cache lines and locality

Fewer reads, same time?

Here is a strange experiment. Make a big Float64Array, then add 1 to every element. Then do it again, but only to every 8th element:

for (let i = 0; i < n; i += 1) xs[i] += 1;
for (let i = 0; i < n; i += 8) xs[i] += 1;

The second loop does one eighth of the work. You would expect it to take one eighth of the time. Try it:

const n = 1 << 23; // 8M doubles: 64 MB
const xs = new Float64Array(n);

function touch(step) {
  const t0 = performance.now();
  for (let i = 0; i < n; i += step) {
    xs[i] += 1;
  }
  return performance.now() - t0;
}

touch(1);
touch(8); // warm up first
// performance.now() is a clock in ms
const a = touch(1);
const b = touch(8);
console.log('all ms:', a.toFixed(1));
console.log('8th ms:', b.toFixed(1));
const r = (a / b).toFixed(1);
console.log('8th was', r, 'x faster');

If your machine behaves like most, the second loop is nowhere near eight times faster. Something other than the number of reads is setting the pace.

Memory moves in blocks

The box is called a cache line. On most processors it is 64 bytes ^[1]: Linux assumes 64-byte lines for 64-bit x86 and for 64-bit ARM^[4]. Some chips use bigger lines; Apple describes its caches as using 64- or 128-byte lines^[5]. This book uses 64.

Eight float64s fill one line. So every eighth element of xs is in a different line, and the second loop still has to fetch every line of the array. Same lines, same trips to memory, nearly the same time.

Memory is divided into lines at fixed boundaries, so working out which line an address is in is one division:

const line = Math.floor(addr / 64);
// addresses 0..63 are line 0,
// 64..127 are line 1, and so on.

Counting lines, not reads

Now go back to chapter 18’s loop, summing every mass, and count lines. The objects here use a toy layout, one per line, to keep the picture simple.

s += ps[i].mass;    // objects
s += mass[i];       // Float64Array

The objects need a new line for every particle, plus the lines holding the pointers. The Float64Array needs one line per eight particles. That is the right way to think about memory cost: count the lines a loop touches, not the values it reads^[1].

Temporal locality is about when. These two loops do the same sums:

// two passes: xs is fetched twice
for (const v of xs) a += v;
for (const v of xs) b += v * v;

// one pass: each line is used for both
for (const v of xs) {
  a += v;
  b += v * v;
}

If xs is too big for the caches, the second pass of the first version finds its early lines long gone and fetches everything again. The fused loop uses each value while it is still hot.

Stride

The gap, in bytes, from one read to the next is the loop’s stride. Step through three layouts of the same masses:

Fetching unused bytes costs more than time spent waiting. It also uses up bandwidth: how many bytes per second can flow from memory to the CPU. A rough 2021 table puts main memory at around ten gigabytes per second, and L1 several times higher^[3]. A loop that streams through a big array is limited by that flow. If only 8 bytes of every 64 are useful, seven eighths of the flow is wasted.

This book’s benchmark measured exactly these three layouts:

The order matches the line counts. The packed buffer removes the objects and pointers, but it still drags five unused fields through the cache for every mass. The struct of arrays fetches nothing it doesn’t use.

Now measure it on the device you are reading this on. Pick “sum every mass” to repeat the chart above, or the particle update loop, x += vx.

Your turn

function countLines(addrs) {
  // your code here
}

// expect 2:
console.log(countLines([0, 8, 63, 64]));

function fieldLines(n, k) {
  // your code here
}

// expect 6:
console.log(fieldLines(8, 6));

What you learned

• Memory moves in cache lines: 64-byte blocks on most mainstream processors. The line of address a is Math.floor(a / 64).
• Count lines touched, not values read.
• Spatial locality: use data near what you just used. Temporal locality: use the same data again soon.
• Stride is the distance between consecutive accesses. Small strides share lines; strides of 64 bytes or more pay for a line every read.
• Bandwidth is how many bytes per second can flow. Unused bytes in a line waste it.