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?

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.

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.