Can C# generics be used to elide virtual function calls?

Question

I use both C++ and C# and something that's been on my mind is whether it's possible to use generics in C# to elide virtual function calls on interfaces. Consider the following:

int Foo1(IList<int> list)
{
    int sum = 0;
    for(int i = 0; i < list.Count; ++i)
        sum += list[i];
    return sum;
}

int Foo2<T>(T list) where T : IList<int>
{
    int sum = 0;
    for(int i = 0; i < list.Count; ++i)
        sum += list[i];
    return sum;
}

/*...*/
var l = new List<int>();
Foo1(l);
Foo2(l);

Inside Foo1, every access to list.Count and list[i] causes a virtual function call. If this were C++ using templates, then in the call to Foo2 the compiler would be able to see that the virtual function call can be elided and inlined because the concrete type is known at template instantiation time.

But does the same apply to C# and generics? When you call Foo2(l), it's known at compile-time that T is a List and therefore that list.Count and list[i] don't need to involve virtual function calls. First of all, would that be a valid optimization that doesn't horribly break something? And if so, is the compiler/JIT smart enough to make this optimization?

Answer 1

This is an interesting question, but unfortunately, your approach to "cheat" the system won't improve the efficiency of your program. If it could, the compiler could do it for us with relative ease!

You are correct that when calling IList<T> through an interface reference, that the methods are dispatched at runtime and therefore cannot be inlined. Therefore the calls to IList<T> methods such as Count and the indexer will be called through the interface.

On the other hand, it is not true that you can achieve any performance advantage (at least not with the current C# compiler and .NET4 CLR), by rewriting it as a generic method.

Why not? First some background. The C# generics work is that the compiler compiles your generic method that has replaceable parameters and then replaces them at run-time with the actual parameters. This you already knew.

But the parameterized version of the method knows no more about the variable types than you and I do at compile time. In this case, all the compiler knows about Foo2 is that list is an IList<int>. We have the same information in the generic Foo2 that we do in the non-generic Foo1.

As a matter of fact, in order to avoid code-bloat, the JIT compiler only produces a single instantiation of the generic method for all reference types. Here is the Microsoft documentation that describes this substitution and instantiation:

If the client specifies a reference type, then the JIT compiler replaces the generic parameters in the server IL with Object, and compiles it into native code. That code will be used in any further request for a reference type instead of a generic type parameter. Note that this way the JIT compiler only reuses actual code. Instances are still allocated according to their size off the managed heap, and there is no casting.

This means that the JIT compiler's version of the method (for reference types) is not type safe but it doesn't matter because the compiler has ensured all type-safety at compile time. But more importantly for your question, there is no avenue to perform inlining and get a performance boost.

Edit: Finally, empirically, I've just done a benchmark of both Foo1 and Foo2 and they yield identical performance results. In other words, Foo2 is not any faster than Foo1.

Let's add an "inlinable" version Foo0 for comparison:

int Foo0(List<int> list)
{
    int sum = 0;
    for (int i = 0; i < list.Count; ++i)
        sum += list[i];
    return sum;
}

Here is the performance comparison:

Foo0 = 1719
Foo1 = 7299
Foo2 = 7472
Foo0 = 1671
Foo1 = 7470
Foo2 = 7756

So you can see that Foo0, which can be inlined, is dramatically faster than the other two. You can also see that Foo2 is slightly slower instead of being anywhere near as fast as Foo0.

Answer 2

This actually does work, and does (if the function is not virtual) result in a non-virtual call. The reason is that unlike in C++, CLR generics define, at JIT time, a specific, concrete class for each unique set of generic parameters (indicated via reflection via trailing 1, 2 etc). If the method is virtual, it will result in a virtual call like any concrete, non-virtual, non-generic method.

The thing to remember about .net generics is that given:

Foo<T>; 

then

Foo<Int32>

is a valid Type at runtime, separate and distinct from

Foo<String>

, and all virtual and non-virtual methods are treated accordingly. This is the reason why you can create a

List<Vehicle>

and add a Car to it, but you can't create a variable of type

List<Vehicle> 

and set its value to an instance of

List<Car>

. They are of different types, but the former has an Add(...) method that takes an argument of Vehicle, a supertype of Car.