3

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.

2

2 Answers 2

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.

3
  • 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?
    – Veler
    Apr 10, 2018 at 20:37
  • Yes, it's pretty trivial to output pdb info using the emit code.
    – Telastyn
    Apr 10, 2018 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.
    – Veler
    Apr 10, 2018 at 21:30
1

LinearLisp vs Python vs MS JScript

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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