118. The research frontier

Where the map ends

Take a perfectly ordinary program: make 1,000 particles, sort them by x, then update them in a loop. Ask Viscosity about it:

ps (line 1) {x, y} → kept as array of
  objects
  · unsafe: line 4: uses .sort on the
    array (only .length and .push are
    supported)
  · unsafe: the array is passed to a
    method call at line 4

No speed-up. Swap two elements by hand instead of sorting and it refuses again. Use a class instead of object literals, export the array, or give half the records an extra field, and you get the same answer. Viscosity is careful, and careful means it says no a lot.

Every one of those refusals is a place where the map ends. Some are edges because nobody has walked that far yet. Others are edges because nobody knows the way.

Six edges

Here are six short programs at the edges, with what Viscosity really says about each (all output from the CLI, wrapped):

Two of them it transforms anyway, but not fully. The nested record gets a column of objects for pos, so reading pos.x still follows a pointer. The unknown size gets no estimate at all, and the transform is a bet on n.

Gaps and open problems

The class case is a gap. Recognizing that new P(i) builds an object with fields x and vx, in that order, is known technique. Someone has to write the lowering, the shape inference and the tests. Destructuring (for (const { x } of ps)) is the same kind of thing: today it is “code Viscosity doesn’t model”.

The others need more than work. Sorting needs every column permuted in step, plus a comparator that receives objects that no longer exist. Varying shapes need either many layouts or a way to say “this field is sometimes missing” in a column. Exported arrays need an analysis of code in other files, some of which may never be shown to the compiler.

Try one edge yourself. This program is refused because half its records have a tag. Give every record a tag (an empty string will do) and watch the verdict change:

Problem one: proof or speculation

Viscosity runs before the program, so it must prove that nobody can tell the difference. A JIT runs during the program, so it can guess and recover. That is exactly the split in the research this book started from. Makor and colleagues turned arrays of objects into columns at run time inside GraalJS, paying for the conversion and earning it back on later accesses^[1]. The follow-up duplicated loops so each copy could assume one layout, and transformed nested objects into columns of their own^[2].

So a run-time system can try layouts that Viscosity can’t prove safe, while Viscosity can explain its choices before you ship and needs no special engine. Getting both, an ahead-of-time compiler with a cheap escape hatch for the cases it can’t prove, is the open question. Emitting both versions of a loop and choosing at run time is the obvious idea, and it costs code size and a check on every entry.

Problem two: knowing when it pays

The cost model is the least proven part of Viscosity. It skips collections under 64 elements and otherwise trusts that a loop over a few fields will win. This book’s own measurements show how rough that is. In the microbenchmarks, gains shrank to about 1.3–2.3× at 1,000 elements, and AoSoA was often slower than plain objects there (FINDINGS.md, section 3). In this book’s end-to-end benchmark run (chapter 111), nbody gained 1.09× while ledger gained 5.11×. In CPython the same layout lost on time and won on memory (section 6). And SoA loses badly whenever whole objects must be rebuilt^[5]. Viscosity has no model that predicts all of that for any program on any machine, and this book knows of none.

Problem three: who decides

Some languages hand the choice to you. In Odin, #soa[N]Vector3 stores an array as columns while you keep writing v[0].x^[4]. ISPC’s soa<N> types do the same for blocked layouts^[3]. Viscosity’s @viscosity soa annotation (chapter 102) sits in between: you ask, and it still checks safety. Whether an automatic tool can match an expert’s choice, and how it should explain itself when it disagrees with one, is open.

Measuring the frontier

How do you choose which edge to work on? The same way Part VII chose its optimizations: measure. Run viscosity explain over a corpus of real programs and count the reasons. The refusal that blocks the most programs is the one worth an idea. That is what the exercise builds.

Your turn

function tally(report) {
  const t = { soa: 0, aosoa: 0,
    kept: 0, unsafe: 0 };
  for (const l of report.split('\n')) {
    if (l.includes('struct')) t.soa++;
  }
  return t;
}

function sumX(ps) {
  let s = 0;
  for (const p of ps) s += p.x;
  return s;
}

What you learned

• Viscosity’s refusals mark the edge of what it can prove. Its explain report names each one.
• An engineering gap (classes, destructuring) needs work. An open problem (reordering, varying shapes, whole programs, nested records, unknown sizes) needs an idea.
• Proof or speculation: run-time systems can guess and recover; ahead-of-time ones must prove. Combining the two is open.
• The cost model is a heuristic, and the book’s own benchmarks show how far “when does it pay” is from solved.
• To choose a problem, measure which refusals are common.