Tuesday, June 3rd, 2008
What is SquirrelFish
SquirrelFish is a register-based, direct-threaded, high-level bytecode engine, with a sliding register window calling convention. It lazily generates bytecodes from a syntax tree, using a simple one-pass compiler with built-in copy propagation.
SquirrelFish owes a lot of its design to some of the latest research in the field of efficient virtual machines, including research done by Professor M. Anton Ertl, et al, Professor David Gregg, et al, and the developers of the Lua programming language.
The post then goes into detail on why it is so much faster:
SquirrelFishâ€™s bytecode engine elegantly eliminates almost all of the overhead of a tree-walking interpreter. First, a bytecode stream exactly describes the operations needed to execute a program. Compiling to bytecode implicitly strips away irrelevant grammatical structure. Second, a bytecode dispatch is a single direct memory read, followed by a single indirect branch. Therefore, executing a bytecode instruction is much faster than visiting a syntax tree node. Third, with the syntax tree gone, the interpreter no longer needs to propagate execution state between syntax tree nodes.
And finishes by promising that this is just the beginning, and that we are going to see even faster:
In a typical compiler, conversion to bytecode is just a means to an end, not an end in itself. The purpose of the conversion is to â€œlowerâ€ an abstract tree of grammatical constructs to a concrete vector of execution primitives, the latter form being more amenable to well-known optimization techniques.
Therefore, though weâ€™re very happy with SquirrelFishâ€™s current performance, we also believe that itâ€™s just the beginning. Some of the compile-time optimizations weâ€™re looking at, now that we have a bytecode representation, include:
- constant folding
- more aggressive copy propagation
- type inferenceâ€”both exact and speculative
- specialization based on expression contextâ€”especially void and boolean context
- peephole optimization
- escape analysis
Weâ€™re also looking at further optimizing the virtual machine, including:
- constant pool instructions
- instructions with implicit register operands
- advanced dispatch techniques, like instruction duplication and context threading
- getting computed goto working on Windows
Performance on Windows has extra room to grow because the interpreter on Windows is not direct-threaded yet. In place of computed goto, it uses a switch statement inside a loop.
Not only is SquirrelFish exciting, but the post itself shows that they get that this is aimed at developers. Great job.
Posted by Dion Almaer at 9:21 am