45. Why bytecode?

Getting around costs more than the work

At the end of Part III you counted what the tree-walker does for n - 2: three recursive calls, three switches on the node kind, two Map lookups and two type checks, all to do one subtraction. The subtraction was the cheap part. Getting to it was expensive.

None of that bookkeeping changes from one run to the next. The node for n - 2 is a subtraction every time fib is called. So why work it out again a million times? Work it out once, write the answer down in a form that is quick to follow, and then just follow it.

Flatten the tree

A tree can be turned into a recipe by visiting each node’s children before the node itself, and writing down one step per node:

The steps come out in exactly the order the work has to happen: every operand is ready before the operator that needs it. Each step is tiny, and the list is a plain array, so following it means moving to the next index, not chasing a pointer to another node.

Opcodes: instructions as numbers

To store a step as a byte, give each kind of step a number. Drip’s VM has a table of them in companion/ts/src/vm/chunk.ts:

// chunk.ts (excerpt)
export const OP = {
  CONSTANT: 0, NIL: 1, TRUE: 2, FALSE: 3,
  POP: 4,
  // …
  ADD: 18, SUBTRACT: 19, MULTIPLY: 20,
  DIVIDE: 21, NOT: 22, NEGATE: 23,
  PRINT: 24,
  // …
  RETURN: 33,
} as const;

There are 37 of them in the finished VM, so one byte (0 to 255) has room to spare. Some instructions need extra information. “Push a constant” must say which constant, so the byte after it is an operand: 0, 2 means “constant number 2”. ADD needs nothing more, because it always works on the two newest values.

A machine made of software

Something has to read those bytes and do what they say. It is a loop: read an opcode, do that instruction, move on, repeat. Here is a whole one, for three opcodes, with each value stored straight after its PUSH to keep it short:

const PUSH = 0, ADD = 1, MUL = 2;
// 1 + 2 * 3, flattened:
const code = [
  PUSH, 1, PUSH, 2, PUSH, 3, MUL, ADD,
];

const st = [];
let ip = 0;
while (ip < code.length) {
  const op = code[ip++];
  if (op === PUSH) {
    st.push(code[ip++]);
  } else {
    const b = st.pop();
    const a = st.pop();
    st.push(op === ADD ? a + b : a * b);
  }
}
console.log(st.pop()); // 7

Notice what is missing: no recursion, no kind field, no lookups. The loop keeps its own small stack of values, st, and an index, ip, saying where it is in the code. A real CPU works the same way on machine code, which is why a loop like this is called a virtual machine: it’s a pretend processor, built out of software.

The same Drip programs run unchanged on the VM. This one uses the bytecode VM you’ll build in the rest of Part IV:

fn fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

print fib(20);
print "same Drip, new engine";

Did it pay off?

The companion code already contains the finished VM, so you can see where this road leads before you walk it. These are the same benchmark runs as chapter 44, this time in seconds rather than as a ratio:

The wins are real. The programs the tree-walker found hardest, full of calls, method lookups and field reads, are where the VM saved the most time. That’s where the tree-walker’s overhead piled up.

But read the rest honestly:

• zoo_batch isn’t a race. It loops until ten seconds of clock time have passed, then reports how much work it finished, so both engines take about ten seconds by design.
• string_equality has no VM time at all. The compiler gave up: this VM’s instructions only have room for a one-byte constant number, so a chunk holds at most 256 constants. The script only has eight variables, but the compiler adds a variable’s name as a new constant every time the name appears, and this script names them hundreds of times. Chapter 46 shows where that limit lives.
• instantiation and equality got slower. One run on a shared machine can’t say why. There are suspects, though: every VM object is also tracked by the VM’s own heap and garbage collector, running on top of V8’s; and the VM’s hash tables are hand-written TypeScript where the tree-walker borrows V8’s built-in Map. Later chapters test those suspects.

Your turn

const OP = { CONST: 0, ADD: 1, MUL: 2 };

function flatten(node, out = []) {
  if (node.kind === 'num') {
    out.push(OP.CONST, node.value);
    return out;
  }
  // children first, then the operator
  return out;
}

function countInstrs(code) {
  return code.length;
}

What you learned

• Bytecode is a program as a flat array of small instructions, produced once by a compiler, in the order the work must happen.
• Visiting children before parents turns an expression tree into that order.
• An opcode is the number naming an instruction; operands are the extra bytes some instructions need.
• A virtual machine is a loop that fetches, decodes and performs instructions: a pretend CPU for your language.
• The VM beat the tree-walker on most programs, lost on two, and couldn’t compile one. A better design is not faster at everything.

Next: the container bytecode lives in, and a tool to read it.