递归泛型类型的实例化会减慢指数它们嵌套更深。为什么？ [英] Instantiation of recursive generic types slows down exponentially the deeper they are nested. Why?

问题描述

  

注意：我可能选择了错误的字称号;也许我真的在谈论的多项式的生长在这里。看到这一问题最终的基准测试结果。的

让我们先从这三个递归通用接口 ^＆匕首; 的重新present不变的堆栈：

接口ISTACK＆LT; T＆GT; {     INonEmptyStack＆LT; T，ISTACK＆LT; T＆GT;＆GT;推送（T X）; } 接口IEmptyStack＆LT; T＆GT; ：ISTACK＆LT; T＆GT; {     新INonEmptyStack＆LT; T，IEmptyStack＆LT; T＆GT;＆GT;推送（T X）; } 接口INonEmptyStack＆LT; T，出TStackBeneath＆GT; ：ISTACK＆LT; T＆GT;     其中，TStackBeneath：ISTACK＆LT; T＆GT; {     T顶部{获得; }     TStackBeneath POP（）;     新INonEmptyStack＆LT; T，INonEmptyStack＆LT; T，TStackBeneath＆GT;＆GT;推送（T X）; }

我已经创建了简单的实施 EmptyStack＆LT; T＆GT; ， NonEmptyStack＆LT; T，TStackBeneath＆GT;

  

更新＃1：见$ C $低于C 的

我发现下面的东西对他们的运行时性能：

• 在推进1000项目到一个 EmptyStack＆LT; INT＆GT; 首次需要7秒钟以上
• 在推进1000项目到一个 EmptyStack＆LT; INT＆GT; 需要几乎没有时间之后
• 性能得到成倍越差更多的项目我推到堆栈中。

  

更新＃2： 的

     

  

• 我终于完成了更precise测量。见基准code和下面的结果。的

  

• 我只在这些测试，.NET 3.5似乎并没有让泛型类型用递归深度GE发现; 100. .NET 4中似乎没有这个限制。的

  

前两个事实让我怀疑的性能下降不是由于我的实现，而是类型系统：NET有实例1,000个不同的封闭通用的类型的，即：

• EmptyStack＆LT; INT＆GT;
• NonEmptyStack＆LT; INT，EmptyStack＆LT; INT＆GT;＆GT;
• NonEmptyStack＆LT; INT，NonEmptyStack＆LT; INT，EmptyStack＆LT; INT＆GT;＆GT;＆GT;
• NonEmptyStack＆LT; INT，NonEmptyStack＆LT; INT，NonEmptyStack＆LT; INT，EmptyStack＆LT; INT＆GT;＆GT;＆GT;＆GT;
• 等

问题：

1. 是我的上述评估是否正确？
2. 如果是这样，为什么泛型类型，如 T＆LT的实例; U＆GT; ， T＆LT; T＆LT; U＆GT;＆GT; ， T＆LT; T＆LT; T＆LT; U＆GT;＆GT;＆GT; ，等获得的指数的慢更深它们嵌套？
3. 是CLR实现比.NET（单声道，Silverlight中，.NET精简等），已知具有相同特征的其他？

---

  

^{＆匕首; ）}题外话注脚：这种类型是很有意思的BTW。因为它们允许编译器捕获某些错误，如：的

     

stack.Push（项目）.Pop（）POP（）。 // ^^^^^^ //原因编译时错误，如果堆栈不知道是非空。

     

也可以为特定的堆栈操作EX preSS要求：的

  TStackBeneath PopTwoItems＆LT; T，TStackBeneath＆GT;
              （INonEmptyStack＆LT; T，INonEmptyStack＆LT; T，TStackBeneath＆GT;堆栈）
 

---

更新＃1：上述接口的实现

 内部类EmptyStack＆LT; T＆GT; ：IEmptyStack＆LT; T＆GT;
{
    公共INonEmptyStack＆LT; T，IEmptyStack＆LT; T＆GT;＆GT;推送（T X）
    {
        返回新NonEmptyStack＆LT; T，IEmptyStack＆LT; T＆GT;＆GT;（X，这一点）;
    }

    INonEmptyStack＆LT; T，ISTACK＆LT; T＆GT;＆GT; ISTACK＆LT; T＆GT; .Push（T X）
    {
        回推（X）;
    }
}
// ^这可以做成每个类型T单身

内部类NonEmptyStack＆LT; T，TStackBeneath＆GT; ：INonEmptyStack＆LT; T，TStackBeneath＆GT;
    其中，TStackBeneath：ISTACK＆LT; T＆GT;
{
    私人只读T顶部;
    私人只读TStackBeneath stackBeneathTop;

    公共NonEmptyStack（T顶部，TStackBeneath stackBeneathTop）
    {
        this.top =顶部;
        this.stackBeneathTop = stackBeneathTop;
    }

    大众T顶部{{返回顶部; }}

    公共TStackBeneath POP（）
    {
        返回stackBeneathTop;
    }

    公共INonEmptyStack＆LT; T，INonEmptyStack＆LT; T，TStackBeneath＆GT;＆GT;推送（T X）
    {
        返回新NonEmptyStack＆LT; T，INonEmptyStack＆LT; T，TStackBeneath＆GT;＆GT;（X，这一点）;
    }

    INonEmptyStack＆LT; T，ISTACK＆LT; T＆GT;＆GT; ISTACK＆LT; T＆GT; .Push（T X）
    {
        回推（X）;
    }
}
 

---

更新＃2：基准code和结果

我用下面的code来衡量递推泛型类型实例化时间.NET 4在Windows 7 SP 1的x64（英特尔U4100 @ 1.3 GHz，拥有4 GB RAM）的笔记本电脑。这是一个不同的，更快的机器比我最初使用，所以结果不与上面的语句匹配

  Console.WriteLine（N，T [毫秒]）;
INT outerN = 0;
而（真）
{
    outerN ++;
    变种的AppDomain = AppDomain.CreateDomain（outerN.ToString（））;
    appDomain.SetData（n的，outerN）;
    appDomain.DoCallBack（委托{
        INT N =（INT）AppDomain.CurrentDomain.GetData（N）;
        VAR秒表=新的秒表（）;
        stopwatch.Start（）;
        ISTACK＆LT; INT＆GT; S =新EmptyStack＆LT;诠释＆GT;（）;
        的for（int i = 0;我n种; ++ I）
        {
            S = s.Push（ⅰ）; //＆LT;  - 这种创造的新型
        }
        stopwatch.Stop（）;
        长毫秒= stopwatch.ElapsedMilliseconds;
        Console.WriteLine（{0}，{1}，N，MS）;
    }）;
    AppDomain.Unload（的AppDomain）;
}
 

（每个测量时在一个单独的应用程序的域，因为这确保了所有的运行时的类型将在每个循环迭代中重新创建。）

下面是输出的X-Y图：

• 横轴： N 的代表型递归的深度，即：

  • 的 N 的= 1表示一个 NonEmptyStack＆LT; EmptyStack＆LT; T＆GT;＆GT;
  • 的 N 的= 2表示 NonEmptyStack＆LT; NonEmptyStack＆LT; EmptyStack＆LT; T＆GT;＆GT;＆GT;
  • 等

• 垂直轴： T 的是，推动的 N 的整数入栈所需要的时间（毫秒）。 （该时间需要创建运行时类型来说，如果实际情况发生时，被包括在该测量。）

解决方案

访问一个新的类型会导致运行时从IL重新编译为本地code（86等）。运行时也优化了code，这也将产生不同的结果值类型和引用类型。

和名单，其中，INT＆GT; 明确提出将优化不同于名单，其中，名单，其中，INT＆GT;＆GT;

因此​​也 EmptyStack＆LT; INT＆GT; 和 NonEmptyStack＆LT; INT，EmptyStack＆LT; INT＆GT;＆GT; 等会被处理为完全不同的类型和将全部重新编译和优化。 （据我所知！）

通过嵌套进一步层的结果类型的复杂性的增长和优化需要较长的时间。

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

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.

Let's start with these three recursive generic interfaces^† that represent immutable stacks:

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

I've created straightforward implementations EmptyStack<T>, NonEmptyStack<T,TStackBeneath>.

Update #1: See the code below.

I've noticed the following things about their runtime performance:

• Pushing 1,000 items onto an EmptyStack<int> for the first time takes more than 7 seconds.
• Pushing 1,000 items onto an EmptyStack<int> takes virtually no time at all afterwards.
• Performance gets exponentially worse the more items I push onto the stack.

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.

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 types, ie.:

• EmptyStack<int>
• NonEmptyStack<int, EmptyStack<int>>
• NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>
• NonEmptyStack<int, NonEmptyStack<int, NonEmptyStack<int, EmptyStack<int>>>>
• etc.

Questions:

1. Is my above assessment correct?
2. If so, why does instantiation of generic types such as T<U>, T<T<U>>, T<T<T<U>>>, and so on get exponentially slower the deeper they are nested?
3. Are CLR implementations other than .NET (Mono, Silverlight, .NET Compact etc.) known to exhibit the same characteristics?

---

^†) 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)

---

Update #1: Implementation of the above interfaces

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

---

Update #2: Benchmark code and results

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.

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

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

Here's a X-Y plot of the output:

• Horizontal axis: N denotes the depth of type recursion, i.e.:

  • N = 1 indicates a NonEmptyStack<EmptyStack<T>>
  • N = 2 indicates a NonEmptyStack<NonEmptyStack<EmptyStack<T>>>
  • etc.

• Vertical axis: t is the time (in milliseconds) required to push N integers onto a stack. (The time needed to create runtime types, if that actually happens, is included in this measurement.)

解决方案

Accessing a new type causes the runtime to recompile it from IL to native code (x86 etc). The runtime also optimizes the code, which will also produce different results for value types and reference types.

And List<int> clearly will be optimized differently than List<List<int>>.

Thus also EmptyStack<int> and NonEmptyStack<int, EmptyStack<int>> and so on will be handled as completely different types and will all be 'recompiled' and optimized. (As far as I know!)

By nesting further layers the complexity of the resulting type grows and the optimization takes longer.

So adding one layer takes 1 step to recompile and optimize, the next layer takes 2 steps plus the first step (or so) and the 3rd layer takes 1 + 2 + 3 steps etc.

这篇关于递归泛型类型的实例化会减慢指数它们嵌套更深。为什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！