107. AoSoA code generation

One comment, a different layout

Viscosity never picks AoSoA on its own. You ask for it, with chapter 102’s annotation on the line before the array. This is the corpus program aosoa.js:

// @viscosity aosoa(8)
const ps = [];
for (let i = 0; i < 1003; i++)
  ps.push({ x: i, y: -i, z: i / 2 });
for (let r = 0; r < 2; r++) {
  for (let i = 0; i < ps.length; i++) {
    const p = ps[i];
    p.x += p.z;
    p.y -= 1;
  }
}

(Long lines are wrapped here, and the final printing loop is left out.) viscosity explain agrees (the two loop lines and the bounds line are left out):

ps (line 3) {x, y, z} → AoSoA, blocks of 8
  · annotated @viscosity aosoa(8) at line 2
  · typed Float64Array columns for all 3
    fields
  · about 1003 elements

Blocks and lanes

Every field of every element goes into one Float64Array called data. Here is how the compiler finds a slot in it:

// fields x, y, vx (F = 3), B = 8
// slot of field k of element i:
  (i >> 3) * 24   // block start
+ k * 8           // field in block
+ (i & 7)         // lane

i >> 3 and i & 7 are chapter 16’s bitwise operators. They work on 32-bit integers^[4], which is plenty for an array index. For a power of two, dropping the low bits is dividing and rounding down, and keeping them is the remainder.

The generated container

Here is what Viscosity writes for aosoa.js, reformatted to fit the screen, with the static of method left out:

class __Vsc_ps {
  constructor(cap = 16) {
    this.length = 0;
    this.cap = Math.ceil(cap / 8) * 8;
    this.data =
      new Float64Array(this.cap * 3);
  }
  push(v0, v1, v2) {
    const n = this.length;
    if (n === this.cap) this.grow();
    const b = (n >> 3) * 24 + (n & 7);
    this.data[b + 0] = v0;
    this.data[b + 8] = v1;
    this.data[b + 16] = v2;
    return (this.length = n + 1);
  }
  grow() {
    const d = new Float64Array(
      this.cap * 2 * 3);
    d.set(this.data);
    this.data = d;
    this.cap *= 2;
  }
}

Three things to notice. The capacity is rounded up to whole blocks, and doubling keeps it that way. push works out the slot of field 0 once, then adds k * 8 for the others. And grow() is simpler than SoA’s: blocks never move inside the array, so a bigger array is just the old blocks followed by new empty ones, and one set copies everything.

The rewritten accesses

The inner loop becomes this (each statement is one line in the real output; it is wrapped here):

for (let i = 0; i < ps.length; i++) {
  const p = i;
  ps.data[((p) >> 3) * 24 + 0
    + ((p) & 7)] +=
      ps.data[((p) >> 3) * 24 + 16
        + ((p) & 7)];
  ps.data[((p) >> 3) * 24 + 8
    + ((p) & 7)] -= 1;
}

const p = ps[i] became const p = i, as in chapter 104, and each field access became the formula with F*B = 24 and k*B filled in. The formula mentions the index twice. That is fine for a name like p, but the last line of aosoa.js reads ps[1002].z, which isn’t proven in bounds, so its index is wrapped in the bounds check. Evaluating that twice would be wasteful, so the emitter calls a helper that takes the index once:

ps.data[__vsc_aosoa(
  __vsc_bc(ps, 1002, 'z', false),
  3, 24, 16, 7)]

function __vsc_aosoa(i, sh, stride,
    off, mask) {
  return (i >> sh) * stride + off
    + (i & mask);
}

Both versions of aosoa.js print 1505503 501 14 -10.

Only numbers

Because everything sits in one Float64Array, every field must be a proven number. Add a string field and Viscosity refuses:

ps (line 2) {x, name} → kept as array of
  objects
  · annotated aosoa, but fields name may
    hold non-numbers

A block size that isn’t a power of two is refused the same way. Put aosoa(6) on the playground program below, and the planner keeps the objects, so the compiled code is the source unchanged:

ps (line 2) {x, y, vx} → kept as array
  of objects
  · annotated aosoa(6), but the block
    size must be a power of two (2, 4,
    8, 16, ...)

The emitter still checks log2(B) and throws if it is not a whole number, but the planner never hands it such a block size now. Try the annotation yourself. Change 8 to 4, delete the annotation (Viscosity picks plain SoA), or add id: 'a' to the record:

Is it worth it?

ISPC builds this layout into the language: soa<8> Point pts[...] stores 8 x values, then 8 y, and pts[10].x still works: the compiler reads the third x of the second block, exactly our formula^[1][2]. There, a block of 8 lines up with the SIMD lanes the program runs on, and ISPC’s guide recommends these layouts because contiguous data allows vector loads and stores^[3]. Plain JavaScript gets no such lanes, and the index arithmetic remains.

This book’s findings put it plainly: AoSoA with blocks of 8 was rarely better than SoA in V8, and at 1,000 elements it was often slower than plain objects. That is why the cost model never chooses it, and why it exists only behind an annotation.

Your turn

function slot(i, k, F, B) {
  // your code here
  return 0;
}

console.log(slot(10, 1, 3, 8));

function blockSum(data, n, k, F, B) {
  // your code here
  return 0;
}

What you learned

• // @viscosity aosoa(8) asks for AoSoA. Every field must be a proven number, and the block size must be a power of two.
• The block size B sets the layout: field k of element i is at (i >> s) * F*B + k*B + (i & (B-1)).
• The container keeps one Float64Array, with capacity in whole blocks; growing is a single copy.
• Complicated indexes go through __vsc_aosoa, so they are evaluated once.
• In V8, AoSoA rarely beat SoA and lost at small sizes, so the cost model never picks it.