Performance of C# method polymorphism with generics

Question

I noticed in C#, unlike C++, you can combine virtual and generic methods. For example:

using System.Diagnostics;

class Base {
    public virtual void Concrete() {Debug.WriteLine("base concrete");}
    public virtual void Generic<T>() {Debug.WriteLine("base generic");}
}

class Derived : Base {
    public override void Concrete() {Debug.WriteLine("derived concrete");}
    public override void Generic<T>() {Debug.WriteLine("derived generic");}
}

class App {
    static void Main() {
        Base x = new Derived();
        x.Concrete();
        x.Generic<PerformanceCounter>();
    }
}

Given that any number of versions of Generic<T> could be instantiated, it doesn't look like the standard vtbl approach could be used to resolve method calls, and in fact it's not. Here's the generated code:

        x.Concrete();
mov         ecx,dword ptr [ebp-8] 
mov         eax,dword ptr [ecx] 
call        dword ptr [eax+38h] 
        x.Generic<PerformanceCounter>();
push        989A38h 
mov         ecx,dword ptr [ebp-8] 
mov         edx,989914h 
call        76A874F1 
mov         dword ptr [ebp-4],eax 
mov         ecx,dword ptr [ebp-8] 
call        dword ptr [ebp-4] 

The extra code appears to be looking up a dynamic vtbl according to the generic parameters, and then calling into it. Has anyone written about the specifics of this implementation? How well does it perform compared to the non-generic case?

Answer 1

Eric Lippert writes quite a lot about the C# compiler and has a bunch of posts about generics and how they are implemented. I don't think however that he goes into that kind of detail.

Answer 2

The way .NET generics are implemented, for each use of a generic class (or method), the CLR creates a new implemention of that class (or method) with the generic parameter filled in. For reference types, they all share a single implementation (as they're all just pointers of the same size); structs each have their own implementation as the sizes are all different.

So I'm guessing that each implementation of a generic type/method has it's own vtable as well, and that code is doing a 'lookup generic implementation', then a 'lookup vtable override' on the implementation it finds.

Answer 3

The .NET generics implementation can handle such a scenario easily and with very good performance. I have written a blog post about it a while ago.

One of the best resources for finding information about the how the CLR implements generics is this paper by Micosoft Research.

You got the thing about the vtable right. How the CLR creates executable code for a generic type when the JIT compiler stumbles upon one, depends on the generic type parameter. The handling is different for value types and reference types.

While the exectuable code (instantiation, the native image) is shared among instantiations for all generic type parameters that are reference types, the vtable associated with an instance (object) of the instantiation is unique to the concrete parameter type.

Here's the relevant quote from the above mentioned paper:

4.2 Object representation Objects in the CLR’s garbage-collected heap are represented by a vtable pointer followed by the object’s contents (e.g. fields or array elements). The vtable’s main role is virtual method dispatch: it contains a code pointer for each method that is defined or inherited by the object’s class. But for simple class types, at least, where there is a one-to-one correspondence between vtables and classes, it can also be used to represent the object’s type. When the vtable is used in this way we call it the type’s type handle. In an implementation of polymorphism based on full specialization, the notion of exact run-time type comes for free as different instantiations of the same parameterized type have different vtables. But now suppose that code is shared between different in- stantiations such as List<string> and List<object>. The vtables for the two instantiations will be identical, so we need some way of representing the instantiation at run-time.

...

[For each instantiation, we ]Replace the vtable pointer by a pointer to a combined vtable- and-instantiation structure and duplicate it [the structure] per instantiation.