Interpreter 2: Rise of the Stack Machine
December 20, 2010
Posted by on
I rewrote everything.
Original design (week before last):
- syntax trees and statement graphs on heap
- interpreter recursion by pointer chasing
- values in reference counted variables
The rewrite (last week):
- const parse trees and statements converted directly to stack bytecode
- interpreter recursion by stack iteration
- no values or reference counting, DAG as bytecode stack is full computation
The reason I moved to a bytecode stack machine is for the JIT. Pointer chasing over a DAG is fine so long as it is strictly interpreted. This becomes impractical for a JIT as the graph must be transformed. The JIT will:
- find subgraphs it knows how to optimize
- synthesize new kernel functions for these subgraphs
- replace subgraphs with new kernels
Another concern I had is all of the locking in the standard library allocators and loss of memory locality when building everything on the heap. It’s just not efficient and could be costly inside inner loops.
There’s one feature of the original design that must be carried over to the rewrite. Variables need mutable state and reference counting again. Once a variable has a value, the graph of computations required to calculate it can be discarded. Without this, the bytecode stack often becomes huge as the full computation is an enormous graph. There’s nothing surprising about this. Tail recursion and memoization are often necessary for recursive algorithms. Otherwise, combinatorial explosions take hold.
One major advantage of a bytecode based virtual machine is that it decouples the front-end. The original design had no clear separation boundary between the front-end and middle/back-end. The zoo of types threatened to turn the design into a big ball of mud. With bytecode, there is clear separation between layers. This also will make it much easier to implement additional front-ends, especially in other languages.
I’m a little disappointed that I don’t have a working JIT yet, even as a primitive proof-of-concept. But the rewrite was necessary to make the JIT possible. And the design is much better now.