C#: Virtual Function invocation is even faster tha

Question

It just happens to me about one code design question. Say, I have one "template" method that invokes some functions that may "alter". A intuitive design is to follow "Template Design Pattern". Define the altering functions to be "virtual" functions to be overridden in subclasses. Or, I can just use delegate functions without "virtual". The delegate functions is injected so that they can be customized too.

Originally, I thought the second "delegate" way would be faster than "virtual" way, but some coding snippet proves it is not correct.

In below code, the first DoSomething method follows "template pattern". It calls on the virtual method IsTokenChar. The second DoSomthing method doesn't depend on virtual function. Instead, it has a pass-in delegate. In my computer, the first DoSomthing is always faster than the second. The result is like 1645:1780.

"Virtual invocation" is dynamic binding and should be more time-costing than direct delegation invocation, right? but the result shows it is not.

Anybody can explain this?

using System;
using System.Diagnostics;

class Foo
{
    public virtual bool IsTokenChar(string word)
    {
        return String.IsNullOrEmpty(word);
    }

    // this is a template method
    public int DoSomething(string word)
    {
        int trueCount = 0;
        for (int i = 0; i < repeat; ++i)
        {
            if (IsTokenChar(word))
            {
                ++trueCount;
            }
        }
        return trueCount;
    }

    public int DoSomething(Predicate<string> predicator, string word)
    {
        int trueCount = 0;
        for (int i = 0; i < repeat; ++i)
        {
            if (predicator(word))
            {
                ++trueCount;
            }
        }
        return trueCount;
    }

    private int repeat = 200000000;
}

class Program
{
    static void Main(string[] args)
    {
        Foo f = new Foo();

        {
            Stopwatch sw = Stopwatch.StartNew();
            f.DoSomething(null);
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);
        }

        {
            Stopwatch sw = Stopwatch.StartNew();
            f.DoSomething(str => String.IsNullOrEmpty(str), null);
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);
        }
    }
}

Answer 1

A virtual call is dereferencing two pointers at a well-known offset in the memory. It's not actually dynamic binding; there is no code at runtime to reflect over the metadata to discover the right method. The compiler generates couple of instructions to do the call, based on the this pointer. in fact, the virtual call is a single IL instruction.

A predicate call is creating an anonymous class to encapsulate the predicate. That class has to be instantiated and there is some code generated to actually check whether the predicate function pointer is null or not.

I would suggest you look at the IL constructs for both. Compile a simplified version of your source above with a single call to each of the two DoSomthing. Then use ILDASM to see what is the actual code for each pattern.

(And I am sure I'll get downvoted for not using the right terminology :-))

Answer 2

Just wanted to add a few corrections to john skeet's response:

A virtual method call does not need to do a null check (automatically handled with hardware traps).

It also does not need to walk up inheritance chain to find non-overriden methods (that's what the virtual method table is for).

A virtual method call is essentially one extra level of indirection when invoking. It is slower than a normal call because of the table look-up and subsequent function pointer call.

A delegate call also involves an extra level of indirection.

Calls to a delegate do not involve putting arguments in an array unless you are performing a dynamic invoke using the DynamicInvoke method.

A delegate call involves the calling method calling a compiler generated Invoke method on the delegate type in question. A call to predicator(value) is turned into predicator.Invoke(value).

The Invoke method in turn is implemented by the JIT to call the function pointer(s) (stored internally in the delegate object).

In your example, the delegate you passed should have been implemented as a compiler generated static method as the implementation does not access any instance variables or locals so therefore the need to access the "this" pointer from the heap should not be an issue.

The performance difference between delegate and virtual function calls should be mostly the same and your performance tests show that they are very close.

The difference could be due to the need to additional checks+branches because of multicast (as suggested by John). Another reason could be that the JIT compiler does not inline the Delegate.Invoke method and the implementation of Delegate.Invoke does not handle arguments as well as the implementation when performming virtual method calls.

Answer 3

Test result worth 1000 of words: http://kennethxu.blogspot.com/2009/05/strong-typed-high-performance_15.html

Answer 4

virtual overrides have some sort of redirection table or something which is hardcoded and fully optimized at compile time. It's set in stone, very fast.

Delegates are dynamic which will always have an overhead and they seem to be objects too so that adds up.

You shouldn't worry about these small performance differences (unless developing performance critical software for the military), for most purposes good code structure wins over optimization.

Answer 5

It is possible that since you don't have any methods that override the virtual method that the JIT is able to recognize this and use a direct call instead.

For something like this it's generally better to test it out as you have done than try to guess what the performance will be. If you want to know more about how delegate invocation works, I suggest the excellent book "CLR Via C#" by Jeffrey Richter.

Answer 6

I doubt it accounts for all of your difference, but one thing off the top of my head that may account for some of the difference is that virtual method dispatch already has the this pointer ready to go. When calling through a delegate the this pointer has to be fetched from the delegate.

Note that according to this blog article the difference was even greater in .NET v1.x.