递归泛型类型的实例化会以嵌套的方式逐渐减慢.为什么？

Question

注意:我可能在标题中选择了错误的单词; 也许我真的在谈论多项式增长.请参阅此问题末尾的基准测试结果.

让我们从这三个表示不可变堆栈的递归通用接口^†开始:

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);
}

我创建了简单的实现EmptyStack<T>,NonEmptyStack<T,TStackBeneath>.

更新#1:请参阅下面的代码.

我注意到有关其运行时性能的以下内容:

• EmptyStack<int>第一次将1,000件物品推到a上需要7秒多.
• 将1,000件物品推到一起EmptyStack<int>几乎没有时间.
• 我推入堆栈的项目越多,性能就会越来越差.

更新#2:

• 我终于进行了更精确的测量.请参阅下面的基准代码和结果.

• 我在这些测试中只发现.NET 3.5似乎不允许递归深度≥100的泛型类型..NET 4似乎没有这个限制.

前两个事实让我怀疑性能缓慢不是由于我的实现,而是由于类型系统:.NET必须实例化1,000个不同的封闭泛型类型,即:

• 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>>>,等得到成倍慢更深它们嵌套？
3. 是否已知除了.NET(Mono,Silverlight,.NET Compact等)之外的CLR实现具有相同的特性？

---

^†)偏离主题的脚注:这些类型非常有趣btw.因为它们允许编译器捕获某些错误,例如:

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

或者您可以表达某些堆栈操作的要求:

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的递归泛型类型实例化时间.这是一个与我最初使用的机器不同,速度更快的机器,因此结果与上述语句不匹配.

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);
}

(每个度量都在一个单独的应用程序域中进行,因为这可确保在每次循环迭代中都必须重新创建所有运行时类型.)

这是输出的XY图:

• 水平轴:N表示递归类型的深度,即:

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

• 垂直轴:t是将N个整数推入堆栈所需的时间(以毫秒为单位).(创建运行时类型所需的时间,如果实际发生,则包含在此度量中.)

Answer 1

访问新类型会导致运行时将其从 IL 重新编译为本机代码（x86 等）。运行时还会优化代码，这也会针对值类型和引用类型产生不同的结果。

显然，List<int>优化的方式与List<List<int>>.

因此，alsoEmptyStack<int>等等NonEmptyStack<int, EmptyStack<int>>将被视为完全不同的类型，并且都将被“重新编译”和优化。（据我所知！）

通过嵌套更多层，结果类型的复杂性会增加，并且优化需要更长的时间。

因此，添加一层需要 1 个步骤来重新编译和优化，下一层需要 2 个步骤加上第一步（左右），第三层需要 1 + 2 + 3 个步骤等。