98. Access patterns

One shape, two loops

Chapter 23 showed that struct of arrays wins most when a loop reads only some of the fields. Here are two suites from this book’s benchmark run. Both use the same six-field records; one loop reads every field, the other reads one:

The collection is the same. What differs is the loop. So before it can decide anything, Viscosity needs to know, for every loop, what that loop does to the collection’s fields.

In Viscosity it is one record per loop, from packages/core/src/analysis.ts:

interface LoopAccess {
  func: string;   // the enclosing function
  line: number;   // the loop's header line
  depth: number;  // 0 = not in a loop
  reads: Set<string>;
  writes: Set<string>;
  /** estimated iterations per
   *  execution, if known */
  trips: number | null;
}

Filing every access under a loop

By this point the safety pass (chapter 99) has already collected every element access: each field.get and field.set whose object is an element ps[i]. Note that ps[i].x += 1 is two accesses, a read and a write. Building the table is a matter of filing each one under the innermost natural loop around it. Step through it:

const ps = [];
for (let i = 0; i < 1000; i++)
  ps.push({ x: i, y: 0, vx: 1, vy: 2 });
for (let t = 0; t < 60; t++) {
  for (let i = 0; i < ps.length; i++) {
    ps[i].x += ps[i].vx;
    ps[i].y += ps[i].vy;
  }
}
let s = 0;
for (let i = 0; i < 10; i++) s += ps[i].x;
console.log(s, ps[0].y);

The real loop is short. Simplified:

for (const a of c.accesses) {
  const f = funcOf.get(a.inst);
  const l = loopOf(loops(f), a.inst.block);
  const key = l ? f.id + ':' + l.header
                : f.id + ':none';
  let la = byLoop.get(key);
  if (!la) {
    la = { func: f.name, line: lineOf(l),
      depth: l ? l.depth : 0,
      reads: new Set(), writes: new Set(),
      trips: l ? tripCount(f, l) : 1 };
    byLoop.set(key, la);
  }
  const set = a.kind === 'read'
    ? la.reads : la.writes;
  set.add(a.field);
}

loopOf picks the smallest loop whose body contains the access’s basic block, and the key is the loop’s header block, so two accesses in the same loop always share a row. Printing the real rows for the program in the diagram gives (reformatted):

<module> line 5 depth 2 trips null
  reads vy, y, vx, x  writes y, x
<module> line 11 depth 1 trips 10
  reads x
<module> line 12 depth 0 trips 1
  reads y

The fields come out in the order the analysis happened to find them, which is fine: they are sets. Because the key includes the function, loops in different functions get different rows. In the corpus file interproc_ok.js, bodies is passed to two functions, and explain reports a loop in each:

bodies (line 2) {x, y, m} → struct of
  arrays
  · loop at line 7 in centerOfMass()
    touches 2 of 3 fields (x, m)
  · loop at line 11 in drift() touches 1
    of 3 fields (x)

Depth and trips

Depth comes from the natural loops of chapter 83: a loop’s depth is one more than the number of larger loops that contain its header. The inner loop in the diagram is inside the t loop, so it has depth 2.

Trips is harder, and Viscosity only tries the easiest case: the loop’s condition is i < c or i <= c for a constant c, where i is an induction variable that starts at 0 and steps by 1. Simplified:

const tripCount = (f, l) => {
  const t = f.blocks[l.header].term;
  if (t.kind !== 'condbr') return null;
  const cond = inst(t.cond);
  if (cond.operator !== '<' &&
      cond.operator !== '<=') return null;
  const [iv, bound] = cond.args.map(inst);
  if (!isCountingPhi(iv, true) ||
      bound.op !== 'const') return null;
  return cond.operator === '<'
    ? bound.value : bound.value + 1;
};

So i < ps.length has no trip count: the length isn’t a constant in the code. Neither does i < 64 * 64, because the bound is an expression, not a constant. That one is from nested_loops.js, where explain says “size unknown statically”. Today the trip counts feed exactly that line: a push inside loops with known trip counts adds their product to the size estimate, and the next chapters’ cost model looks at the size.

Hot loops

Before the program runs, nobody knows for sure which loops are hot. Viscosity uses the weakest sign that can be checked statically: an access counts only if it is in a loop at all. The planner, in plan.ts, throws away the depth-0 rows:

const fieldLoops =
  c.loops.filter((l) => l.depth > 0);
if (fieldLoops.length === 0)
  keep('no loop reads or writes its ' +
    'fields, so a new layout cannot ' +
    'pay off');

That is the whole story of the corpus file no_loops.js, which fills ps in a loop but only ever reads ps.length:

ps (line 2) {x} → kept as array of
  objects
  · no loop reads or writes its fields,
    so a new layout cannot pay off

Depth and trip counts are recorded, but the planner doesn’t yet weigh one loop against another with them. A loop that runs ten times and a loop nested three deep both count. Chapter 109 replaces this guess with measurements from a real run.

Your turn

function loopTable(accs) {
  const table = {};
  // your code here
  return table;
}

console.log(loopTable([
  { loop: 'L5', field: 'x',
    kind: 'read' },
  { loop: 'L5', field: 'x',
    kind: 'write' },
]));

function describeLoop(row, F) {
  // your code here
}

console.log(describeLoop({
  func: 'drift', line: 11, depth: 1,
  reads: ['x'], writes: ['x'],
}, 3));

What you learned

• A loop’s access pattern is its read set, write set, nesting depth and trip count for one collection.
• Viscosity files every element access under the innermost natural loop around it, one row per loop per function. Accesses outside any loop get a depth-0 row.
• x += 1 is a read and a write. Rows hold sets of fields.
• Trip counts are known only for loops like i < 10 counting from 0 by
  1. Today they only feed the size estimate.
• A hot loop is where the time goes. Before the program runs, Viscosity’s stand-in is “in a loop”: with no field access in any loop, it keeps the array of objects.