This post first appearedon my blog

Generics in C# are certainly very useful and I find it amazing thatwe almost didn't get them:

What would the cost of inaction have been? What would the cost of failure have been? No generics in C# 2.0? No LINQ in C# 3.0? No TPL in C# 4.0? No Async in C# 5.0? No F#? Ultimately, an erasure model of generics would have been adopted, as for Java, since the CLR team would never have pursued a in-the-VM generics design without external help.

So a big thanks is due toDon Syme and the rest of the team at Microsoft Research in Cambridge!

But as well as being useful, I also find some usages of generics mind-bending, for instance I'm still not sure what this codeactually means or how to explain it in words:

classBlah<T>whereT:Blah<T>

As always, reading an Eric Lippert posthelps a lot, but even he recommends against using this specific 'circular' pattern.

Recently I spoke at theCORESTART 2.0 conference in Prague, giving a talk on'Microsoft and Open-Source – A 'Brave New World'. Whilst I was there I met the very knowledgeableJiri Cincura, who blogs attabs ↹ over ␣ ␣ ␣ spaces. He was giving a great talk on 'C# 7.1 and 7.2 features', but also shared with me an excellent code snippet that he called 'Crazy Class':

classClass<A,B,C,D,E,F>{classInner:Class<Inner,Inner,Inner,Inner,Inner,Inner>{Inner.Inner.Inner.Inner.Inner.Inner.Inner.Inner.Innerinner;}}

He said:

this is the class that takes crazy amount of time to compile. You can add moreInner.Inner.Inner... to make it even longer (and also generic parameters).

After a big of digging around I found that someone else had noticed this, see the StackOverflow questionWhy does field declaration with duplicated nested type in generic class results in huge source code increase? Helpfully the 'accepted answer' explains what is going on:

When you combine these two, the way you have done, something interesting happens. The typeOuter<T>.Inner is not the same type asOuter<T>.Inner.Inner.Outer<T>.Inner is a subclass ofOuter<Outer<T>.Inner> whileOuter<T>.Inner.Inner is a subclass ofOuter<Outer<Outer<T>.Inner>.Inner>, which we established before as being different fromOuter<T>.Inner. SoOuter<T>.Inner.Inner andOuter<T>.Innerare referring to different types.

When generating IL, the compiler always uses fully qualified names for types. You have cleverly found a way to refer to types with names whose lengths that grow atexponential rates. That is why as you increase the generic arity ofOuter or add additional levels.Y to the fieldfield inInner the output IL size and compile time grow so quickly.

Clear? Good!!

You probably have to be Jon Skeet, Eric Lippert or a member of theC# Language Design Team (yay, 'Matt Warren') to really understand what's going on here, but that doesn't stop the rest of us having fun with the code!!

I can't think of any reason why you'd actually want to write code like this, so please don't!! (or at least if you do, don't blame me!!)

For a simple idea of what's actually happening, lets take this code (with only 2 'Levels'):

classClass<A,B,C,D,E,F>{classInner:Class<Inner,Inner,Inner,Inner,Inner,Inner>{Inner.Innerinner;}}

The 'decompiled' version actually looks like this:

internalclassClass<A,B,C,D,E,F>{privateclassInner:Class<Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner>{privateClass<Class<Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner>.Inner,Class<Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner>.Inner,Class<Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner>.Inner,Class<Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner>.Inner,Class<Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner>.Inner,Class<Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner,Class<A,B,C,D,E,F>.Inner>.Inner>.Innerinner;}}

Wow, no wonder things go wrong quickly!!

Exponential Growth

Firstly let's check the claim ofexponential growth, if you don't remember yourBig O notation you can also think of this asO(very, very bad)!!

To test this out, I'm going to compile the code above, but vary the 'level' each time by adding a new.Inner, so 'Level 5' looks like this:

Inner.Inner.Inner.Inner.Innerinner;

'Level 6' like this, and so on

Inner.Inner.Inner.Inner.Inner.Innerinner;

We then get the following results:

If we look at these results in graphical form, it's very obvious what's going on

(the dotted lines are a 'best fit' trend-line and they are exponential)

If I compile the code withdotnet build (version 2.0.0), things go really wrong at 'Level 10' and the compiler throws an error (full stack trace):

System.ArgumentOutOfRangeException:Specifiedargumentwasoutoftherangeofvalidvalues.

Which looks similar toInternal compiler error when creating Portable PDB files #3866.

However your mileage may vary, when I ran the code in Visual Studio 2015 it threw anOutOfMemoryException instead and then promptly restarted itself!! I assume this is becauseVS is a 32-bit application and it runs out of memory before it can go really wrong!

Profiling the Compiler

Finally, I want to look at just where the compiler is spending all it's time. From the results above we saw that it was takingover 3 minutes to compile a simple program, with a peak memory usage of2.14 GB, so what was it actually doing??

Well clearly there's lots ofTypes involved and the Compiler seems happy for you to write this code, so I guess it needs to figure it all out. Once it's done that, it then needs to write all thisType metadata out to a .dll or .exe, which can be100's of MB in size.

At a high-level the profiling summary produce by VS looks like this (click for full-size image):

However if we take a bit of a close look, we can see the 'hot-path' is inside theSerializeTypeReference(..) method inCompilers/Core/Portable/PEWriter/MetadataWriter.cs

Summary

I'm a bit torn about this, it is clearly an 'abuse' of generics!!

In some ways I think that itshouldn't be fixed, it seems better that the compiler encourages you tonot write code like this, rather than making is possible!!

So if it takes 3 mins to compile your code, allocates 2GB of memory and then crashes, take that as a warning!!