Runtime Representation of Generics — Part 2

this is an excerpt from chapter 5 (collections and generics) of pro .net performance , scheduled to appear in less than a month. i might be publishing a few more of these before and after the book is out.

after giving ample consideration to the design of java generics and c++ templates, we can understand better the implementation choice for clr generics. clr generics are implemented as follows. generic types — even open ones, like list<> — are first-class runtime citizens. there is a method table and an eeclass for each generic type and a system.type instance can be produced as well. generic types can be exported from assemblies and only a single definition of the generic type exists at compile-time. generic types are not expanded at compile-time, but as we have seen the compiler makes sure that any operation attempted on generic type parameter instances is compatible with the specified generic constraints.

when the clr needs to create an instance of a closed generic type, such as list<int> , it creates a method table and eeclass based on the open type. as always, the method table contains method pointers, which are compiled on the fly by the jit compiler. however, there is a crucial optimization here: compiled method bodies on closed generic types that have reference type parameters can be shared . to digest this, let’s consider the list<t>.add method and try to compile it to x86 instructions when t is a reference type:

//c# code:
public void add(t item) {
  if (size < items.length – 1) {
    items[size] = item;
    ++size;
  } else {
    allocateandaddslow(item);
  }
} 

; x86 assembly when t is a reference type
; assuming that ecx contains ‘this’ and edx contains
; ‘item’, prologue and epilogue omitted
mov eax, dword ptr [ecx+4]       ; items
mov eax, dword ptr [eax+4]       ; items.length
dec eax
cmp dword ptr [ecx+8], eax       ; size < items.length – 1
jge allocateandaddslow
mov eax, dword ptr [ecx+4]
mov ebx, dword ptr [ecx+8]
mov dword ptr [eax+4*ebx+4], edx ; items[size] = item
inc dword ptr [eax+8]            ; ++size

it’s clear that the method’s code does not depend on t in any way, and will work exactly as well for any reference type. this observation allows the jit compiler to conserve resources (time and memory) and share the method table pointers for list<t>.add in all method tables where t is a reference type.

(this idea requires some further refinement, which we will not carry out. for example, if the method’s body contained a new t[10] expression, it would require a separate code path for each t , or at least a way of obtaining t at runtime (through an additional hidden parameter passed to the method). additionally, we haven’t considered how constraints affect the code generation — but you should be convinced by now that invoking interface methods or virtual methods through base classes requires the same code regardless of the type.)

the same idea does not work for value types. for example, when t is long, the assignment statement items[size] = item requires a different instruction, because 8 bytes must be copied instead of 4. even larger value types may even require more than one instruction; and so on.

to demonstrate this in a simple setting, we can inspect using sos the method tables of closed generic types that are all realizations of the same open generic type. for example, consider a basicstack<t> class with only push and pop methods, as follows:

class basicstack<t> {
  private t[] items;
  private int topindex;
  public basicstack(int capacity = 42) {
    items = new t[capacity];
  }
  public void push(t item) {
    items[topindex++] = item;
  }
  public t pop() {
    return items[--topindex];
  }
}

the method tables for basicstack<string> , basicstack<int[]> , basicstack<int> , and basicstack<double> are listed below. note that the method table entries (i.e. code addresses) for the closed types with a reference type generic type argument are shared, and for the value types are not:

0:004> !dumpheap –stat
...
00173b40 1 16 basicstack`1[[system.double, mscorlib]]
00173a98 1 16 basicstack`1[[system.int32, mscorlib]]
00173a04 1 16 basicstack`1[[system.int32[], mscorlib]]
001739b0 1 16 basicstack`1[[system.string, mscorlib]]
...

0:004> !dumpmt -md 001739b0
eeclass: 001714e0
module: 00172e7c
name: basicstack`1[[system.string, mscorlib]]
...
00260360 00173924 jit basicstack`1[[system.__canon, mscorlib]].push(system.__canon)
00260390 0017392c jit basicstack`1[[system.__canon, mscorlib]].pop()

0:004> !dumpmt -md 00173a04
eeclass: 001714e0
module: 00172e7c
name: basicstack`1[[system.int32[], mscorlib]]
...
00260360 00173924 jit basicstack`1[[system.__canon, mscorlib]].push(system.__canon)
00260390 0017392c jit basicstack`1[[system.__canon, mscorlib]].pop()

0:004> !dumpmt -md 00173a98
eeclass: 0017158c
module: 00172e7c
name: basicstack`1[[system.int32, mscorlib]]
...
002603c0 00173a7c jit basicstack`1[[system.int32, mscorlib]].push(int32)
002603f0 00173a84 jit basicstack`1[[system.int32, mscorlib]].pop()

0:004> !dumpmt -md 00173b40
eeclass: 001715ec
module: 00172e7c
name: basicstack`1[[system.double, mscorlib]]
...
00260420 00173b24 jit basicstack`1[[system.double, mscorlib]].push(double)
00260458 00173b2c jit basicstack`1[[system.double, mscorlib]].pop()

finally, if we inspect the actual method bodies, it becomes evident that the reference type versions do not depend at all on the actual type (all they do is move references around), and the value type versions do depend on the type. copying an integer, after all, is different from copying a double floating-point number. below are the disassembled versions of the push method, with the line that actually moves the data around highlighted:

0:004> !u 00260360
normal jit generated code
basicstack`1[[system.__canon, mscorlib]].push(system.__canon)
00260360 57 push edi
00260361 56 push esi
00260362 8b7104 mov esi,dword ptr [ecx+4]
00260365 8b7908 mov edi,dword ptr [ecx+8]
00260368 8d4701 lea eax,[edi+1]
0026036b 894108 mov dword ptr [ecx+8],eax
0026036e 52 push edx
0026036f 8bce mov ecx,esi
00260371 8bd7 mov edx,edi
00260373 e8f4cb3870 call clr!jit_stelem_ref (705ecf6c)
00260378 5e pop esi
00260379 5f pop edi
0026037a c3 ret

0:004> !u 002603c0
normal jit generated code
basicstack`1[[system.int32, mscorlib]].push(int32)
002603c0 57 push edi
002603c1 56 push esi
002603c2 8b7104 mov esi,dword ptr [ecx+4]
002603c5 8b7908 mov edi,dword ptr [ecx+8]
002603c8 8d4701 lea eax,[edi+1]
002603cb 894108 mov dword ptr [ecx+8],eax
002603ce 3b7e04 cmp edi,dword ptr [esi+4]
002603d1 7307 jae 002603da
002603d3 8954be08 mov dword ptr [esi+edi*4+8],edx
002603d7 5e pop esi
002603d8 5f pop edi
002603d9 c3 ret
002603da e877446170 call clr!jit_rngchkfail (70874856)
002603df cc int 3

0:004> !u 00260420
normal jit generated code
basicstack`1[[system.double, mscorlib]].push(double)
00260420 56 push esi
00260421 8b5104 mov edx,dword ptr [ecx+4]
00260424 8b7108 mov esi,dword ptr [ecx+8]
00260427 8d4601 lea eax,[esi+1]
0026042a 894108 mov dword ptr [ecx+8],eax
0026042d 3b7204 cmp esi,dword ptr [edx+4]
00260430 730c jae 0026043e
00260432 dd442408 fld qword ptr [esp+8]
00260436 dd5cf208 fstp qword ptr [edx+esi*8+8]
0026043a 5e pop esi
0026043b c20800 ret 8
0026043e e813446170 call clr!jit_rngchkfail (70874856)
00260443 cc int 3

we have already seen that the .net generics implementation is fully type-safe at compile-time. it only remains to ascertain that there is no boxing cost incurred when using value types with generic collections. indeed, because the jit compiler compiles a separate method body for each closed generic type where the generic type arguments are value types, there is no need for boxing.

to summarize, .net generics offer significant advantages when contrasted with java generics or c++ templates. the generic constraints mechanism is somewhat limited compared to the wild west that c++ affords, but the flexibility gains from sharing generic types across assemblies and the performance benefits from generating code on demand (and sharing it) are overwhelming.