The bytecode virtual machine

Why bytecode

Walking a syntax tree repeatedly is slow, and the engine re-evaluates constantly. Compiling to a flat instruction sequence once and executing it many times is substantially faster, and it makes execution easy to bound.

1. 1Tree walkingRe-descend on every evaluation.
2. 2Compile onceThe parse emits bytecode directly.
3. 3Run many timesA loop over a byte array.
4. 4And it can be boundedThe reason that matters most.

1. Keystrokethe document is evaluated again
2. Walk the treea virtual call and a branch at every node
3. Walk it againnext keystroke, same work

The structure is convenient to build and expensive to run. Every evaluation pays the cost of navigating the shape as well as the cost of doing the arithmetic.

The trade

BackPauseNext

Shape

The program is a byte array of opcodes and operands, with separate pools for numeric and string constants. Operands are single bytes, which caps a pool at 256 entries and is checked at compile time.

flowchart LR
  subgraph program["Program"]
    direction TB
    code["<b>Code</b><br/>PUSH_NUM 0 · PUSH_NUM 1 · ADD"]
    nums["<b>Number pool</b><br/>[0] 25 · [1] 80"]
    strs["<b>String pool</b><br/>[0] USD"]
  end

  code -->|"operand 0"| nums
  code -->|"operand 1"| nums
  program --> stack["<b>Stack</b><br/>values, not raw numbers"]

A compiled program. Operands index into the pools, never into the code.

Dispatch

A switch over the opcode. The most frequent arithmetic paths have an inlined fast path for the case where both operands are plain numbers, which avoids a function call and an allocation in the common case.

Safety

Every instruction increments a counter and checks the stack depth. Both limits are configurable and both produce a named error. This matters because the input is untrusted and arrives one keystroke at a time.

1. 1FetchRead the next opcode.
2. 2Check the budgetBefore any work happens.
3. 3Check the depthSame idea, other resource.
4. 4DispatchA switch, with a fast path.

1. Fetch
2. Budget
3. Depth
4. Switch
5. Advance

The program counter indexes into a byte array. There is no node to visit and no pointer to follow.

One instruction

BackPauseNext

Values on the stack

The stack holds values, not raw numbers, so a unit, an error or a pending state survives an operation instead of being flattened into a number.

1. 1PushPUSH_NUMBER 0
2. 2Attach a unitUOM_CONVERT
3. 3Two of themThe second operand, built the same way.
4. 4OperateADD

PUSH_NUMBER 0

1. 5Number

A constant from the number pool. So far this looks exactly like a stack of numbers, which is where most stack machines stop.

The stack

BackPauseNext