Predict the Speedup on Paper Before You Change a Line

Last timeIt Fetches More Than You Asked For

Splitting one array of records into several arrays of fields is the single highest-value layout change, and the gain is calculable from two numbers before you write any code.

Records together, or fields together

A collection of things with several properties each can be stored two ways.

The familiar way is one array of records, each record holding all the

properties of one thing. It matches how people think, it matches how most

languages encourage you to write, and it is right when your code works with

one whole thing at a time.

The other way is several arrays, one per property, with the properties of one

thing sitting at the same index in each. It reads worse and it is right when

your code sweeps one property across everything.

FIG 1The same data, both ways

plaintext

one array of records

  record Particle
      position      12 bytes
      velocity      12 bytes
      colour        16 bytes
      flags         16 bytes
  particles: array of 1000000 Particle

  loop over particles
      total = total + p.position.x

several arrays of fields

  xs: array of 1000000 values
  ys, zs, velocities, colours, flags: likewise

  loop over xs
      total = total + xs[i]

The lower loop reads the same numbers in the same order and produces the same answer. The difference is that its values sit four bytes apart instead of fifty-six, so every block fetched delivers sixteen of them instead of one.

Now apply the previous lesson. The upper loop touches a new sixty-four byte

block for nearly every particle and uses four bytes of it. The lower loop

touches one block per sixteen particles and uses all of it. The amount of

arithmetic is identical.

Predicting the gain

The useful part of this is that you do not have to try it to find out whether

it is worth doing.

The lesson stops here

4 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

Predict the Speedup on Paper Before You Change a Line

Records together, or fields together

Predicting the gain

4 more paragraphs to go

This is the reading half

Read alongside