103. Generating SoA storage

Where do the columns live?

The planner has said soa. Now the compiler has to change this line:

const ps = [];

into storage for one array per field. Viscosity’s answer is to write a small class at the top of your file, and replace the empty array with an instance of it:

const ps = new __Vsc_ps();

Everything about the new layout lives inside that class. The rest of the program talks to it through push, length, and one column per field, which chapter 104 wires up.

The generated class

Here is what Viscosity emits for ps, whose records are { x, vx }. The compiler writes each member on one long line; it is reformatted here to fit the page, with nothing else changed:

// Generated by Viscosity: "ps" stored as
// a struct of arrays (fields x, vx).
class __Vsc_ps {
  constructor(cap = 16) {
    this.length = 0; this.cap = cap;
    this.x = new Float64Array(cap);
    this.vx = new Float64Array(cap);
  }
  static of(...v) {
    const c = new __Vsc_ps(
      Math.max(16, v.length / 2));
    for (let i = 0; i < v.length; i += 2)
      c.push(v[i + 0], v[i + 1]);
    return c;
  }
  push(v0, v1) {
    const n = this.length;
    if (n === this.cap) this.grow();
    this.x[n] = v0; this.vx[n] = v1;
    return (this.length = n + 1);
  }
  grow() {
    const cap = (this.cap *= 2); let t;
    t = new Float64Array(cap);
    t.set(this.x); this.x = t;
    t = new Float64Array(cap);
    t.set(this.vx); this.vx = t;
  }
}

Member by member:

• constructor sets length (how many elements are in use) and cap (how many slots each column has), and makes the columns. A new Float64Array is filled with zeros^[2].
• push(v0, v1) takes one value per field, in the shape’s field order, writes them into the same slot of every column, and returns the new length, just as Array.prototype.push does. A program that used ps.push(...)’s result still gets the same number.
• grow() doubles cap, and for each typed column makes a bigger Float64Array, copies the old values in with set, and swaps it in. Chapter 105 explains why doubling makes push cheap on average.
• static of(...v) replaces an array literal. It takes every field of every record, flattened, and pushes them in groups of two.

Watching it grow

Step through the first seventeen pushes of for (let i = 0; i < N; i++) ps.push(i, 1):

push(v0, v1) {
  const n = this.length;
  if (n === this.cap) this.grow();
  this.x[n] = v0; this.vx[n] = v1;
  return (this.length = n + 1);
}
grow() {
  const cap = (this.cap *= 2); let t;
  t = new Float64Array(cap);
  t.set(this.x); this.x = t;
  t = new Float64Array(cap);
  t.set(this.vx); this.vx = t;
}

The check n === this.cap runs once per push. Most of the time it is false, and push is a few plain writes. The copying happens only on the 17th push, the 33rd, the 65th, and so on.

Typed columns and plain columns

A Float64Array stores raw 64-bit doubles, side by side, with no object per value^[1]. That is the whole point. But it only stores numbers. Anything else you write into it is converted:

const col = new Float64Array(4);
console.log(col); // zero-filled

col[0] = 2.5;
col[1] = -0;
col[2] = '7';   // converted
col[3] = 'abc'; // converted
console.log(col[0]);
console.log(Object.is(col[1], -0));
console.log(col[2], typeof col[2]);
console.log(col[3]);

// Writing past the end does nothing:
col[4] = 9;
console.log(col.length, col[4]);

// A plain array takes anything, and
// lengthens by itself:
const arr = [];
arr[0] = 'abc';
arr[3] = null;
console.log(arr.length, arr[0]);

So a typed column is only correct for a field that is provably always a number. Every other field gets a plain JavaScript array. Here is the constructor Viscosity emits for the corpus file mixed_columns.js, whose records are { id: 'e' + i, hp: 100, x: i, tag: … }:

constructor(cap = 16) {
  this.length = 0; this.cap = cap;
  this.hp = new Float64Array(cap);
  this.x = new Float64Array(cap);
  this.id = []; this.tag = [];
}

push writes all four columns. grow only touches hp and x: a plain array lengthens by itself when you write past its end, so it never needs copying.

Doubles also keep the awkward values exactly. literal_init.js stores { x: -0, y: NaN } and checks, after compiling, that Object.is(pts[2].x, -0) and Number.isNaN(pts[2].y) are still true. They are: a Float64Array holds any IEEE 754 double, -0 and NaN included.

Try it: this collection has a string field, a numeric field and a field that is sometimes null. Open the compiled code and find the columns.

Names that would clash

Columns are named after their fields, so ps.x is the x column. But the container already has members of its own. A record with a field called length or push would overwrite them. The emitter therefore renames any field that is a reserved name (length, push, grow, of, constructor, prototype, get, cap, data) or isn’t a plain identifier, to f plus its position plus _. For records { length: i, cap: 1, 'a-b': 2 }:

this.f0_ = new Float64Array(cap);
this.f1_ = new Float64Array(cap);
this.f2_ = new Float64Array(cap);

The program’s ps[i].length becomes ps.f0_[i], and nothing outside the generated code ever sees the new name. A new name could still collide with a real field: records { length: i, f0_: 2 } would put both in f0_. So a renamed column gets another _ until its name is free: length becomes f0__, and the real f0_ keeps its own column.

Your turn

class Ps {
  constructor(cap = 2) {
    this.length = 0;
    this.cap = cap;
    this.x = new Float64Array(cap);
    this.vx = new Float64Array(cap);
  }
  push(x, vx) {
    const n = this.length;
    this.x[n] = x;
    this.vx[n] = vx;
    this.length = n + 1;
  }
}

class Ps {
  constructor(cap = 2) {
    this.length = 0;
    this.cap = cap;
    this.x = new Float64Array(cap);
    this.vx = new Float64Array(cap);
  }
  static of(...v) {
    return new Ps();
  }
}

What you learned

• Column storage keeps one array per field; element i is index i of every column.
• The SoA container is a generated class: length, cap, one column per field, push, grow and of.
• push takes one value per field and returns the new length, like Array.prototype.push. When the columns are full, grow doubles them and copies with set.
• Provably numeric fields get Float64Array columns; every other field gets a plain array, which grows by itself.
• Fields whose names clash with the container’s own members are renamed f0_, f1_, … (with an extra _ if a real field already has that name), invisibly to the program.