How can C# allow virtual generic methods where C++ can't allow virtual template methods?

Question

C++ does not support virtual template methods. The reason is that this would alter the vtable whenever a new instantiation of such a method is made (it has to be added to the vtable).

Java in contrast does allow virtual generic methods. Here, it is also clear how this can be implemented: Java generics are erased at runtime, so a generic method is a usual method at runtime, so no alterations of the vtable necessary.

But now to C#. C# does have reified generics. With reified generics and especially when using value types as type parameters, there have to be different versions of a generic method. But then we have the same problem as C++ has: We would need to alter the vtable whenever a new instantiation of a generic method was made.

I am not too deep into the inner workings of C#, so my intuition could simply be totally wrong. So can someone with more in-depth knowledge about C#/.NET tell me how they are able to implement generic virtual methods in C#?

Here's code to show what I mean:

[MethodImpl(MethodImplOptions.NoInlining)]
static void Test_GenericVCall()
{
    var b = GetA();
    b.M<string>();
    b.M<int>();
}

[MethodImpl(MethodImplOptions.NoInlining)]
static A GetA()
{
    return new B();
}

class A
{
    public virtual void M<T>()
    {
    }
}

class B : A
{
    public override void M<T>()
    {
        base.M<T>();
        Console.WriteLine(typeof(T).Name);
    }
}

How does the CLR dispatch to the correct JITed code when calling M in the function Test_GenericVCall?

Ayesha

Generics in c++ and c# are handled in very different ways! Your question is too broad. – Winonawinonah

@πάνταῥεῖ: i don't think it's too broad. one can hardly ask about this without using some concrete example. – Wagtail

@Cheersandhth.-Alf I'd say the reason why c# can support this is that the language has reflection (available at runtime). That's a really broad field. I seriously doubt, an example would make it easier to explain all that. – Winonawinonah

@πάνταῥεῖ: still, for those voting to close: one doesn't know that a question is too broad until it's been shown to not be too broad. one should not vote to close just because one is unable to answer the question. others may not necessarily be unable to answer. – Wagtail

The jitted code calls into a helper method to obtain the address of the function to call. Visual Studio doesn't let me debug into that helper. This is certainly not an ordinary virtual call. – Iver

Reified generics generate the concrete types at runtime. So there can never be a problem with dispatch tables, they are distinct. – Archdiocese

@HansPassant in the example code there is only one vtable that has to dispatch to two different methods depending on the generic argument. – Iver

@πάνταῥεῖ: I think the great answers that have been posted (paired with the upvotes) show that the question is not too broad. It asks a very precise thing (how can C# handle generic methods where other languages have problems) and the given answers are very concise. – Ayesha

@Ayesha IMHO they just improve that your question was 'too broad' :-/ ... – Winonawinonah

Answer 1

Running this code and analyzing the IL and generated ASM allows us to see what is going on:

internal class Program
{
    [MethodImpl(MethodImplOptions.NoInlining)]
    private static void Test()
    {
        var b = GetA();
        b.GenericVirtual<string>();
        b.GenericVirtual<int>();
        b.GenericVirtual<StringBuilder>();
        b.GenericVirtual<int>();
        b.GenericVirtual<StringBuilder>();
        b.GenericVirtual<string>();
        b.NormalVirtual();
    }

    [MethodImpl(MethodImplOptions.NoInlining)]
    private static A GetA()
    {
        return new B();
    }

    private class A
    {
        public virtual void GenericVirtual<T>()
        {
        }

        public virtual void NormalVirtual()
        {
        }
    }

    private class B : A
    {
        public override void GenericVirtual<T>()
        {
            base.GenericVirtual<T>();
            Console.WriteLine("Generic virtual: {0}", typeof(T).Name);
        }

        public override void NormalVirtual()
        {
            base.NormalVirtual();
            Console.WriteLine("Normal virtual");
        }
    }

    public static void Main(string[] args)
    {
        Test();
        Console.ReadLine();
        Test();
    }
}

I breakpointed Program.Test with WinDbg:

.loadby sos clr; !bpmd CSharpNewTest CSharpNewTest.Program.Test

I then used Sosex.dll's great !muf command to show me interleaved source, IL and ASM:

0:000> !muf
CSharpNewTest.Program.Test(): void
    b:A

        002e0080 55              push    ebp
        002e0081 8bec            mov     ebp,esp
        002e0083 56              push    esi
var b = GetA();
    IL_0000: call CSharpNewTest.Program::GetA()
    IL_0005: stloc.0  (b)
>>>>>>>>002e0084 ff15c0371800    call    dword ptr ds:[1837C0h]
        002e008a 8bf0            mov     esi,eax
b.GenericVirtual<string>();
    IL_0006: ldloc.0  (b)
    IL_0007: callvirt A::GenericVirtuallong
        002e008c 6800391800      push    183900h
        002e0091 8bce            mov     ecx,esi
        002e0093 ba50381800      mov     edx,183850h
        002e0098 e877e49b71      call    clr!JIT_VirtualFunctionPointer (71c9e514)
        002e009d 8bce            mov     ecx,esi
        002e009f ffd0            call    eax
b.GenericVirtual<int>();
    IL_000c: ldloc.0  (b)
    IL_000d: callvirt A::GenericVirtuallong
        002e00a1 6830391800      push    183930h
        002e00a6 8bce            mov     ecx,esi
        002e00a8 ba50381800      mov     edx,183850h
        002e00ad e862e49b71      call    clr!JIT_VirtualFunctionPointer (71c9e514)
        002e00b2 8bce            mov     ecx,esi
        002e00b4 ffd0            call    eax
b.GenericVirtual<StringBuilder>();
    IL_0012: ldloc.0  (b)
    IL_0013: callvirt A::GenericVirtuallong
        002e00b6 6870391800      push    183970h
        002e00bb 8bce            mov     ecx,esi
        002e00bd ba50381800      mov     edx,183850h
        002e00c2 e84de49b71      call    clr!JIT_VirtualFunctionPointer (71c9e514)
        002e00c7 8bce            mov     ecx,esi
        002e00c9 ffd0            call    eax
b.GenericVirtual<int>();
    IL_0018: ldloc.0  (b)
    IL_0019: callvirt A::GenericVirtuallong
        002e00cb 6830391800      push    183930h
        002e00d0 8bce            mov     ecx,esi
        002e00d2 ba50381800      mov     edx,183850h
        002e00d7 e838e49b71      call    clr!JIT_VirtualFunctionPointer (71c9e514)
        002e00dc 8bce            mov     ecx,esi
        002e00de ffd0            call    eax
b.GenericVirtual<StringBuilder>();
    IL_001e: ldloc.0  (b)
    IL_001f: callvirt A::GenericVirtuallong
        002e00e0 6870391800      push    183970h
        002e00e5 8bce            mov     ecx,esi
        002e00e7 ba50381800      mov     edx,183850h
        002e00ec e823e49b71      call    clr!JIT_VirtualFunctionPointer (71c9e514)
        002e00f1 8bce            mov     ecx,esi
        002e00f3 ffd0            call    eax
b.GenericVirtual<string>();
    IL_0024: ldloc.0  (b)
    IL_0025: callvirt A::GenericVirtuallong
        002e00f5 6800391800      push    183900h
        002e00fa 8bce            mov     ecx,esi
        002e00fc ba50381800      mov     edx,183850h
        002e0101 e80ee49b71      call    clr!JIT_VirtualFunctionPointer (71c9e514)
        002e0106 8bce            mov     ecx,esi
        002e0108 ffd0            call    eax
b.NormalVirtual();
    IL_002a: ldloc.0  (b)
        002e010a 8bce            mov     ecx,esi
        002e010c 8b01            mov     eax,dword ptr [ecx]
        002e010e 8b4028          mov     eax,dword ptr [eax+28h]
    IL_002b: callvirt A::NormalVirtual()
        002e0111 ff5014          call    dword ptr [eax+14h]
}
    IL_0030: ret 

Of interest is the normal virtual call, which can be compared to the generic virtual calls:

b.NormalVirtual();
    IL_002a: ldloc.0  (b)
        002e010a 8bce            mov     ecx,esi
        002e010c 8b01            mov     eax,dword ptr [ecx]
        002e010e 8b4028          mov     eax,dword ptr [eax+28h]
    IL_002b: callvirt A::NormalVirtual()
        002e0111 ff5014          call    dword ptr [eax+14h]

Looks very standard. Let's take a look at the generic calls:

b.GenericVirtual<string>();
    IL_0024: ldloc.0  (b)
    IL_0025: callvirt A::GenericVirtuallong
        002e00f5 6800391800      push    183900h
        002e00fa 8bce            mov     ecx,esi
        002e00fc ba50381800      mov     edx,183850h
        002e0101 e80ee49b71      call    clr!JIT_VirtualFunctionPointer (71c9e514)
        002e0106 8bce            mov     ecx,esi
        002e0108 ffd0            call    eax

Ok, so the generic virtual calls are handled by loading our object b (which is in esi, being moved into ecx), and then calling into clr!JIT_VirtualFunctionPointer. Two constants are also pushed: 183850 in edx. We can conclude that this is probably the handle for the function A.GenericVirtual<T>, as it does not change for any of the 6 call sites. The other constant, 183900, looks to be the type handle for the generic argument. Indeed, SSCLI confirms the suspicions:

HCIMPL3(CORINFO_MethodPtr, JIT_VirtualFunctionPointer, Object * objectUNSAFE, CORINFO_CLASS_HANDLE classHnd, CORINFO_METHOD_HANDLE methodHnd)

So, the lookup is basically delegated to JIT_VirtualFunctionPointer, which must prepare an address that can be called. Supposedly it will either JIT it and return a pointer to the JIT'ted code, or make a trampoline which, when called the first time, will JIT the function.

0:000> uf clr!JIT_VirtualFunctionPointer
clr!JIT_VirtualFunctionPointer:
71c9e514 55              push    ebp
71c9e515 8bec            mov     ebp,esp
71c9e517 83e4f8          and     esp,0FFFFFFF8h
71c9e51a 83ec0c          sub     esp,0Ch
71c9e51d 53              push    ebx
71c9e51e 56              push    esi
71c9e51f 8bf2            mov     esi,edx
71c9e521 8bd1            mov     edx,ecx
71c9e523 57              push    edi
71c9e524 89542414        mov     dword ptr [esp+14h],edx
71c9e528 8b7d08          mov     edi,dword ptr [ebp+8]
71c9e52b 85d2            test    edx,edx
71c9e52d 745c            je      clr!JIT_VirtualFunctionPointer+0x70 (71c9e58b)

clr!JIT_VirtualFunctionPointer+0x1b:
71c9e52f 8b12            mov     edx,dword ptr [edx]
71c9e531 89542410        mov     dword ptr [esp+10h],edx
71c9e535 8bce            mov     ecx,esi
71c9e537 c1c105          rol     ecx,5
71c9e53a 8bdf            mov     ebx,edi
71c9e53c 03ca            add     ecx,edx
71c9e53e c1cb05          ror     ebx,5
71c9e541 03d9            add     ebx,ecx
71c9e543 a180832872      mov     eax,dword ptr [clr!g_pJitGenericHandleCache (72288380)]
71c9e548 8b4810          mov     ecx,dword ptr [eax+10h]
71c9e54b 33d2            xor     edx,edx
71c9e54d 8bc3            mov     eax,ebx
71c9e54f f77104          div     eax,dword ptr [ecx+4]
71c9e552 8b01            mov     eax,dword ptr [ecx]
71c9e554 8b0490          mov     eax,dword ptr [eax+edx*4]
71c9e557 85c0            test    eax,eax
71c9e559 7430            je      clr!JIT_VirtualFunctionPointer+0x70 (71c9e58b)

clr!JIT_VirtualFunctionPointer+0x47:
71c9e55b 8b4c2410        mov     ecx,dword ptr [esp+10h]

clr!JIT_VirtualFunctionPointer+0x50:
71c9e55f 395804          cmp     dword ptr [eax+4],ebx
71c9e562 7521            jne     clr!JIT_VirtualFunctionPointer+0x6a (71c9e585)

clr!JIT_VirtualFunctionPointer+0x55:
71c9e564 39480c          cmp     dword ptr [eax+0Ch],ecx
71c9e567 751c            jne     clr!JIT_VirtualFunctionPointer+0x6a (71c9e585)

clr!JIT_VirtualFunctionPointer+0x5a:
71c9e569 397010          cmp     dword ptr [eax+10h],esi
71c9e56c 7517            jne     clr!JIT_VirtualFunctionPointer+0x6a (71c9e585)

clr!JIT_VirtualFunctionPointer+0x5f:
71c9e56e 397814          cmp     dword ptr [eax+14h],edi
71c9e571 7512            jne     clr!JIT_VirtualFunctionPointer+0x6a (71c9e585)

clr!JIT_VirtualFunctionPointer+0x64:
71c9e573 f6401801        test    byte ptr [eax+18h],1
71c9e577 740c            je      clr!JIT_VirtualFunctionPointer+0x6a (71c9e585)

clr!JIT_VirtualFunctionPointer+0x85:
71c9e579 8b4008          mov     eax,dword ptr [eax+8]
71c9e57c 5f              pop     edi
71c9e57d 5e              pop     esi
71c9e57e 5b              pop     ebx
71c9e57f 8be5            mov     esp,ebp
71c9e581 5d              pop     ebp
71c9e582 c20400          ret     4

clr!JIT_VirtualFunctionPointer+0x6a:
71c9e585 8b00            mov     eax,dword ptr [eax]
71c9e587 85c0            test    eax,eax
71c9e589 75d4            jne     clr!JIT_VirtualFunctionPointer+0x50 (71c9e55f)

clr!JIT_VirtualFunctionPointer+0x70:
71c9e58b 8b4c2414        mov     ecx,dword ptr [esp+14h]
71c9e58f 57              push    edi
71c9e590 8bd6            mov     edx,esi
71c9e592 e8c4800400      call    clr!JIT_VirtualFunctionPointer_Framed (71ce665b)
71c9e597 5f              pop     edi
71c9e598 5e              pop     esi
71c9e599 5b              pop     ebx
71c9e59a 8be5            mov     esp,ebp
71c9e59c 5d              pop     ebp
71c9e59d c20400          ret     4

The implementation can be viewed in SSCLI, and it looks like it is still applicable:

HCIMPL3(CORINFO_MethodPtr, JIT_VirtualFunctionPointer, Object * objectUNSAFE,
                                                       CORINFO_CLASS_HANDLE classHnd,
                                                       CORINFO_METHOD_HANDLE methodHnd)
{
    CONTRACTL {
        SO_TOLERANT;
        THROWS;
        DISABLED(GC_TRIGGERS);      // currently disabled because of FORBIDGC in HCIMPL
    } CONTRACTL_END;

    OBJECTREF objRef = ObjectToOBJECTREF(objectUNSAFE);

    if (objRef != NULL && g_pJitGenericHandleCache)
    {
        JitGenericHandleCacheKey key(objRef->GetMethodTable(), classHnd, methodHnd);
        HashDatum res;
        if (g_pJitGenericHandleCache->GetValueSpeculative(&key,&res))
            return (CORINFO_GENERIC_HANDLE)res;
    }

    // Tailcall to the slow helper
    ENDFORBIDGC();
    return HCCALL3(JIT_VirtualFunctionPointer_Framed, OBJECTREFToObject(objRef), classHnd, methodHnd);
}
HCIMPLEND

So basically it checks a cache to see if we have seen this type/class combination before, and otherwise sends it off to JIT_VirtualFunctionPointer_Framed which calls into MethodDesc::GetMultiCallableAddrOfVirtualizedCode to get an address of it. The MethodDesc call is passed the object reference and generic type handle so it can look up what virtual function to dispatch to, and what version of the virtual function (ie. with what generic parameter).

All of this can be viewed in SSCLI if you want to go more in depth - it seems this has not changed with the 4.0 version of the CLR.

In short, the CLR does what you would expect; generate different call sites which carry information of the type that the virtual, generic function is called with. This is then passed to the CLR to do the dispatch. The complexity is that the CLR has to both keep track of the generic virtual function and the versions of it that it has JIT'ted.

Aldershot

Very elaborate answer, thanks. So it seems that there is really some runtime overhead for calling generic methods in comparison to non-generic methods, right? Interesting. – Ayesha

Yes, indeed it seems like virtual generic functions have significant overhead compared to normal virtual dispatch. Probably because generic virtual functions are rare. It could be optimized similarly to how interface calls are optimized (where the JIT compiler patches in "fast" checks for the virtual calls it has seen at any call site, specific to that call site). – Aldershot

Answer 2

I will call C++ templates and C# generics 'pattern code' in order to have a common term.

Pattern code at the point where it generates concrete code needs:

• a full description of the pattern (the source code of the pattern, or something similar)
• information about the pattern-arguments it is being instantiated on
• a compilation environment robust enough to combine the two

In C++, the pattern generates concrete code at the compilation unit level. We have the full compiler, the entire source code of the template, and the full type information of the template argument, so we shake and bake.

Traditional generics (non-reified) also generate concrete code at a similar spot, but they then allow runtime extension with new types. So runtime type erasure is used instead of the full type information of the type in question. Java apparently does only this to avoid needing new bytecode for generics (see above encoding).

Reified generics package the raw generic code up into some kind of representation that is strong enough to reapply the generic on a new type. At runtime, C# has a complete copy of the compiler, and the type added also carries with it basically full information about what it was compiled from. With all 3 parts, it can reapply the pattern on a new type.

C++ does not carry a compiler around, it does not store enough info about types or templates to apply at runtime. Some attempts have been made to delay template instantiation until link time in C++.

So your virtual generic method ends up compiling a new method when a new type is passed. At runtime.

Newsome

Yakk: Quite simple explanation, but I think it hits the nail's head. Thanks. – Ayesha

Answer 3

Both C++ templates and C# generics are features designed to implement the generic-programming paradigm: Write algorithms and data structores which doesn't depend on the type of the data they manipulate.

But they work on very different ways.

Generics work injecting type information on the code to be aviable at runtime. So the different algorithms/data structores know what types they are using, adapting themselves. Since the type information is aviable/accesible at runtime, that type decissions could be done at runtime and depend on runtime input. Thats why polymorphism (A runtime decission too) and C# generics work well together.

C++ templates, on the other hand, are a very different beast. They are a compile-time code generation system. That means what the template system does is to generate at compile-time different versions of the code depending on the types used. Even if this could achieve many powerfull things that generics doesn't (In fact the C++ template system is Turing Complete), the code-generation is done at compile-time, so we must know the types used at compile-time.
Since templates just generate different versions of the code for different types used, given a function template template<typename T> void foo( const T& t );, foo( 1 ) and foo( 'c' ) don't call the same function, they call the int and char generated versions respectively.

Thats why polymorphism cannot be used toghether with templates: Every function template instance its a distinct function, so making the template polymorphic has no sense. What version should call at runtime?.

Infra

Answer 4

C++ generally compiles straight to native code, and the native code for C.Foo<int>(int) and C.Foo<long>(long) may be different. Additionally, C++ generally stores pointers to native code in the vtable. Combine these, and you see that if C.Foo<T> is virtual, then a pointer to every instantiation needs to be part of the vtable.

C# does not have that problem. C# compiles to IL, and IL is JITted to native code. IL vtables don't contain pointers to native code, they contain pointers to IL (sort of). In addition to that, .NET generics don't allow specialisations. So at the IL level, C.Foo<int>(int) and C.Foo<long>(long) will always look exactly the same.

Therefore, the problem C++ has simply doesn't exist for C#, and isn't a problem that needed solving.

P.S.: The Java approach is actually used by the .NET runtime too. Often, generic methods will result in the exact same native code, regardless of the generic type argument, and in that case, there will only be one instance of that method. This is why you sometimes see references to System.__Canon in stack traces and such, it's a rough run-time equivalent of Java's ?.

Gorman

System.__Canon is a placeholder for reference types, because all reference types have the same size (pointer size). The same is not true for value types - each value type is JIT'ted to a different version, so this does not answer the question. – Aldershot

@Janiels That's just a P.S.. The rest of my answer does apply to any type. – Gorman

At the IL level this problem does not exist. But at the x86 level it does. – Iver

@Iver As I attempted to explain in my answer, the virtual method implementation exists mainly at the IL level, not at the machine code level. So no, the problem doesn't exist at the x86 level, because at that point, there aren't any virtual methods any longer. There may be function pointers used to implement virtual methods, but it's the job of the JITter to do this in such a way that the native code doesn't have to concern itself with the relevant details directly. – Gorman

I understand this question to be about implementation details. Looking at the disassembly of the example code it looks like the fact that the vcall is to a generic method did impact the generated code. – Iver

@Iver That example code in the question wasn't there when I answered, and when the OP added it, I didn't think my answer needed an update to address it. Evidently you do though :) I'll take a fresh look later, and maybe that fresh look will convince me too that I should expand my answer. – Gorman

@hvd: Your answer may be correct for all reference types, but for value types with different sizes, there have to be different versions. I.e., C.Foo<int>(int) and C.Foo<long>(long) will not be the same method. The disassembly in Janiels answer does support this claim. – Ayesha

@Ayesha At the IL level, they are the exact same method. At the IL level, virtual methods are resolved. So the fact that after the IL level, they are no longer the exact same method is simply not relevant. – Gorman

Answer 5

It's been a long time since I did C# things, before C# generics, so I do not know how C# implementations generally do things internally.

However, on the C++ side virtual templates are constrained by the design goal of translating each translation unit in isolation.

The following is a hypothetical example of virtual function template, that won't compile with current C++:

#include <iostream>
using namespace std;

struct Base
{
    template< int n >
    virtual void foo() { cout << "Base::foo<" << n << ">" << endl; }

    static auto instance() -> Base&;
};

auto main()
    -> int
{
    Base::instance().foo<666>();
}

//-------------------------------- Elsewhere:

struct Derived: Base
{
    template< int n >
    virtual void foo() { cout << "Derived::foo<" << n << ">" << endl; }
};

auto Base::instance() -> Base&
{
    static Derived o;
    return o;
}

Here's how it could be implemented manually:

#include <iostream>
#include <map>
#include <typeindex>
using namespace std;

struct Base
{
    virtual ~Base() {}

    template< int n >
    struct foo_pointer
    {
        void (*p)( Base* );
    };

    template< int n >
    using Foo_pointer_map = map<type_index, foo_pointer< n >>;

    template< int n >
    static
    auto foo_pointer_map()
        -> Foo_pointer_map< n >&
    {
        static Foo_pointer_map< n > the_map;
        return the_map;
    }

    template< int n >
    static
    void foo_impl( Base* ) { cout << "Base::foo<" << n << ">" << endl; }

    template< int n >
    void foo() {  foo_pointer_map< n >()[type_index( typeid( *this ) )].p( this ); }

    static auto instance() -> Base&;
};

bool const init_Base = []() -> bool
{
    Base::foo_pointer_map<666>()[type_index( typeid( Base ) )].p = &Base::foo_impl<666>;
    return true;
}();

auto main()
    -> int
{
    Base::instance().foo<666>();
}

//-------------------------------- Elsewhere:

struct Derived: Base
{
    template< int n >
    static
    void foo_impl( Base* ) { cout << "Derived::foo<" << n << ">" << endl; }
};

bool const init_Derived = []() -> bool
{
    // Here one must know about the instantiation of the base class function with n=666.
    Base::foo_pointer_map<666>()[type_index( typeid( Derived ) )].p = &Derived::foo_impl<666>;
    return true;
}();

auto Base::instance() -> Base&
{
    static Derived o;
    return o;
}

This code compiles and yields the result one would expect from the first code, but only by using knowledge about all instantiations of the template, instantiations that might be in different translation units.

At the point where the lookup tables are initialized this knowledge is generally not available.

Still, modern C++ compilers do provide whole program optimization with possibly code generation at link time, so it's probably not beyond current technology. I.e. not a technical impossibility, but rather an impracticality. Added to that there's the problem of dynamic libraries, which of course C++ doesn't support, but still part of practical reality of C++ programming.

Wagtail