recursiongenericstypes的实例化在它们嵌套的越深处指数地减慢。 为什么？

注：我可能在标题中select了错误的词语; 也许我真的在 这里 谈论多项式增长。 在这个问题的末尾查看基准testing结果。

让我们从这三个代表不可变堆栈的recursiongenerics接口开始：

interface IStack<T> { INonEmptyStack<T, IStack<T>> Push(T x); } interface IEmptyStack<T> : IStack<T> { new INonEmptyStack<T, IEmptyStack<T>> Push(T x); } interface INonEmptyStack<T, out TStackBeneath> : IStack<T> where TStackBeneath : IStack<T> { T Top { get; } TStackBeneath Pop(); new INonEmptyStack<T, INonEmptyStack<T, TStackBeneath>> Push(T x); } 

我创build了简单的实现EmptyStack<T> ， NonEmptyStack<T,TStackBeneath> 。

更新＃1：请参阅下面的代码。

我注意到他们的运行时性能如下：

• 首次将1000个项目推送到EmptyStack<int>需要7秒以上。
• 将1000个物品推到EmptyStack<int>之后几乎不需要任何时间。
• 性能得到指数更糟，我把更多的项目推入堆栈。

更新＃2：

• 我终于做了一个更精确的测量。 请参阅下面的基准代码和结果。

• 我只在这些testing中发现，.NET 3.5似乎不允许recursion深度≥100的genericstypes.NET 4似乎没有这个限制。

前两个事实让我怀疑慢性能不是由于我的实现，而是由于types系统：.NET必须实例化1000个不同的封闭genericstypes ，即：

• EmptyStack<int>
• NonEmptyStack<int, EmptyStack<int>>
• NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>
• NonEmptyStack<int, NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>>
• 等等

问题：

1. 我上面的评估是否正确？
2. 如果是这样的话，那么为什么T<U> ， T<T<U>> ， T<T<T<U>>>等genericstypes的实例化在嵌套越深的时候指数级地越慢？
3. 已知.NET以外的CLR实现（Mono，Silverlight，.NET Compact等）展现出相同的特性？

---

^{† ）}题外话题：这些types是相当有趣的顺便说一句。 因为它们允许编译器捕获某些错误，如：

 stack.Push(item).Pop().Pop(); // ^^^^^^ // causes compile-time error if 'stack' is not known to be non-empty. 

或者你可以expression对某些堆栈操作的要求：

 TStackBeneath PopTwoItems<T, TStackBeneath> (INonEmptyStack<T, INonEmptyStack<T, TStackBeneath> stack) 

---

更新＃1：实现上述接口

 internal class EmptyStack<T> : IEmptyStack<T> { public INonEmptyStack<T, IEmptyStack<T>> Push(T x) { return new NonEmptyStack<T, IEmptyStack<T>>(x, this); } INonEmptyStack<T, IStack<T>> IStack<T>.Push(T x) { return Push(x); } } // ^ this could be made into a singleton per type T internal class NonEmptyStack<T, TStackBeneath> : INonEmptyStack<T, TStackBeneath> where TStackBeneath : IStack<T> { 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<T, INonEmptyStack<T, TStackBeneath>> Push(T x) { return new NonEmptyStack<T, INonEmptyStack<T, TStackBeneath>>(x, this); } INonEmptyStack<T, IStack<T>> IStack<T>.Push(T x) { return Push(x); } } 

---

更新＃2：基准代码和结果

我使用下面的代码来测量Windows 7 SP 1 x64（Intel U4100 @ 1.3 GHz，4 GB RAM）笔记本上.NET 4的recursiongenericstypes实例化时间。 这与我原来使用的机器不同，速度更快，所以结果与上面的说明不符。

 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<int> s = new EmptyStack<int>(); for (int i = 0; i < n; ++i) { s = s.Push(i); // <-- this "creates" a new type } stopwatch.Stop(); long ms = stopwatch.ElapsedMilliseconds; Console.WriteLine("{0}, {1}", n, ms); }); AppDomain.Unload(appDomain); } 

（每个测量都是在一个单独的应用程序域中进行的，因为这样可以确保在每次循环迭代中都必须重新创build所有运行时types。）

以下是输出的XY图：

• 水平轴： N表示typesrecursion的深度，即：

  • N = 1表示NonEmptyStack<EmptyStack<T>>
  • N = 2表示NonEmptyStack<NonEmptyStack<EmptyStack<T>>>
  • 等等

• 垂直轴： t是将N个整数推入堆栈所需的时间（以毫秒为单位）。 （创build运行时types所需的时间（如果实际发生的话）包含在此度量中。）

Answer 1

访问一个新types会导致运行时从IL重新编译为本地代码（x86等）。 运行时还会优化代码，这也会为值types和引用types产生不同的结果。

和List<int>显然会比List<List<int>>优化。

因此也将EmptyStack<int>和NonEmptyStack<int, EmptyStack<int>>等作为完全不同的types进行处理，并将全部重新编译和优化。 （我所知道的！）

通过嵌套更多的层次，结果types的复杂性增长，优化需要更长的时间。

所以添加一层需要1步重新编译和优化，下一层需要2步加第一步（左右），第三层需要1 + 2 + 3步等。

Answer 2

如果James和其他人在运行时创build的types是正确的，那么性能受到types创build速度的限制。 那么，为什么types创作的速度呈指数级缓慢呢？ 我认为，按照定义，types是彼此不同的。 因此，下一个types会导致一系列不同的内存分配和释放模式。 速度仅仅受到GC自动pipe理内存效率的限制。 有一些积极的顺序，这将减缓任何内存pipe理器，不pipe它有多好。 GC和分配器将花费越来越多的时间为下一个分配和大小寻找最佳大小的可用内存块。

回答：

因为，你发现了一个非常激进的序列，这个序列使得记忆碎片如此糟糕，速度如此之快，使得GC难以置信。

从中可以学到的是：真正快速的真实世界的应用程序（例如：algorithm股票交易应用程序）是非常简单的具有静态数据结构的直接代码片段，只为整个应用程序运行分配一次。

Answer 3

在Java中，计算时间似乎比线性要高一点，而且比在.net中报告的要高效得多。 从我的答案中使用testRandomPopper方法，运行N = 10,000,000大约需要4秒，运行N = 20,000,000的时间约为10秒

Answer 4

有没有迫切需要区分空的堆栈和非空的堆栈？

从实际的angular度来看，如果没有完全限定types，并且在添加1,000个非常长的types名称之后，就不能popup任意堆栈的值。

为什么不这样做：

 public interface IImmutableStack<T> { T Top { get; } IImmutableStack<T> Pop { get; } IImmutableStack<T> Push(T x); } public class ImmutableStack<T> : IImmutableStack<T> { private ImmutableStack(T top, IImmutableStack<T> pop) { this.Top = top; this.Pop = pop; } public T Top { get; private set; } public IImmutableStack<T> Pop { get; private set; } public static IImmutableStack<T> Push(T x) { return new ImmutableStack<T>(x, null); } IImmutableStack<T> IImmutableStack<T>.Push(T x) { return new ImmutableStack<T>(x, this); } } 

你可以传递任何IImmutableStack<T> ，你只需要检查Pop == null来知道你已经达到了堆栈的末端。

否则，这就是你正在尝试编码的语义，而不会影响性能。 我用这个代码在1.873秒内创build了一个具有10,000,000个值的堆栈。