Optimizing Interpreters: Fusion

submited by

Style Pass

2024-09-01 13:30:04

Let me start with making an assumption that everyone has at some point in their life encountered a humble tree-walking interpreter.

Between older implementations of popular programming languages, expression evaluators embedded in user-facing tools, and home-grown almost-a-complete-Lisp interpreters, these can still be found everywhere.

This type of interpreter is considered to be the simplest - and the slowest one. Oftentimes you may see people rewriting their interpreters to a bytecode-based ones just to get a bit more performance.

However, recently a project named daScript (apparently renamed to Daslang) came into my attention. It is a very fast programming language, boasting one of the fastest interpreters I ever saw.

What is more interesting is that this interpreter is tree-based, and yet it still manages to outperform bytecode-based interpreters with ease.

I got nerd-sniped and set out to investigate why is it so fast, and I found that it uses a pretty interesting optimization technique which authors call fusion. As always, it turned out that the idea has already been explored and is also known as supernodes or, in context of bytecode interpreters, as superoperators.