title: Instantiation of recursive generic types slows down exponentially the deeper they are nested. Why?
body: <blockquote>
    <p><em><strong>Note:</strong> I may have chosen the wrong word in the title; perhaps I'm really talking about</em> polynomial <em>growth here. See the benchmark result at the end of this question.</em></p>
  </blockquote>
  
  <p>Let's start with these three recursive generic interfaces<sup><strong>&dagger;</strong></sup> that represent immutable stacks:</p>
  
  <pre class="lang-cs prettyprint-override"><code>interface IStack&lt;T&gt;
  {
      INonEmptyStack&lt;T, IStack&lt;T&gt;&gt; Push(T x);
  }
  
  interface IEmptyStack&lt;T&gt; : IStack&lt;T&gt;
  {
      new INonEmptyStack&lt;T, IEmptyStack&lt;T&gt;&gt; Push(T x);
  }
  
  interface INonEmptyStack&lt;T, out TStackBeneath&gt; : IStack&lt;T&gt;
      where TStackBeneath : IStack&lt;T&gt;
  {
      T Top { get; }
      TStackBeneath Pop();
      new INonEmptyStack&lt;T, INonEmptyStack&lt;T, TStackBeneath&gt;&gt; Push(T x);
  }
  </code></pre>
  
  <p>I've created straightforward implementations <code>EmptyStack&lt;T&gt;</code>, <code>NonEmptyStack&lt;T,TStackBeneath&gt;</code>.</p>
  
  <blockquote>
    <p><em><strong>Update #1:</strong> See the code below.</em></p>
  </blockquote>
  
  <p>I've noticed the following things about their runtime performance: </p>
  
  <ul>
  <li>Pushing 1,000 items onto an <code>EmptyStack&lt;int&gt;</code> for the first time takes more than 7 seconds.</li>
  <li>Pushing 1,000 items onto an <code>EmptyStack&lt;int&gt;</code> takes virtually no time at all afterwards.</li>
  <li>Performance gets exponentially worse the more items I push onto the stack.</li>
  </ul>
  
  <blockquote>
    <p><em><strong>Update #2:</strong></em></p>
    
    <ul>
    <li><p><em>I've finally performed a more precise measurement. See the benchmark code and results below.</em></p></li>
    <li><p><em>I've only discovered during these tests that .NET 3.5 doesn't seem to allow generic types with a recursion depth &ge; 100. .NET 4 doesn't seem to have this restriction.</em></p></li>
    </ul>
  </blockquote>
  
  <p>The first two facts make me suspect that the slow performance is not due to my implementation, but rather to the type system: .NET has to instantiate 1,000 distinct closed generic <em>types</em>, ie.:</p>
  
  <ul>
  <li><code>EmptyStack&lt;int&gt;</code></li>
  <li><code>NonEmptyStack&lt;int, EmptyStack&lt;int&gt;&gt;</code></li>
  <li><code>NonEmptyStack&lt;int, NonEmptyStack&lt;int, EmptyStack&lt;int&gt;&gt;&gt;</code></li>
  <li><code>NonEmptyStack&lt;int, NonEmptyStack&lt;int, NonEmptyStack&lt;int, EmptyStack&lt;int&gt;&gt;&gt;&gt;</code></li>
  <li>etc.</li>
  </ul>
  
  <p><strong>Questions:</strong></p>
  
  <ol>
  <li>Is my above assessment correct?</li>
  <li>If so, why does instantiation of generic types such as <code>T&lt;U&gt;</code>, <code>T&lt;T&lt;U&gt;&gt;</code>, <code>T&lt;T&lt;T&lt;U&gt;&gt;&gt;</code>, and so on get <em>exponentially</em> slower the deeper they are nested? </li>
  <li>Are CLR implementations other than .NET (Mono, Silverlight, .NET Compact etc.) known to exhibit the same characteristics?</li>
  </ol>
  
  <hr>
  
  <blockquote>
    <p><em><sup><strong>&dagger;</strong>)</sup> Off-topic footnote: These types are quite interesting btw. because they allow the compiler to catch certain errors such as:</em></p>
    
    <pre class="lang-cs prettyprint-override"><code>stack.Push(item).Pop().Pop();
  //                    ^^^^^^
  // causes compile-time error if 'stack' is not known to be non-empty.
  </code></pre>
    
    <p><em>Or you can express requirements for certain stack operations:</em></p>
  
  <pre><code>TStackBeneath PopTwoItems&lt;T, TStackBeneath&gt;
                (INonEmptyStack&lt;T, INonEmptyStack&lt;T, TStackBeneath&gt; stack)
  </code></pre>
  </blockquote>
  
  <hr>
  
  <h2>Update #1: Implementation of the above interfaces</h2>
  
  <pre><code>internal class EmptyStack&lt;T&gt; : IEmptyStack&lt;T&gt;
  {
      public INonEmptyStack&lt;T, IEmptyStack&lt;T&gt;&gt; Push(T x)
      {
          return new NonEmptyStack&lt;T, IEmptyStack&lt;T&gt;&gt;(x, this);
      }
  
      INonEmptyStack&lt;T, IStack&lt;T&gt;&gt; IStack&lt;T&gt;.Push(T x)
      {
          return Push(x);
      }
  }
  // ^ this could be made into a singleton per type T
  
  internal class NonEmptyStack&lt;T, TStackBeneath&gt; : INonEmptyStack&lt;T, TStackBeneath&gt;
      where TStackBeneath : IStack&lt;T&gt;
  {
      private readonly T top;
      private readonly TStackBeneath stackBeneathTop;
  
      public NonEmptyStack(T top, TStackBeneath stackBeneathTop)
      {
          this.top = top;
          this.stackBeneathTop = stackBeneathTop;
      }
  
      public T Top { get { return top; } }
  
      public TStackBeneath Pop()
      {
          return stackBeneathTop;
      }
  
      public INonEmptyStack&lt;T, INonEmptyStack&lt;T, TStackBeneath&gt;&gt; Push(T x)
      {
          return new NonEmptyStack&lt;T, INonEmptyStack&lt;T, TStackBeneath&gt;&gt;(x, this);
      }
  
      INonEmptyStack&lt;T, IStack&lt;T&gt;&gt; IStack&lt;T&gt;.Push(T x)
      {
          return Push(x);
      }
  }
  </code></pre>
  
  <hr>
  
  <h2>Update #2: Benchmark code and results</h2>
  
  <p>I used the following code to measure recursive generic type instantiation times for .NET 4 on a Windows 7 SP 1 x64 (Intel U4100 @ 1.3 GHz, 4 GB RAM) notebook. This is a different, faster machine than the one I originally used, so the results do not match with the statements above.</p>
  
  <pre><code>Console.WriteLine("N, t [ms]");
  int outerN = 0;
  while (true)
  {
      outerN++;
      var appDomain = AppDomain.CreateDomain(outerN.ToString());
      appDomain.SetData("n", outerN);
      appDomain.DoCallBack(delegate {
          int n = (int)AppDomain.CurrentDomain.GetData("n");
          var stopwatch = new Stopwatch();
          stopwatch.Start();
          IStack&lt;int&gt; s = new EmptyStack&lt;int&gt;();
          for (int i = 0; i &lt; n; ++i)
          {
              s = s.Push(i);  // &lt;-- this "creates" a new type
          }
          stopwatch.Stop();
          long ms = stopwatch.ElapsedMilliseconds;
          Console.WriteLine("{0}, {1}", n, ms);
      });
      AppDomain.Unload(appDomain);
  }
  </code></pre>
  
  <p>(Each measurement is taken in a separate app domain because this ensures that all runtime types will have to be re-created in each loop iteration.)</p>
  
  <p>Here's a X-Y plot of the output:</p>
  
  <p><img src="https://i.stack.imgur.com/xWJW1.png" alt="Line chart showing a measurement for recursive generic type instantiation times"></p>
  
  <ul>
  <li><p>Horizontal axis: <em>N</em> denotes the depth of type recursion, i.e.:</p>
  
  <ul>
  <li><em>N</em> = 1 indicates a <code>NonEmptyStack&lt;EmptyStack&lt;T&gt;&gt;</code></li>
  <li><em>N</em> = 2 indicates a <code>NonEmptyStack&lt;NonEmptyStack&lt;EmptyStack&lt;T&gt;&gt;&gt;</code></li>
  <li>etc.</li>
  </ul></li>
  <li><p>Vertical axis: <em>t</em> is the time (in milliseconds) required to push <em>N</em> integers onto a stack. (The time needed to create runtime types, if that actually happens, is included in this measurement.)</p></li>
  </ul>