1

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.

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.

  • Thanks for your reply. Yes, that's what I'm thinking to do more and more. One last thing : I'm optionally plan to implement a debugger to give the possibility to pause the execution and explore the call stack, variable's values...etc. Is it still possible to do by emitting bytecode? If I understand well it will generates an assembly in memory, so except with the Windows/.Net debugger or a homemade dirty bridge between the generated assembly and my program, I don't see how I can do it. Is there something for this? – Etienne Baudoux Apr 10 '18 at 20:37
  • Yes, it's pretty trivial to output pdb info using the emit code. – Telastyn Apr 10 '18 at 21:02
  • That makes totally sense. Then, like in in VS in fact, I think I will make 2 mode : Debug, that interprets the AST and gives the possibility to go step by step and set breakpoint. And Release : that emit the AST and run faster. – Etienne Baudoux Apr 10 '18 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.