there are so many cores

Just another WordPress.com site

Interpreter 2: Rise of the Stack Machine

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:

  1. find subgraphs it knows how to optimize
  2. synthesize new kernel functions for these subgraphs
  3. 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: