70. GraalJS and Truffle

The question your tree-walker keeps asking

Your Part III interpreter evaluates a + b by asking the same questions every single time: what kind of node is this? Are both values numbers? Strings? In a loop that runs a million times, the answers never change, and you pay for them a million times. That is the interpreter overhead you measured in chapter 44.

V8’s answer is separate machinery: bytecode for Ignition, then compilers that rewrite hot code using what the interpreter observed^[9]. Truffle, from Oracle and the Johannes Kepler University Linz, takes another road. You write an interpreter for “self-modifying Abstract Syntax Trees”, and the Graal compiler derives fast machine code from that interpreter itself^[1]. GraalJS, “a JavaScript engine implemented in Java on top of GraalVM”, is built this way^[5].

Two ideas make it work: nodes that specialize themselves, and partial evaluation.

Nodes that rewrite themselves

A + node starts with no idea what it will see. After the first few executions it narrows itself to the case it saw, and it widens again when something else turns up:

This is GraalJS’s real +, trimmed. Each @Specialization is one case. The integer case uses Math.addExact, which throws on overflow:

// JSAddNormalNode.java (GraalJS)
@Specialization(rewriteOn =
    ArithmeticException.class)
static int doInt(int a, int b) {
  return Math.addExact(a, b);
}
// JSAddNode.java (GraalJS)
@Specialization
static double doDouble(double a,
    double b) {
  return a + b;
}

rewriteOn means: if this exception is thrown even once, this node never uses that case again, and the next one runs instead^[4]. Further down, a generic case that first converts its operands replaces all the specific ones^[5]. At the lowest level, any node can swap itself for another in the tree with replace, which also invalidates compiled code that relied on the old node^[3].

Partial evaluation

Truffle’s documentation starts with exactly this kind of example^[2], here in JavaScript:

function round(v, up) {
  return up ? Math.ceil(v)
            : Math.floor(v);
}
// specialized for up = true:
function roundUp(v) {
  return Math.ceil(v);
}

Now apply the same trick to an interpreter. Its two inputs are the program and the program’s data. The program doesn’t change while it runs, so fix it and simplify:

function interpret(prog, args) {
  return prog.execute(args);
}
class Add {
  execute(args) {
    return this.l.execute(args) +
      this.r.execute(args);
  }
}
class Arg {
  execute(args) {
    return args[this.i];
  }
}

You can do a version of this by hand in JavaScript. Instead of a switch that runs on every evaluation, walk the tree once and build closures. The kind of each node is decided while building, not while running:

// a tiny AST: (args[0] + 2) * args[1]
const t = { op: '*',
  l: { op: '+',
    l: { op: 'arg', i: 0 },
    r: { op: 'num', v: 2 } },
  r: { op: 'arg', i: 1 } };

// the interpreter: decides every time
function run(n, args) {
  switch (n.op) {
    case 'num': return n.v;
    case 'arg': return args[n.i];
    case '+': return run(n.l, args) +
      run(n.r, args);
    case '*': return run(n.l, args) *
      run(n.r, args);
  }
}

// specialize: decide once, return code
function spec(n) {
  switch (n.op) {
    case 'num': {
      const v = n.v;
      return () => v;
    }
    case 'arg': {
      const i = n.i;
      return (args) => args[i];
    }
    case '+': {
      const l = spec(n.l);
      const r = spec(n.r);
      return (a) => l(a) + r(a);
    }
    case '*': {
      const l = spec(n.l);
      const r = spec(n.r);
      return (a) => l(a) * r(a);
    }
  }
}

const f = spec(t); // the tree is gone
console.log(run(t, [1, 9]), f([1, 9]));
console.log(run(t, [5, 3]), f([5, 3]));

How does Truffle know what may be treated as constant? It starts from the root node of the code being compiled and static final fields, then follows stable fields: final fields and declared @Child nodes. Fields marked @CompilationFinal can still change, so a node can record what it has seen, but once compilation starts they are folded like constants. Truffle counts calls and loop iterations, and compiles a root node (roughly, a function) once it is hot. If a recorded fact later turns out wrong, the node calls transferToInterpreterAndInvalidate: the compiled code is thrown away and execution continues in the interpreter, which re-specializes and may be compiled again^[2].

Your turn

const Lit = (v) =>
  ({ execute: () => v });
const Var = (k) =>
  ({ execute: (env) => env[k] });
const isInt = (x) => (x | 0) === x;
const isNum = (x) =>
  typeof x === 'number';

class AddNode {
  constructor(l, r) {
    this.l = l;
    this.r = r;
    this.state = 'uninit';
  }
  execute(env) {
    const a = this.l.execute(env);
    const b = this.r.execute(env);
    return a + b;
  }
}

function pe(n) {
  return '0';
}

What you learned

• A self-optimizing AST node records the types it sees, rewrites itself into a specialized version, and generalizes, one way only, when a guard fails. GraalJS’s + has int, double, string and generic cases.
• Partial evaluation fixes the known inputs and simplifies. Applied to an interpreter and one program, it inlines and folds the interpreter away, leaving a residual program: the first Futamura projection.
• Truffle treats the root node, final fields, @Child nodes and @CompilationFinal fields as constants, and invalidates compiled code when one of them must change.
• The engine’s semantics live in one place, the interpreter.