71. Columnar arrays at run time: the research

Where the idea came from

Back in chapter 23 you measured struct-of-arrays beating an array of objects whenever a loop touches a few fields of many elements. Doing that rewrite by hand is tedious and easy to get wrong. So why doesn’t the engine just do it for you?

Lukas Makor, Sebastian Kloibhofer and colleagues, whose papers appear in the GraalVM team’s publication list, asked exactly that, and built it into GraalJS, the Truffle-based engine from chapter 70^[1][3]. Their work is the closest prior work to Viscosity, and this chapter is a reading of it.

Columnar storage

Columnar is the database word for the layout you know as SoA. The research describes it as a layout used in analytical applications, because it speeds up read-heavy work^[1]. A loop over particles that reads x and vx of every element is exactly that kind of work.

Columns while the program runs

Makor and colleagues transform arrays of JavaScript objects into columnar arrays automatically, at run time, inside the GraalJS engine. The transformation has a cost, which they amortize over the later accesses^[1]. Running inside a speculating JIT gives them two things a compiler reading source doesn’t have: the real sizes and values of the arrays, and a way to recover from a wrong guess, deoptimization (chapters 66 and 70).

The follow-up paper starts from a weakness. By its abstract’s account, the first approach had performance issues on smaller workloads and on more complex, nested data^[2]. Its answer has two parts. First, control-flow duplication in the Graal compiler: loops that may touch a columnar array are duplicated, and a check decides which copy runs:

// the shape of the idea, not their code
if (isColumnar(ps)) {
  // fast copy: column accesses only
} else {
  // the original loop, which must cope
  // with either kind of storage
}

Second, a multi-level transformation for arrays of objects that contain objects, demonstrated with JavaScript Date objects, whose values become a column of their own. Their abstract reports TPC-H data-analytics queries running up to 10× faster for particular queries, with the multi-level transformation adding around 2× more^[2].

The same job, somewhere else

Viscosity asks the research’s question in a different place: in a compiler that reads your source before anything runs. Step through the two side by side:

The differences follow from where each one stands:

• Safety. The engine can guess and deoptimize. Viscosity can’t, so every use of the array must be one it can prove it rewrites correctly. If not, it bails out and the array stays as objects.
• Cost. The run-time version pays for converting during the run. Viscosity’s output allocates columns from the first push.
• Information. The engine knows the real sizes. Viscosity has to estimate them, leaves small arrays alone (64 elements by default), or uses a profile you record.
• Reach. The run-time version needs a modified engine. Viscosity’s output is plain JavaScript that runs anywhere.

Try it. This is the real compiler. Then delete the line that adds .tag to one element, and watch the decision change:

With .tag there, explain keeps ps as an array of objects and says why: line 5 “adds a new property .tag to an element”. An engine would see that write happen and handle it at run time. Viscosity sees it in the source and doesn’t transform at all.

Here is what the ahead-of-time version achieved on this book’s five end-to-end programs, in one recorded run:

Notice the same weakness the follow-up paper started from. In this book’s microbenchmarks, gains shrink for small collections (FINDINGS.md, section 3), and Zap’s TypeScript experiments found SoA losing when whole objects must be rebuilt^[5]. Moving the decision earlier doesn’t make that go away; it only changes who has to decide, and with what information.

Your turn

const HOT = 3;

class HotArray {
  constructor(objs) {
    this.rows = objs;
    this.cols = null;
    this.n = objs.length;
    this.uses = 0;
  }
  get mode() {
    return this.cols
      ? 'columns' : 'rows';
  }
  // rows -> one Float64Array per field,
  // only if every row has the same
  // numeric fields
  columnarize() {
    const rs = this.rows;
    const ks = Object.keys(rs[0]);
    const m = ks.length, n = rs.length;
    const ok = rs.every((r) =>
      Object.keys(r).length === m &&
      ks.every((k) =>
        typeof r[k] === 'number'));
    if (!ok) return;
    this.cols = {};
    for (const k of ks) {
      const c = new Float64Array(n);
      for (let i = 0; i < n; i++) {
        c[i] = rs[i][k];
      }
      this.cols[k] = c;
    }
    this.rows = null;
  }
  // columns -> objects again
  rowify() {
    const ks = Object.keys(this.cols);
    this.rows = [];
    for (let i = 0; i < this.n; i++) {
      const r = {};
      for (const k of ks) {
        r[k] = this.cols[k][i];
      }
      this.rows.push(r);
    }
    this.cols = null;
  }
  get(i, k) {
    return this.cols
      ? this.cols[k][i]
      : this.rows[i][k];
  }
  sum(k) {
    return 0;
  }
  set(i, k, v) {
    this.rows[i][k] = v;
  }
}

function scale(a, k, f) {
  for (let i = 0; i < a.n; i++) {
    a.rows[i][k] *= f;
  }
}

What you learned

• Columnar storage is struct-of-arrays by its database name: one contiguous column per field.
• Run-time transformation (Makor et al.) converts arrays of objects into columns inside GraalJS while the program runs, amortizing the cost; the follow-up adds control-flow duplication and multi-level columns (for Date), and reports large speed-ups on particular TPC-H queries.
• Viscosity does it ahead of time: safety by proof, a bail-out that leaves the array untouched, no guards, no deoptimization.
• Both pay off on large arrays and few fields, and struggle with small ones and whole-object use.