105. Growing collections

Push into a fixed box

Here is a program from Viscosity’s test corpus, growth.js. Nobody knows how many elements ps will hold until the while loop has run:

const ps = [];
let n = 0;
while (n < 5000) {
  ps.push({ a: n, b: n % 7 });
  n++;
}

Viscosity turns ps into a struct of arrays with two Float64Array columns. But a Float64Array made with new Float64Array(n) has a fixed length, and it starts out full of zeros^[1]. There is no push on it. So how does the compiled program keep pushing?

Capacity and length

The container from chapter 103 keeps two numbers. cap is how many slots each column has. length is how many of them hold real elements. Step through a column filling up:

push(v) {
  const n = this.length;
  if (n === this.cap) this.grow();
  this.a[n] = v;
  return (this.length = n + 1);
}
grow() {
  const cap = (this.cap *= 2);
  const t = new Float64Array(cap);
  t.set(this.a); this.a = t;
}

The real container

Here is what Viscosity really generates for growth.js, reformatted to fit the screen (the compiler writes each method on one line):

class __Vsc_ps {
  constructor(cap = 16) {
    this.length = 0;
    this.cap = cap;
    this.a = new Float64Array(cap);
    this.b = new Float64Array(cap);
  }
  push(v0, v1) {
    const n = this.length;
    if (n === this.cap) this.grow();
    this.a[n] = v0;
    this.b[n] = v1;
    return (this.length = n + 1);
  }
  grow() {
    const cap = (this.cap *= 2);
    let t;
    t = new Float64Array(cap);
    t.set(this.a); this.a = t;
    t = new Float64Array(cap);
    t.set(this.b); this.b = t;
  }
}

The push in the loop becomes ps.push(n, n % 7). grow() doubles cap, and gives each column a new Float64Array of that size. set copies every value of the old column into the start of the new one^[2]. The old column has no references left, so the garbage collector will reclaim it. And push returns the new length, just as Array.prototype.push does, in case the program uses it.

Not every column is typed. When a field may hold strings or objects, chapter 103’s container gives it a plain array column instead, and grow() leaves that column alone. Writing this.name[n] = v at index length simply appends to a plain array: the JavaScript engine grows it by itself.

Why doubling

Growing could add a fixed number of slots, say 16, each time. That sounds thriftier. Count the copies instead:

function copies(n, next) {
  let cap = 16, c = 0;
  for (let len = 0; len < n; len++) {
    if (len === cap) {
      c += len;
      cap = next(cap);
    }
  }
  return c;
}
const dbl = (c) => c * 2;
const add = (c) => c + 16;
for (const n of [1000, 10000, 100000])
  console.log(n, copies(n, dbl),
    copies(n, add));

With doubling, building 100,000 elements copies about 131,000 values in all. Adding 16 at a time copies more than 312 million. The reason is simple. When doubling, each grow copies 16 more values than all the earlier grows put together: 16, then 32, then 64. So the total is always less than the final capacity, which is less than twice the length. Adding 16 instead copies 16, 32, 48, 64 and so on, a sum that grows with the square of the length.

For growth.js itself, the counter below follows the container from capacity 16: 9 grows, 8,176 values copied per column, and a final capacity of 8,192 for 5,000 elements.

let cap = 16, len = 0;
let grows = 0, copies = 0;
for (let k = 0; k < 5000; k++) {
  if (len === cap) {
    copies += len; // t.set(old)
    cap *= 2;
    grows++;
  }
  len++;
}
console.log(grows, copies, cap);
console.log((copies / len).toFixed(2));

What it costs

The book’s construct suite times building a whole collection of 6-field particles from raw values:

Read it carefully. The harness knows n in advance, so its columns are created at the right size and never grow. What the chart shows is that filling columns avoids an allocation per element. Doubling adds fewer than two copies per value on top, which is small next to an allocation, but this run doesn’t time it separately.

Your turn

function makeCol() {
  return {
    len: 0, cap: 4, copies: 0,
    data: new Float64Array(4),
    push(v) {
      // your code here
    },
  };
}

const c = makeCol();
for (let i = 0; i < 5; i++) c.push(i);
console.log(c.len, c.cap, c.copies);

function copiesFor(n, next) {
  // your code here
  return 0;
}

const dbl = (c) => c * 2;
console.log(copiesFor(5000, dbl));

What you learned

• A collection has a capacity (slots allocated) and a length (slots used). Spare slots are real memory, full of zeros, so bounds checks must compare with length.
• Viscosity’s container grows by doubling cap and copying each typed column with set(). Plain array columns grow by themselves.
• Amortized growth: with doubling, n pushes copy fewer than 2n values in total, so a push is cheap on average. Growing by a constant is quadratic.
• The construct benchmark shows filling columns beats allocating objects; it doesn’t measure growth, because its sizes are known.