Generics under the hood
and a JITter bug for dessert
Overview
- Compare with JAVA and C++
- Find out .NET is awesome
- Recall memory layout
- Look under the hood
- Analyze the performance degradation
- Discuss some interesting things
JAVA and swear words
“Šuo ir kariamas pripranta.”
Lithuanian proverbs
Generics in .NET
Well known benefits
- Reduce code duplication
- Constraints & variance
- Performance improvements (no boxing, no casting)
- Compile-time checks
.NET memory layout
var o = new object();
Instance on heap:
| Sync block address |
| Method table address |
| Field1 |
| FieldN |
Method Table structure
- The central data structure of the runtime
- "Hot" data
| EEClass address |
| Interface Map Table address |
| Inherited Virtual Method addresses |
| Introduced Virtual Method addresses |
| Instance Method addresses |
| Static Method addresses |
| Static Fields values |
| InterfaceN method addresses |
EEClass structure
- Everything about the type
- Data needed by type loading, JITing or reflection
- "Cold" data
- Too complex: contains EEClassOptionalFields, EEClassPackedFields
WinDbg the Great and Powerful
SOS / Son of Strike
SOSEX / SOS extensions
An example class:
public class MyClass
{
private int _myField;
public int MyMethod()
{
return _myField;
}
}
An instance:
var myClass = new MyClass();
Method Table looks like:
EEClass looks like:
Links:
HOWTO: Debugging .NET with WinDbg
Book: "Pro .NET Performance" by Sasha Goldshtein, Dima Zurbalev, Ido Flatow
Generics memory layout
An example class:
public class MyGenericClass<T>
{
private T _myField;
public T MyMethod()
{
return _myField;
}
}
Compiles to:
Miracle! CLR knows about Generics
An instance:
var myObject = new MyGenericClass<object>();
Method table:
EEClass:
An instance:
var myString = new MyGenericClass<string>();
Method table:
An instance:
var myInt = new MyGenericClass<int>();
Method table:
EEClass:
Under the hood
- Value types don't share anything
- Reference types share code and EEClass
- System.__Canon - an internal type
- System.__Canon - will be replaced
Optimizations by CLR
- Class loader - 30x
- Type hierarchy walk with global dictionary cache lookup - 6x
- Global dictionary cache lookup - 3x
- Method Table slot - 1x
Note: Optimizes the generic calls in your method not your generic method
Links:
Design and Implementation of Generics for the .NET Common Language Runtime
Dessert
Simplified version:
Benchmark:
public class Program
{
public static void Main()
{
Measure(new DerivedClass());
Measure(new BaseClass<object>());
}
private static void Measure(BaseClass<object>> baseClass)
{
var sw = Stopwatch.StartNew();
baseClass.Run();
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
}
}
Workaround:
"Just add two methods"
public class BaseClass<T>
{
...
public void Method1()
{
}
public void Method2()
{
}
...
}
Wat?
The fix
The pull request on github
Moral:
Links:
Interesting things
Heuristic algorithm
DWORD numMethodsAdjusted =
(bmtMethod->dwNumDeclaredNonAbstractMethods == 0)
? 0
: (bmtMethod->dwNumDeclaredNonAbstractMethods < 3)
? 3
: bmtMethod->dwNumDeclaredNonAbstractMethods;
DWORD nTypeFactorBy2 = (bmtGenerics->GetNumGenericArgs() == 1)
? 2
: 3;
DWORD estNumTypeSlots = (numMethodsAdjusted * nTypeFactorBy2 + 2) / 3;
Dictionary lookup
CORINFO_GENERIC_HANDLE
JIT_GenericHandleWorker(
MethodDesc * pMD,
MethodTable * pMT,
LPVOID signature)
{
CONTRACTL {
THROWS;
GC_TRIGGERS;
} CONTRACTL_END;
MethodTable * pDeclaringMT = NULL;
if (pMT != NULL)
{
SigPointer ptr((PCCOR_SIGNATURE)signature);
ULONG kind; // DictionaryEntryKind
IfFailThrow(ptr.GetData(&kind));
// We need to normalize the class passed in (if any) for reliability purposes. That's because preparation of a code region that
// contains these handle lookups depends on being able to predict exactly which lookups are required (so we can pre-cache the
// answers and remove any possibility of failure at runtime). This is hard to do if the lookup (in this case the lookup of the
// dictionary overflow cache) is keyed off the somewhat arbitrary type of the instance on which the call is made (we'd need to
// prepare for every possible derived type of the type containing the method). So instead we have to locate the exactly
// instantiated (non-shared) super-type of the class passed in.
ULONG dictionaryIndex = 0;
IfFailThrow(ptr.GetData(&dictionaryIndex));
pDeclaringMT = pMT;
for (;;)
{
MethodTable * pParentMT = pDeclaringMT->GetParentMethodTable();
if (pParentMT->GetNumDicts() <= dictionaryIndex)
break;
pDeclaringMT = pParentMT;
}
if (pDeclaringMT != pMT)
{
JitGenericHandleCacheKey key((CORINFO_CLASS_HANDLE)pDeclaringMT, NULL, signature);
HashDatum res;
if (g_pJitGenericHandleCache->GetValue(&key,&res))
{
// Add the denormalized key for faster lookup next time. This is not a critical entry - no need
// to specify appdomain affinity.
JitGenericHandleCacheKey denormKey((CORINFO_CLASS_HANDLE)pMT, NULL, signature);
AddToGenericHandleCache(&denormKey, res);
return (CORINFO_GENERIC_HANDLE) (DictionaryEntry) res;
}
}
}
DictionaryEntry * pSlot;
CORINFO_GENERIC_HANDLE result = (CORINFO_GENERIC_HANDLE)Dictionary::PopulateEntry(pMD, pDeclaringMT, signature, FALSE, &pSlot);
if (pSlot == NULL)
{
// If we've overflowed the dictionary write the result to the cache.
BaseDomain *pDictDomain = NULL;
if (pMT != NULL)
{
pDictDomain = pDeclaringMT->GetDomain();
}
else
{
pDictDomain = pMD->GetDomain();
}
// Add the normalized key (pDeclaringMT) here so that future lookups of any
// inherited types are faster next time rather than just just for this specific pMT.
JitGenericHandleCacheKey key((CORINFO_CLASS_HANDLE)pDeclaringMT, (CORINFO_METHOD_HANDLE)pMD, signature, pDictDomain);
AddToGenericHandleCache(&key, (HashDatum)result);
}
return result;
}
TODO
Generic method:
public class MyClassWithGenericMethod
{
public T MyGenericMethod<T>(T arg)
{
return arg;
}
}
Generic struct:
public struct MyGenericStruct<T>
{
private T _myField;
public T MyMethod()
{
return _myField;
}
}