60. Making the VM fast

The fastest fix was a deletion

Chapter 58 ended with a safety net. When the heap frees an object, it can poison it, so that any later use throws:

function poison(o: Obj) {
  const type = o.type;
  for (const k of Object.keys(o)) {
    delete (o as any)[k];
  }
  Object.defineProperty(o, 'type', {
    get() { throw new Error(/* ... */); },
  });
}

At first the heap poisoned every freed object, always. Then the VM was profiled. On allocation-heavy programs, poisoning was more than half the running time. The commit that fixed it gives the reason: deleting every property pushed each dead object into V8’s dictionary mode. V8 keeps such “slow properties” for objects whose properties are added and deleted a lot, and they are slower than fast properties (chapter 22)^[1]. A program that frees millions of objects paid that millions of times.

The fix was one flag. Poisoning now runs only in stress and debug mode, where the tests use it, and the normal VM skips it. That commit recorded the instantiation benchmark, which makes fifteen million instances, going from 19.4 seconds to 3.6:

The same commit moved the hash table to chapter 23’s struct-of-arrays layout: parallel keys and values arrays instead of an array of {key, value} entry objects, saving an allocation per slot. The commit doesn’t time that change on its own, so this book won’t claim a number for it.

Two lessons. Nobody would have guessed that a debugging aid was the bottleneck; a profile showed it. And even after the fix, this benchmark is slower on the VM than on the tree-walker, in this book’s one recorded run. Why is an open question. Node’s built-in profiler (node --cpu-prof) is the place to start, not a hunch.

The rest of this chapter is ideas the companion does not implement. They are what real VMs do next, and each is a good project.

NaN-boxing

Today a Drip Value is null | boolean | number | Obj, and V8 picks a representation for each (chapter 22). A VM in C needs its own. A tagged value (chapter 49) as a C struct, a type tag plus an 8-byte payload, usually takes 16 bytes once padded. NaN-boxing fits every value into one 8-byte double.

In IEEE 754, a double whose exponent bits are all ones and whose fraction is not zero is a NaN. That leaves a huge number of NaN bit patterns, and arithmetic only ever produces one or two of them. So pick a NaN pattern no arithmetic makes: here, the quiet-NaN bits plus one extra “box” bit. Any double with those bits set is not a number but a boxed value, and its other bits carry a tag and a payload:

In JavaScript you can try this with two views over one buffer (chapter 16): a Float64Array to read and write doubles, and a Uint32Array over the same bytes to reach their bits. On a little-endian machine, which is almost every machine today, the high word of slot i is u32[2 * i + 1]:

const f64 = new Float64Array(4);
const u32 = new Uint32Array(f64.buffer);
// quiet NaN + the "box" bit
const BOX = 0x7ffc0000;
const NIL = 1, TRUE = 3, OBJ = 4;

function box(i, tag, payload) {
  u32[2 * i] = payload; // low word
  u32[2 * i + 1] = BOX | tag; // high
}
function isNum(i) {
  return (u32[2 * i + 1] & BOX) !== BOX;
}
function show(i) {
  if (isNum(i)) return f64[i];
  const tag = u32[2 * i + 1] & 0xffff;
  const p = u32[2 * i];
  if (tag === NIL) return 'nil';
  if (tag === TRUE) return 'true';
  return 'object #' + p;
}

f64[0] = 1.5;
box(1, NIL, 0);
box(2, OBJ, 7);
f64[3] = NaN;
for (let i = 0; i < 4; i++) {
  const hi = u32[2 * i + 1];
  console.log(hi.toString(16), show(i));
}
// a boxed value *is* a NaN:
console.log(Number.isNaN(f64[2]));

Two catches. First, a real NaN must never look boxed, so a VM stores every NaN in one canonical form. That matters in JavaScript too: when a NaN is written into a typed array, the spec lets the engine choose its bit pattern^[2], so a NaN carrying “boxed” bits can survive the trip and be misread. Second, JavaScript can’t put a pointer in a double, so the payload would be an index into an array of objects. In C, the spare bits can hold a real pointer.

Generational collection

Chapter 58’s collector marks every live object on every collection. If a program keeps a large data structure alive, each collection traces all of it again, only to free a few short-lived strings.

Most collectors exploit an observation called the generational hypothesis: most objects die young^[4]. So split the heap into a young generation and an old one. New objects start young. A minor collection looks only at the young generation, which is small and mostly garbage, so it is cheap. Objects that survive a few minor collections are promoted to old, which is collected rarely.

The catch is pointers from old objects to young ones. A minor collection doesn’t trace the old generation, so it would miss a young object kept alive only by an old one. The fix is a write barrier: a check on every store of a reference into an object, recording old objects that now point at young ones. That record joins the roots. In the companion, every SET_PROPERTY, SET_UPVALUE on a closed upvalue and OP_METHOD would need one. A sketch:

// a sketch: not in the companion
function barrier(owner: Obj, v: Value) {
  if (owner.old && isObj(v) && !v.old) {
    remembered.add(owner); // extra root
  }
}

Superinstructions

Every instruction pays for a trip round the dispatch loop: fetch the opcode, branch to its case, come back. Fewer, bigger instructions mean fewer trips. To see which instructions travel together, I added a pair counter to a copy of the VM’s run() loop:

// per instruction, in a copy of run():
const key = prev + ' ' + instruction;
pairs.set(key, (pairs.get(key) ?? 0) + 1);
prev = instruction;

Running fib(20) on that copy executes 262,695 instructions (the same count the real VM’s instructionsExecuted reports). The most common pairs:

GET_LOCAL     -> CONSTANT        43781
CONSTANT      -> LESS            21891
LESS          -> JUMP_IF_FALSE   21891
JUMP_IF_FALSE -> POP             21891
CONSTANT      -> SUBTRACT        21890

n < 2 and n - 2 are each GET_LOCAL, CONSTANT, then an operator. One instruction could do all three, with the slot and the constant as operands:

// a sketch: not in the companion
case OP.SUB_LOCAL_CONST: {
  const a = stack[frame.slots + readByte()];
  const b = readConstant();
  // (check both are numbers)
  push(a - b);
  break;
}

It isn’t free. The compiler must spot the pattern. A jump must never land in the middle of a fused group. And every new opcode is more code in the dispatch loop. CPython does this for real: its compiler fuses two adjacent LOAD_FAST instructions into LOAD_FAST_LOAD_FAST, only within a basic block (a straight run of code that jumps enter only at the top), only when both operands fit in 4 bits, and turns the second instruction into a NOP^[5].

Your turn

const f64 = new Float64Array(8);
const u32 = new Uint32Array(f64.buffer);
const BOX = 0x7ffc0000;
const NIL = 1, FALSE = 2, TRUE = 3;

function setValue(i, v) {
  f64[i] = v;
}

function getValue(i) {
  return f64[i];
}

function fuse(code, targets) {
  const out = code.slice();
  // fuse GET_LOCAL, GET_LOCAL pairs
  return out;
}

What you learned

• The VM’s biggest measured win was making GC poisoning debug-only: deleting properties pushed dead objects into V8’s dictionary mode. A profile found it, and the result still needs explaining.
• NaN-boxing: every value is one double; non-numbers hide in NaN bit patterns arithmetic never makes. NaNs must be canonical.
• Generational GC: most objects die young, so collect the young generation often, promote survivors, and use a write barrier to remember old-to-young pointers.
• Superinstructions: count which instructions run together, fuse the common sequences, and never let a jump land inside one.

That’s Part IV: a compiler, a VM, and a garbage collector, all yours.