.net - 递归泛型类型的实例化速度越慢，嵌套越深。为什么？

Question

Note: I may have chosen the wrong word in the title; perhaps I'm really talking about polynomial growth here. See the benchmark result at the end of this question.

让我们从这三个递归泛型接口(interface)开始 † 代表不可变堆栈:

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> .

Update #1: See the code below.

我注意到它们的运行时性能有以下几点:

将 1,000 个项目推送到 EmptyStack<int>第一次需要超过 7 秒。

将 1,000 个项目推送到 EmptyStack<int>之后几乎不需要任何时间。

我插入堆栈的项目越多，性能就越差。

Update #2:

• I've finally performed a more precise measurement. See the benchmark code and results below.

• I've only discovered during these tests that .NET 3.5 doesn't seem to allow generic types with a recursion depth ≥ 100. .NET 4 doesn't seem to have this restriction.

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

EmptyStack<int>

NonEmptyStack<int, EmptyStack<int>>

NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>

NonEmptyStack<int, NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>>

等

问题:

我的上述评估是否正确？

如果是这样，为什么要实例化泛型类型如 T<U> , T<T<U>> , T<T<T<U>>> ，等等它们嵌套得越深，速度就越慢？

.NET(Mono、Silverlight、.NET Compact 等)以外的 CLR 实现是否已知具有相同的特性？

^†) Off-topic footnote: These types are quite interesting btw. because they allow the compiler to catch certain errors such as:

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

Or you can express requirements for certain stack operations:

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

更新#1:上述接口(interface)的实现

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

(每次测量都在单独的应用程序域中进行，因为这确保了所有运行时类型都必须在每次循环迭代中重新创建。)

这是输出的 X-Y 图:

横轴:N 表示类型递归的深度，即:

N = 1 表示 NonEmptyStack<EmptyStack<T>>

N = 2 表示 NonEmptyStack<NonEmptyStack<EmptyStack<T>>>

等

纵轴:t 是将 N 个整数压入堆栈所需的时间(以毫秒为单位)。 (创建运行时类型所需的时间，如果确实发生，则包含在此测量中。)

Answer 1

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

和List<int>显然会以不同于 List<List<int>> 的方式进行优化.

因此也是EmptyStack<int>和 NonEmptyStack<int, EmptyStack<int>>等等将作为完全不同的类型处理，并且都将被“重新编译”和优化。
(据我所知!)

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

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