109. Profile-guided optimization

A question the code can’t answer

In chapter 101 the cost model got one rule that has nothing to do with safety: below 64 elements, a new layout isn’t worth it. That rule needs a number. For most programs the analysis can count, because the elements are pushed in a loop with a constant bound. Here it can’t:

const ps = [];
function spawn(x) {
  ps.push({ x, vx: 1 });
}
for (let i = 0; i < 20; i++) spawn(i);
for (let f = 0; f < 100; f++) {
  for (let i = 0; i < ps.length; i++) {
    ps[i].x += ps[i].vx;
  }
}
console.log(ps[0].x);

The estimate counts literal elements, and pushes in top-level loops with a constant trip count. This push sits inside spawn, so the count depends on how often spawn is called, and the analysis gives up. This is what viscosity explain says (long lines wrapped):

ps (line 1) {x, vx} → struct of arrays
  · loop at line 7 in <module>() touches
    2 of 2 fields (vx, x)
  · typed Float64Array columns for all 2
    fields
  · size unknown statically
  · 2 of 3 element accesses proven in
    bounds

“Size unknown”, so the threshold can’t apply, and Viscosity transforms 20 elements into columns. It is safe, but pointless. You can read this program and see the 20. A real program’s count comes from a file, a network or a user, and nobody can read it off the source.

Run it, count, compile

Viscosity answers the question by running the program. The command is viscosity profile, and the output goes back in with --profile:

$ viscosity profile spawn.js -o p.json
$ cat p.json
{
  "ps": {
    "maxLength": 20
  }
}
$ viscosity explain spawn.js \
    --profile p.json
ps (line 1) {x, vx} → kept as array of
  objects
  · about 20 elements (measured): below
    the 64-element threshold, where the
    benefit is too small

Both outputs are real, from runs for this chapter. Step through the whole loop:

Instrumentation

To count, viscosity profile builds a slightly different program. It finds the collections the same way the compiler does (chapter 96), and wraps the expression that creates each one. From cli/src/profile.ts, simplified:

function instrument(src, plugin) {
  const m = plugin.lower(src).module;
  const cs = analyze(m).collections;
  // Edit from the end: offsets stay valid.
  cs.sort((a, b) =>
    b.init.src.start - a.init.src.start);
  let out = src;
  for (const c of cs) {
    const { start, end } = c.init.src;
    out = out.slice(0, start) +
      `__vsc_track("${c.name}", ` +
      out.slice(start, end) + ')' +
      out.slice(end);
  }
  return PRELUDE + out;
}

So const ps = []; becomes const ps = __vsc_track("ps", []);. The prelude defines the tracker and an exit hook:

const __vsc_seen = [];
function __vsc_track(name, arr) {
  __vsc_seen.push([name, arr]);
  return arr;
}
process.on('exit', () => {
  const p = {};
  for (const [n, a] of __vsc_seen) {
    const old = p[n]?.maxLength ?? 0;
    p[n] = {
      maxLength: Math.max(old, a.length) };
  }
  writeFileSync(
    process.env.VSC_PROFILE_OUT,
    JSON.stringify(p, null, 2));
});

__vsc_track returns the same array it was given. Nothing is copied or wrapped, so every push, every === and every console.log behaves as before. A profile of a program that behaves differently would be a profile of the wrong program.

The profile run is the original program, run once in its own Node process with its output thrown away. Nothing is timed: it counts.

Try it in the browser. This is the same instrumentation, done by hand:

// The tracker from the prelude.
const seen = [];
function track(name, arr) {
  seen.push([name, arr]);
  return arr; // the same array
}
function report() {
  const p = {};
  for (const [n, a] of seen) {
    const old = p[n]
      ? p[n].maxLength : 0;
    const len = a.length;
    p[n] = {
      maxLength: Math.max(old, len),
    };
  }
  return p;
}

// The program, instrumented:
const ps = track('ps', []);
function spawn(x) {
  ps.push({ x, vx: 1 });
}
const waves = 20; // try 5000
for (let i = 0; i < waves; i++) {
  spawn(i);
}
for (let i = 0; i < ps.length; i++) {
  ps[i].x += ps[i].vx;
}
console.log(ps[0].x);

// What the exit hook would write:
const prof = report();
console.log(JSON.stringify(prof));
const n = prof.ps.maxLength;
console.log(n < 64
  ? 'kept as objects (measured)'
  : 'struct of arrays (measured)');

Where the number goes

The profile reaches exactly one line of the planner. From core/src/plan.ts:

const measured =
  opts.profile?.[c.name]?.maxLength;
const size = measured ?? c.sizeEstimate;
if (size !== null && size < opts.minSize) {
  // keep: "about N elements (measured)"
}

A measurement, when there is one, beats the estimate. And the report says which it used: “(measured)” on a kept collection, “(measured by profiling)” on a transformed one. Profile the same program with 5000 calls to spawn and the verdict flips:

ps (line 1) {x, vx} → struct of arrays
  · …
  · about 5000 elements (measured by
    profiling)

Look at where that line sits. By the time the planner reads the profile, the collection has already passed every safety check, has a numeric field, and has a loop over its fields. A profile can’t rescue an unsafe collection, because none of those checks look at it.

Why a wrong profile is only slow

Here is the property that makes Viscosity’s PGO calm. Both layouts were already proven to behave identically (chapter 99). The profile only chooses between two correct programs. So the worst a stale or unrepresentative profile can do is pick the slower of two right answers.

There are rough edges, visible in the code. Profiles are keyed by the array’s variable name, so two collections both called ps in different functions share one entry. And lengths are read once, at exit. For a collection Viscosity can transform that is the same as the maximum, because such a collection only ever grows: only .push and .length are allowed. The profile type also has room for per-field read counts, but nothing records or reads them yet.

Your turn

function makeTracker() {
  const seen = [];
  return {
    track(name, arr) {
      // your code here
      return arr;
    },
    profile() {
      return {};
    },
  };
}

function sizeLine(est, measured, min) {
  return { keep: false, text: '' };
}

What you learned

• Profile-guided optimization compiles with measurements from a real run. Viscosity measures the one thing it can’t always compute: how big each collection gets.
• Instrumentation wraps each collection’s creation in __vsc_track, which returns the same array, so the program behaves exactly as before. An exit hook writes the lengths to a JSON profile.
• In the planner, measured ?? estimate: a measurement wins, and the report says “(measured)”.
• The profile is read only after every safety check passes, so a bad profile can cost speed, never correctness. Profile with typical input.