106. Identity and materialization

Two names, one particle

Here is aliasing_identity.js from Viscosity’s test corpus:

const ps = [];
for (let i = 0; i < 100; i++)
  ps.push({ x: i });
const keep = [];
for (let i = 0; i < ps.length; i++)
  keep.push(ps[i]);
keep[0].x = 42;
console.log(ps[0].x, keep[0] === ps[0]);

It prints 42 true. keep[0] and ps[0] are two references to one object (chapter 4), so a write through one is seen through the other, and === says they are the same^[1]. Now imagine ps as columns. There is no object for keep to hold. What could the compiler put there?

Copies break aliasing

The easy answer is chapter 23’s materialization: build a fresh object from the columns every time the program asks for ps[i]. Run both versions:

// Original: real objects.
const ps = [];
for (let i = 0; i < 4; i++)
  ps.push({ x: i });
const k = [ps[0]];
k[0].x = 42;
console.log(ps[0].x, k[0] === ps[0]);

// SoA, materializing copies.
const s = { x: [0, 1, 2, 3] };
const get = (i) => ({ x: s.x[i] });
const k2 = [get(0)];
k2[0].x = 42;
console.log(s.x[0], k2[0] === get(0));

The copy is a snapshot. The write k2[0].x = 42 changes the snapshot, not the column, so the next read sees 0. And every call makes a new object, so === is false. The program can tell the layout changed, twice.

Handles

The fix for aliasing is to hand out something that refers to the element instead of copying it. Step through it:

const h1 = at(0);
keep.push(h1);
keep[0].x = 42;
console.log(ps[0].x);
const h2 = at(0);
console.log(h1 === h2);
console.log(Object.keys(h1));

class H {
  constructor(c, i) {
    this.c = c;
    this.i = i;
  }
  get x() { return this.c.x[this.i]; }
  set x(v) { this.c.x[this.i] = v; }
}

get x() and set x(v) are accessors: reading h.x calls the first, and assigning h.x = v calls the second. So every read and write goes to the column, and the value lives in one place.

Notice what the handle holds: the container c, not the column c.x. Chapter 105’s grow() replaces each column with a bigger one. A handle that had saved the old column would keep reading an array that nothing writes to any more.

Keeping identity

Two handles for element 0 are still two objects. To make === behave, the container must hand out the same handle every time, so it keeps a cache: one slot per index, filled the first time that index is asked for.

class H {
  constructor(c, i) {
    this.c = c;
    this.i = i;
  }
  get x() { return this.c.x[this.i]; }
  set x(v) { this.c.x[this.i] = v; }
}
const c = { x: [0, 1, 2, 3], hs: [] };
function at(i) {
  let h = c.hs[i];
  if (!h) h = c.hs[i] = new H(c, i);
  return h;
}
const k = [at(0)];
k[0].x = 42;
console.log(c.x[0], k[0] === at(0));
console.log(Object.keys(at(0)));
try {
  JSON.stringify(at(0));
} catch (e) {
  console.log(e.name);
}

The run also shows what is still wrong. Object.keys sees c and i, not x. JSON.stringify doesn’t print {"x":42}: here it throws, because the handle points at the container, which points back at its cache. Spreading ({ ...h }), console.log and the object’s prototype all differ too. A real handle mode would have to emulate each one, with a different handle class for every record shape.

What Viscosity actually does

Viscosity has no handle mode. When an element escapes, it keeps the array of objects and says why. Here is viscosity explain on the program above:

ps (line 1) {x} → kept as array of objects
  · unsafe: line 8: an element is compared
    or combined with "==="
  · unsafe: line 6: an element is used by
    push

(The real lines are longer; they are wrapped here.) Viscosity does use one handle, a very small one: when you write const p = ps[i] and only touch p.x, the compiled code says const p = i. The index is the handle. That is only safe because p never escapes and is never compared, which is exactly what the safety analysis proved.

Why refuse instead of emulating? Look at the cost of the snapshot route, the cheapest kind of object to rebuild:

In this book’s benchmark run, SoA was about 20 times slower than AoS at 100,000 elements, and about 33 times at a million. A handle cache would bring back one object per element handed out, plus an accessor call per field. Nobody has measured a handle mode in this repository, so we can’t quote its numbers, but it starts from the same kind of allocation.

The other suite is the exception that proves the rule:

Here the object didn’t escape consume, so V8 inlined it and replaced the object with its fields (scalar replacement, chapter 67). An object that doesn’t escape costs nothing. One that escapes costs a lot. So Viscosity lets only the first kind through, and turns the second kind into a message.

Try it. This is the corpus program escapes_log.js: printing a whole element makes it escape. Change the last line to console.log(ps[3].x, ps[3].y) and watch the verdict change:

Your turn

class H {
  constructor(c, i) {
    this.c = c;
    this.i = i;
  }
  get x() { return this.c.x[this.i]; }
  set x(v) { this.c.x[this.i] = v; }
}

function at(c, i) {
  // your code here
  return new H(c, i);
}

const c = { x: [5, 6, 7], hs: [] };
console.log(at(c, 0) === at(c, 0));

class H {
  constructor(c, i) {
    this.c = c;
    this.i = i;
  }
  get x() { return this.c.x[this.i]; }
  set x(v) { this.c.x[this.i] = v; }
}

function at(c, i) {
  // your code here
}

const c = {
  x: [1, 2, 3], hs: new Map(), made: 0,
};
at(c, 0); at(c, 0); at(c, 2);
console.log(c.made);

What you learned

• Materializing a fresh copy per access breaks both aliasing (writes hit the copy) and identity (=== is false).
• A handle holds the collection and an index, with accessors that use the columns. It keeps aliasing correct.
• Identity preservation needs a cache with one handle per element, which brings back an object per element.
• Handles still differ in keys, JSON, spreading and printing.
• Viscosity has no handle mode: it refuses collections whose elements escape, and explains why. Its only “handle” is a bare index, used when nothing escapes.