Scripting language parser

Question

I'm making a scripting language parser and it's shaping up well but it takes about 30ms to do 30 or so odd/even checks.

Profiler tells me that it's taking most of the time in the InvokeOperator.Operate function but that doesn't tell me a lot because the Operate call the Run method on the CodeBlock which in turn again calls the Operate call and makes it very hard to actually determine what's taking as long.

Here's the Github repo

Here are the most important bits of the code:

Stack<Token> solvingStack = new Stack<Token>();
for ( int i = 0 ; i < value.Count ; ++i )
{
 if ( value[ i ] is Operator )
 {
 Operator op = (Operator)value[ i ];
 if ( op.Type == OperatorType.PrefixUnary || op.Type == OperatorType.SufixUnary )
 {
 op.Operate( ( solvingStack.Pop() as Value ), new NoValue() );
 } else
 {
 Value second = (Value)solvingStack.Pop();
 Value result = op.Operate( ( solvingStack.Pop() as Value ), second );
 solvingStack.Push( result );
 }
 } else
 {
 solvingStack.Push( value[ i ] );
 }
}
Compiler.ExitScope();
if ( solvingStack.Count == 0 ) return new NoValue();
else return (Value)solvingStack.Peek();

It's how the code is parsed after the infix expression is turned into RPN. A token can be an operator or a value and a value can be a literal, identifier, codeblock.

A somewhat special case is a function because it's not parsed to RPN directly but only the code inside of it is. Then is there's an invoke operator, it takes the array of arguments that was provided and the function before it and runs the function (which inherits from CodeBlock, so it also runs the same thing that is shown here).

What each operator does on different types of values is determined by the operator itself in the Operators.cs file.

• Snowbear: see Make sure you include your code in your question part in FAQ
• sepp2k: As @Snowbear points out, we do require questions to contain the relevant code inside the post. If you can edit your post to contain the most important parts of the code and a summary of the ones you left out, so that the code can be meaningfully reviewed based on the code in the question, please do so. If that's not possible, I'm afraid this question is not appropriate here.
• Michael K: Is this the InvokeOperator.Operate method?
• Snowbear: @Michael, no, it's CodeBlock.Run() method
• Snowbear: @Darwin, replace it with (num & 1) == 1, it should be faster

Answer 1

I am not sure if these are bottlenecks, but they are at least performance improvements.

1. Replace Stack<Token> with Stack<Value> since you are only pushing/popping Value. This way there is no need to do expensive casts.

2. You can replace

   if ( value[ i ] is Operator )
   {
    Operator op = (Operator)value[ i ];
   

   with

   Operator op = value[ i ] as Operator;
   if ( op != null ) // it was an Operator
   

   to have only one typecheck (x as y) instead of two (x is y and (y) x).

3. You can replace

   for ( int i = 0 ; i < value.Count ; ++i )
   

   with

   foreach(Token item in value)
   

   to eliminate the index operations value[ i ].

Answer 2

I suggest you try using a profiler of some sort in order to determine exactly where the bottleneck is. Once you do that, it will much easier to find how to avoid it.

• Darwin: Profiler tells me that it's taking most of the time in the InvokeOperator.Operate function but that doesn't tell me a lot because the Operate call the Run method on the CodeBlock which in turn again calls the Operate call and makes it very hard to actually determine what's taking as long.
• Sam Bloomberg: What you need to do is profile the function calls inside the operate call, then figure out which one exactly is taking so long. Then go into that and do the same thing.