Databases
StackOverflow2013
Postsdbo
POInstantiation of recursive generic types slows down exponentially the deeper they are nested. Why?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POInstantiation of recursive generic types slows down exponentially the deeper they are nested. Why?
    primarykey
    data
    text
    <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>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USstakx
    1. USstakx
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    3. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POInstantiation of recursive generic types slows down exponentially the deeper they are nested. Why?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POInstantiation of recursive generic types slows down exponentially the deeper they are nested. Why?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POInstantiation of recursive generic types slows down exponentially the deeper they are nested. Why?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIt would really help if you could provide the implementations and your benchmarking code... oh, and an idea of whether you were *really* going to try to use code like this, which seems rather tortuous to me.
      singulars
      1. POInstantiation of recursive generic types slows down exponentially the deeper they are nested. Why?
      1. USJon Skeet
    2. COAs far as I know .NET creates single closed generic class per unique generic parameters set and then reuse it, so for creating 1000 instances of EmptyStack<int> one type should be created, why you mentioned 1000?
      singulars
      1. POInstantiation of recursive generic types slows down exponentially the deeper they are nested. Why?
      1. USsll
    3. CO@Jon, **1.** I've appended the implementation at the end of the question. **2.** It was more an experiment than production code for regular use, but using these classes is actually not a hassle at all thanks to type inference.
      singulars
      1. POInstantiation of recursive generic types slows down exponentially the deeper they are nested. Why?
      1. USstakx
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload