Trees vs Arrays: Expression Evaluation in C# Part 3

Alright, I'm back with the latest news. I implemented the IL emitter, which can be either painfully slow, or jaw-droppingly-ridiculously fast, depending on how it's called.

The code is pretty simple, too:

public static EvaluatorDelegate GetDynamicMethod(Tree e)
{
    DynamicMethod m = new DynamicMethod("Evaluation" + DateTime.Now.ToString(), typeof(long), new Type[] { }, typeof(Evaluator), false);

    ILGenerator il = m.GetILGenerator();

    foreach (string t in e.PostFix)
    {
        if (t == "+")
        {
            il.Emit(OpCodes.Add);
        }
        else if (t == "-")
        {
            il.Emit(OpCodes.Sub);
        }
        else if (t == "*")
        {
            il.Emit(OpCodes.Mul);
        }
        else if (t == "/")
        {
            il.Emit(OpCodes.Div);
        }
        else
        {
            long a = Convert.ToInt64(t);
            il.Emit(OpCodes.Ldc_I8, a);
        }
    }

    il.Emit(OpCodes.Ret);

    EvaluatorDelegate del = (EvaluatorDelegate)m.CreateDelegate(typeof(EvaluatorDelegate));
    return del;
}

The first thing you should notice is that there are no stacks. The CLR runtime uses an execution stack, so it's all being handled internally. It loads numbers as they appear to the stack, and then operates on them. At least this implementation, if not any of the others, should make it obvious that reverse polish notation is where it's at. Evaluation is about as simple as it gets.

It will certainly get more complicated to code once I add in some function calls, but it will still be much faster than any of the previous methods.

Getting back to performance... The first time I ran it, it ran very slowly, about as fast as the Tree Evaluator. I was justifiably saddened. But I had used Invoke() to start it every time, which is what was killing performance. From what I've read, Invoke is about 100x slower than a direct call, while invoking a delegate is only a few times slower.

I rewrote it with a delegate, and it trompled the competition:

Array Evaluation: 999ms
Tree Evaluation: 2433ms
Delegate Evaluation: 47ms
Dynamic Method Delegate Evaluation: 15ms

That's 1.5% of the original time required for that evaluation. I can calculate 66x more values now! Yessss...

But realistically, is being 3x faster worth emitting my own OpCodes? It's a tough call. In this instance, no. But you add a few trig functions in there, parameter substitution, and twice as many evaluations, and it might be worth more than a few milliseconds.