Direction to take to improve a AST interpreter

Question

I'm looking for some opinions/advices about a particular subject. Here is the situation : I'm developing for fun, in my spare time, a programming language interpreter made in C# and I'm looking for improving its speed. I've made a Lexer (works great !), a Parser (works great !), Optimizer (works great !) and Interpreter (works great, but could be much better).

I've made a small syntax that is a mix of BASIC and VB.Net. It looks like this :

FUNCTION Main(args[])
    # The language actually supports .Net API.
    System.Console.WriteLine(FirstMethod(100).ToString())
END FUNCTION

FUNCTION FirstMethod(num)
    IF num > 1 THEN
        RETURN FirstMethod(num - 1)
    END IF
    RETURN num
END FUNCTION

Components

1. The Lexer transforms the text into a set of tokens.
2. The Parser transforms it into an AST (Abstract Syntax Tree) similar to the System.CodeDom structure.
3. As the interpreter interprets the algorithm in recursive way, with the code above, we will reach a StackOverflowException quickly. So the Optimizer's role is mainly to inline the method call, loop, condition...etc. It replaces it by a set of Label, GoTo and Conditions. The goal is to have at the end a method body with only ONE block. It works pretty well too. I don't get any StackOverflow even if I run the code above with 1000000 in argument.
4. Then the Interpreter will browse the AST and interpret everything. This component architecture is similar to this PoC I've made a few years ago. https://github.com/veler/AlgorithmSimulator But please note that it's way different in several points, in particular the way it runs binary operators.

Relevant points about the interpreter

1. It's made in .Net and my language supports the access to object's properties and .Net methods. So basically I can write "RETURN num.ToString()", it will work thanks to Reflection. The Properties and Methods, when called for the first time, are stored in a delegate cache so it's faster to call the second time.
2. Binary operators, in my new version, are implemented by using the dynamic keyword. Not the best for performances. But at this point good for maintenance and it's easy to read. I'm conscious it's definitely not the most optimized solution.

Performances

So talking about the performances, the algorithm above, with my previous implementation of 2015 on GitHub, takes about 8 milliseconds to run on a Intel i5. My new implementation that caches the access to properties/methods and use the Dynamic keyword takes about 5 milliseconds to run (without counting the time to parse and optimize).

Using the Optimizer to inline everything improves the speed by 10% in average (and it depends of the algorithm of course).

It's nice, but still slow haha

So now that I have a PoC I enjoyed to make, I would like to make it faster. The interpreter in particular (the other components are "OK"). The first thing I did is to take a look at Performance Profiler in Visual Studio, but compared to some other projects (pro or personal) I don't see anything relevant (The Reflection is not very slower compared to the rest of the program, it's still slow if I don't do any binary operator... I have a lot of Switch on types but I didn't found a clean way to escape from this...etc). Everything goes pretty fast, but the global result is slow. So everything is slow in fact...

I have several ideas in mind, that would requires to rewrite most of the interpreter (but I'm fine with it, it's a project for fun after what), and I would like your opinion about it.

1. Using IL.Emit : If I understand well, it will inject CIL/MSIL directly at runtime. Looks great for a small expression (like binary operator... this could be my next implementation of this specific part), but it looks tricky to implement for an entire AST.
2. Compile Linq.Expressions : I already use it to solve automatically a constructor and instantiate a class when the user use a syntax like "NEW Namespace.Class(Foo, Bar)". It works like a charm and, as I keep the constructors in a cache thanks to delegate, performances are better than with a full Reflection process. From what I saw in Reference Source website, it uses IL.Emit. But could it still work for an entire AST? I'm wondering.
3. I saw that the library "CSScript" (http://csscript.net/) interprets "any statement in the script only once even if the statement is frequently used throughout the code". Does anyone has a technical explanation of how does this black magic works?

Final point : my first PoC that dates from a few years had its own system to run the algorithm step by step, set breakpoints in a algorithm and take a look at the call stack with the value of all the variables (it was fun to implement !). It's not implemented in my last PoC and I don't know if by using one of those 2 firsts ideas I'll be able to do it again. But I'm fine with it. It's a side goal.

I'm opened to any opinion and other ideas. =) Let's discuss about it?

Please note that I don't want to use libraries that does everything for me (http://csscript.net/ or Roslyn and friends). My goal is to have fun with a challenging project and learn. I also don't want to rewrite it in C++. I'm convinced there is a way to make this .Net project faster.

Answer 1

Emitting actual bytecode will (pretty much) always have the best performance of those options (for this sort of code) because the translation from AST to operations happens at compile time rather than runtime - and you're not likely to take advantage of run time information to perform further optimization.

And honestly, emitting bytecode is easier too once you get over the little learning curve since it should map more closely to your AST.

Answer 2

AST-walking interpreters do not have to be slow.

In fact, you can implement one for .NET 6 with run time performance in the same ballpark as Python 3.10, and in just a few hundreds of lines of C# and easily extensible.

I've done it:

https://github.com/ysharplanguage/LinearLisp

I've dubbed the technique as "full linearization" (of said AST).

Getting rid as much as possible of references to instances of reference types is key to letting automatic memory management, likewise, go on vacation for as many CPU cycles as possible (hence, avoid paying for its overhead during the evaluation of terms in expressions, of expressions in special forms or other syntactic sugar constructs, etc).

It isn't too hard to see why full linearization certainly counts among the best friends of cache locality, also.

(Contrariwise, frantically walking naively implemented ASTs full of references all over the place on the heap - as it has been traditionally done for long for such interpreters - is a sure way of throwing cache locality out of the window.)

So, don't take my word for it, and feel free to just check out the upper bounds used in the various micro benchmarks for the experiment linked above, and see for yourself that most of these run in under a second or two on modern machines.

Not hours, not minutes. Just within seconds.