Delegate stack efficiency

Question

Suppose I have written such a class (number of functions doesn't really matter, but in real, there will be somewhere about 3 or 4).

    private class ReallyWeird
    {
        int y;

        Func<double, double> f1;
        Func<double, double> f2;
        Func<double, double> f3;

        public ReallyWeird()
        {
            this.y = 10;

            this.f1 = (x => 25 * x + y);
            this.f2 = (x => f1(x) + y * f1(x));
            this.f3 = (x => Math.Log(f2(x) + f1(x)));
        }

        public double CalculusMaster(double x)
        {
            return f3(x) + f2(x);
        }
    }

I wonder if the C# compiler can optimize such a code so that it won't go through numerous stack calls.

Is it able to inline delegates at compile-time at all? If yes, on which conditions and to which limits? If no, is there an answer why?

Another question, maybe even more important: will it be significantly slower than if I had declared f1, f2 and f3 as methods?

I ask this because I want to keep my code as DRY as possible, so I want to implement a static class which extends the basic random number generator (RNG) functionality: its methods accept one delegate (e.g. from method NextInt() of the RNG) and returning another Func delegate (e.g. for generating ulongs), built on top of the former. and as long as there are many different RNG's which can generate ints, I prefer not to think about implementing all the same extended functionality ten times in different places.

So, this operation may be performed several times (i.e. initial method of the class may be 'wrapped' by a delegate twice or even three times). I wonder what will be the performance overhead like.

Thank you!

Answer 1

If you use Expression Trees instead of complete Func<> the compiler will be able to optimize the expressions.

Edit To clarify, note that I'm not saying the runtime would optimize the expression tree itself (it shouldn't) but rather that since the resulting Expression<> tree is .Compile()d in one step, the JIT engine will simply see the repeated subexpressions and be able to optimize, consolidate, substitue, shortcut and what else it does normally.

(I'm not absolutely sure that it does on all platforms, but at least it should be able to fully leverage the JIT engine)

---

Comment response

• First, expression trees has in potential shall equal execution speed as Func<> (however a Func<> will not have the same runtime cost - JITting probably takes place while jitting the enclosing scope; in case of ngen, it will even be AOT, as opposed to an expresseion tree)

• Second: I agree that Expression Trees can be hard to use. See here for a famous simple example of how to compose expressions. However, more complicated examples are pretty hard to come by. If I've got the time I'll see whether I can come up with a PoC and see what MS.Net and MONO actually generate in MSIL for these cases.

• Third: don't forget Henk Holterman is probably right in saying this is premature optimization (although composing Expression<> instead of Func<> ahead of time just adds the flexibility)

• Lastly, when you really think about driving this very far, you might consider using Compiler As A Service (which Mono already has, I believe it is still upcoming for Microsoft?).

Answer 2

I would not expect a compiler to optimize this. The complications (because of the delegates) would be huge.

And I would not worry about a few stack-frames here either. With 25 * x + y the stack+call overhead could be significant but call a few other methods (PRNG) and the part you are focusing on here becomes very marginal.

Answer 3

I compiled a quick test application where I compared the delegate approach to an approach where I defined each calculation as a function.

When doing 10.000.000 calculations for each version I got the following results:

• Running using delegates: 920 ms average
• Running using regular method calls: 730 ms average

So while there is a difference it is not very large and probably negligible.

Now, there may be an error in my calculations so I am adding the entire code below. I compiled it in release mode in Visual Studio 2010:

class Program
{
    const int num = 10000000;

    static void Main(string[] args)
    {

        for (int run = 1; run <= 5; run++)
        {
            Console.WriteLine("Run " + run);
            RunTest1();
            RunTest2();
        }
        Console.ReadLine();
    }

    static void RunTest1()
    {

        Console.WriteLine("Test1");

        var t = new Test1();

        var sw = Stopwatch.StartNew();
        double x = 0;
        for (var i = 0; i < num; i++)
        {
            t.CalculusMaster(x);
            x += 1.0;
        }
        sw.Stop();

        Console.WriteLine("Total time for " + num + " iterations: " + sw.ElapsedMilliseconds + " ms");

    }

    static void RunTest2()
    {

        Console.WriteLine("Test2");

        var t = new Test2();

        var sw = Stopwatch.StartNew();
        double x = 0;
        for (var i = 0; i < num; i++)
        {
            t.CalculusMaster(x);
            x += 1.0;
        }
        sw.Stop();

        Console.WriteLine("Total time for " + num + " iterations: " + sw.ElapsedMilliseconds + " ms");

    }
}

class Test1 
{
    int y;

    Func<double, double> f1;
    Func<double, double> f2;
    Func<double, double> f3;

    public Test1()
    {
        this.y = 10;

        this.f1 = (x => 25 * x + y);
        this.f2 = (x => f1(x) + y * f1(x));
        this.f3 = (x => Math.Log(f2(x) + f1(x)));
    }

    public double CalculusMaster(double x)
    {
        return f3(x) + f2(x);
    }

}
class Test2
{
    int y;


    public Test2()
    {
        this.y = 10;
    }

    private double f1(double x)
    {
        return 25 * x + y;
    }

    private double f2(double x)
    {
        return f1(x) + y * f1(x);
    }

    private double f3(double x)
    {
        return Math.Log(f2(x) + f1(x));
    }

    public double CalculusMaster(double x)
    {
        return f3(x) + f2(x);
    }

}