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
- The Lexer transforms the text into a set of tokens.
- The Parser transforms it into an AST (Abstract Syntax Tree) similar to the System.CodeDom structure.
- 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.
- 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
- 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.
- 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.
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.
- 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.
- 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.
- 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.