CLR Generics and code sharing

It’s been a while since I’ve posted - we’ve been busy getting Beta 2 ready, and that means fixing bugs, bugs, and more bugs. I have a bunch of nearly complete posts, mostly around Reflection and type system identity, which I’ll be kicking out soon I hope. Lately, I’ve received a few questions around code sharing on generic methods. I figured this would be as good a forum as any to drill down on some of the details. This post is a bit all over the place, so please post any questions you have below!

 

First up - the high level bits for generics and code sharing:

 

- We do a mix and match of code sharing and specialization, depending what type arguments we’re dealing with.

- Generic method instantiation code sharing is done for reference type arguments.

- Generic method specialization is always done for primitives and valuetypes, including enums.

What is code sharing again?

 

In the case of generics, code sharing is when two or more “compatible” method instantiations point to the same x86 code. An example of this is Foo.M<MyClass1> and Foo.M<MyClass2> sharing the same generated x86, where MyClass1 and MyClass2 are ref types.

Brief history – we also code share for the arrays of reference types in v1.0 and v1.1 (we just use the code for object array).

 

Very quick recap of EE data structures

 

There’s excellent explanation’s on the CLR’s execution engine data structures in the SSCLI Essentials book. A quick recap though:

 

All objects on the heap have a fixed size pointer that points to a MethodTable, which describes the objects type identity (you get essentially get a managed code representation through RuntimeTypeHandle). MethodTable’s contain pointers to EE structures, and more importantly, a list of the type’s methods and their representative code pointers. These pointers can either be pointing at x86 code, or the JIT stub (which invokes the JIT if a method has not been JIT’ed yet). MethodTable’s are used extensively for type identity.

 

MethodDesc’s are small structures used to describe methods. Each method has a representative MethodDesc structure, although it’s not typically used by the runtime unless you’re trying to do bind to methods late-bound (reflection). There are different types of MethodDesc’s in the runtime, but for the purpose of this post, we just assume they’re all basically the same.

 

Calls on a instance method conceptually look something like this: start with the this pointer, hit the MethodTable, index to the code pointer of the method, then call the code pointer, passing the “this” address as an argument as per x86 calling convention. Calls on static methods do essentially the same thing, just without the “this” pointer being passed as an argument. Of course, the JIT can generate code for direct calls to these various pointers – it does the heavy lifting of MethodTable lookups for code pointers at JIT time.

 

Generic Methods in IL

 

When we introduce generics in to the picture, we have this potential unknown – when we JIT compile, what do we do with locals/arguments of T? How do we generate x86 for something like that?

 

Let’s consider the following code snippet:

 

class Foo

{

      [MethodImpl(MethodImplOptions.NoInlining)]

      public void M1<T>()

      {

            Console.WriteLine(typeof(T));

      }

}

Foo f1 = new Foo().M1<string>();

Foo f2 = new Foo().M1<object>();

How do we represent the code in M1<T> in IL when we don’t know what T will be? We actually specify the type parameter as “!!arity”, where arity is the index in to the type parameters on the generic method (0 being the first, 1 being the second etc).

 

The Foo.M1<T>() IL code looks like the following:

 

// IL Code for Foo.M1<T>

.method public hidebysig instance void M1<([mscorlib]System.Object) T>() cil managed noinlining

{

  // Code size 17 (0x11)

  .maxstack 8

  IL_0000: ldtoken !!0

  IL_0005: call class [mscorlib]System.Type [mscorlib]System.Type::GetTypeFromHandle(valuetype [mscorlib]System.RuntimeTypeHandle)

  IL_000a: call void [mscorlib]System.Console::WriteLine(object)

  IL_000f: nop

  IL_0010: ret

} // end of method Foo::M1

We make no assumptions about the type that the method will be passed. You can imagine, in the abstract machine world, that calling this method, we would simply replace the !!0 with string or object, depending what was passed in as the generic argument. This imaginary scenario is close to what actually happens when we JIT compile this piece of code.

 

Enter: generic methods and code sharing

Looking at the code, I have two instances of the same type Foo, calling essentially different methods (ie: M1<object> is not the same as M1<string>, which is also exposed and represented via reflection). Code sharing steps in, these two method instantiations end up pointing to the same x86 code.

 

It happens like this: When we hit this piece of code: Foo f1 = new Foo().M1<string>(), kick the JIT to go compile the method for the first time. We take the IL above, and in a basic sense, replace !!0 with a pointer that calls in to the runtime to get the type information about the type we passed as generic argument in slot 0. Where do we get this pointer from? Well, the magic comes from the calling convention: we supply a “hidden” argument in the call, which is a pointer in to a runtime data structure that supplies us with that information.

 

Bring in the “hidden” argument data structure

 

A pointer to what? Well, in this specific instance where we only need to know about the type argument supplied to the generic method, we create and pass in a MethodDesc pointer for that particular declaration of the method. For the Foo().M1<string> case we pass in a MethodDesc that describes the method as M1<string>, for Foo().M1<object>, we pass in the MethodDesc for M1<object>. The MethodDesc essentially contains all the information needed to describe what !!0 will be. The JIT compiles x86 code to pull the type information out of the MethodDesc pointer.

 

So, for the case above, the JIT hits the “ldtoken !!0”, and compiles x86 code to retrieve the type token from the hidden argument pointer which was passed in. This code works for both the string and object case, because we’re hitting a pointer indirection, not a specific piece of code for string or object.

 

Cases where we need this “hidden” argument

 

We generally need this hidden argument for cases where we can’t derive the type information from any means available at x86 execution time in the current stack frame. Below lists a few examples, along with the data structure the hidden argument represents

 

1. Foo<T> static M()                   == TypeHandle
2. Foo<T> static M<T>               == MethodDesc
3. Foo M<T>                               == MethodDesc
4. Foo static M<T>                      == MethodDesc

Number 4 is an interesting one – we actually need both the TypeHandle and the MethodDesc, but the JIT knows that we can generate code to get at the TypeHandle _from_ the MethodDesc (there’s an indirection there, which I think is described in SSCLI Essentials).

 

One case that’s not pointed out is Foo<T> M(). Because M is an instance method, and we already pass in the “this” pointer as per the calling convention, we can derive the type argument of type argument T, directly from the “this” pointer.

 

For those that ask the question – why pass in the MethodDesc/TypeHandle, why can’t we just pass in the type handle as a “hidden argument”. Good question, but for the case where we have more than one generic parameter, it makes sense to minimize the amount of arguments passed in at calling convention time. M<U,W,Z> for example, is fully described by the MethodDesc, so its easier and more efficient to pass in just the MD pointer and generate code to index in to the MethodDesc appropriately.

 

Okay, so why the lack of code sharing on primitives and value types?

 

While technically, we could code share on primitives and value types, it’s clearly not very efficient to do so. Just to make it more understandable:

 

Consider:

Foo { M<T>() {} }

 

new Foo().M<int>();

new Foo().M<double>();

 

The JIT will actually go off and generate two separate code sections for both of those instantiations. Why? Well, primitives and valuetypes live on the stack and have no reference to a MethodTable (unless they’re boxed). Generally, different valuetypes/primitives have different data sizes, int and double being a good example of that. The JIT clearly can’t generate x86 code that deals with unknown data sizes, so it specializes them.

 

The runtime could have made these primitive/valuetype guys play well with code sharing by boxing every time we call, but isn’t preventing unnecessary boxing one of the best reasons around for using generics?

 

Partial specialization

 

I’m not exactly sure if we the CLR team calls it partial specialization, but that’s what I’ll call it for this blog post <g>. For cases where we have a valuetype and a ref type, we specialize for the valuetype case, and link the sharable code for the ref type.

 

Foo<int>.M<string> and Foo<int>.M<object> are essentially the same code. We share M<T> in the context of Foo<int>.

 

More resources

 

Some of this is fairly dense; the blog posts intention is for Google to pick some of this up, so I can remember how it works. If you want to know more detail about this, check out the following:

 

https://research.microsoft.com/projects/clrgen/

https://research.microsoft.com/projects/clrgen/generics.pdf

https://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnvs05/html/csharp_generics.asp

 

The book I mention: Shared Source CLI Essentials, 2003, ISBN: 059600351X

 

That’s all for now – hopefully I’ll have more time in the coming weeks to jot down some more random brain dump stuff from inside the guts of the CLR.

Comments

• Anonymous
  November 17, 2004
  Tanks for the informative post!
  
  One little nitpick: Qoute: "Generally, different valuetypes/primitives have different data sizes, int and float being a good example of that."
  
  Eh, actually, both are 4 bytes, aren't they? So, this is a good example that different value types actually can have the same size. I can imagine however that the JIT wants to generate code involving FPU registers and instructions for the 'float' though...
• Anonymous
  November 18, 2004
  Yep, good catch. Updated the post appropriately.
  Thanks
• Anonymous
  November 20, 2004
  Good stuff :-) Do you know if this is the way it will work (internally) on the CF CLR as well?
• Anonymous
  November 21, 2004
  Does it mean that Generics unable to use inling for sealed classes and short methods ?
• Anonymous
  November 21, 2004
  "but isn’t preventing unnecessary boxing one of the best reasons around for using generics?"
  
  This is a good example of keeping your eye on the ball. I've seen dev teams make some decisions that go against their primary design goals. It is easy sometimes to get caught up in implementation and forget why you are doing a piece software in the first place.
  
• Anonymous
  November 21, 2004
  The inner workings of generics
• Anonymous
  December 01, 2004
  The comment has been removed
• Anonymous
  December 02, 2004
  The comment has been removed
• Anonymous
  December 02, 2004
  Thanks so much and just in time for my generics presentatiuon!
• Anonymous
  December 27, 2004
  [http://itpeixun.51.net/][http://aissl.51.net/][http://kukuxz003.freewebpage.org/][http://kukuxz001.51.net/][http://kukuxz003.51.net/][http://kukuxz005.51.net/][http://kukuxz002.51.net/][http://kukuxz004.freewebpage.org/][http://kukuxz007.51.net/][http://kukuxz001.freewebpage.org/][http://kukuxz006.51.net/][http://kukuxz002.freewebpage.org/][http://kukuxz004.51.net/][http://kukuxz008.51.net/][http://kukuxz009.51.net/][http://kukuxz005.freewebpage.org/][http://kukuxz006.freewebpage.org/][http://kukuxz007.freewebpage.org/][http://kukuxz009.freewebpage.org/]
• Anonymous
  July 04, 2005
  In Whidbey, apart from the token handle resolution APIs I mentioned earlier, there are some more overloads...
• Anonymous
  July 04, 2005
  In Whidbey, apart from the token handle resolution APIs I mentioned earlier, there are some overloads...
• Anonymous
  July 05, 2005
  In Whidbey, apart from the token handle resolution APIs I mentioned earlier, there are some overloads...
• Anonymous
  July 05, 2005
  In Whidbey, apart from the token handle resolution APIs I mentioned earlier, there are some overloads...
• Anonymous
  July 05, 2005
  In Whidbey, apart from the token handle resolution APIs I mentioned earlier, there are some overloads...
• Anonymous
  August 12, 2005
  I've heard several different opinions about how the debugger should display a generic method in the callstack....
• Anonymous
  November 28, 2007
  PingBack from http://feeds.maxblog.eu/item_1328757.html