19

tl;博士;

在 C# 中，你是否保证一个惰性迭代器函数只调用它自己并且确实有一个有效的递归退出条件不会导致堆栈溢出？

详细问题：

我知道，作为一项规则，您无法保证 C# 编译器（或 JIT）生成的尾调用优化 (TCO) 指令，因此虽然您可能会获得 TCO，但无法保证。

鉴于对 TCO 的这种认识，我想知道惰性迭代器函数（使用yield return等）是否因为它们作为协程的性质 - 每个尾调用是否会占用堆栈空间？由于协程的可重入性，我对协程的直觉是，默认情况下每个尾调用都经过优化，因为能够跳出函数并从父框架进入下一个函数而不是创建新框架似乎很自然。

这是 C# 中的行为，还是 C# 迭代器函数的递归调用从当前创建一个新框架，而不是弹出到父框架并使用新参数重新输入？

例子：

public static IEnumerable<IEnumerable<T>> GeneratePermutations<T>(this IEnumerable<T> choices, int numberToChoose)
{
    if (numberToChoose == 1)
    {
        foreach (var choice in choices)
            yield return new T[] { choice };
        yield break;
    }

    var subPermutations = choices.SelectMany(choice =>
        choices.Where(elem => !EqualityComparer<T>.Default.Equals(elem, choice))
            .GeneratePermutations(numberToChoose - 1)
            .Select(permutation => (new T[] { choice }).Concat(permutation)));
    foreach (var perm in subPermutations)
        yield return perm;
}

我的直觉是基于上面的例子subPermutations只是一个堆计算，它似乎在调用迭代它时，它可以知道它是一个堆计算（它是函数sig的一部分，它是一个迭代器函数），因此立即跳转超出当前帧并将堆积的计算扩展到新帧 -在尝试递归调用之前不会花费额外的堆栈空间......

这种直觉可能完全没有根据……

4

1 回答 1

10

所以，让我们打开一个示例方法，以便我们有一些东西可以参考：

public static IEnumerable<int> Foo()
{
    yield return 1;
    foreach (var n in Foo())
        yield return n;
}

这是我们的递归迭代器块。我只是想花点时间来介绍一下这个方法的一些属性，这些属性可能（或可能不）最终是相关的。

  • 有一个递归调用，但递归调用在yield.

  • 当我们确实到达递归调用时，在那之后我们唯一要做的就是产生所有结果。每个项目都没有投影，没有finally块，在这些产量之后什么都没有，等等。

那么，当一些代码去写以下内容时会发生什么？

foreach(var n in Foo())
    Console.WriteLine(n);

好吧，当我们到达这个语句时发生的第一件事就是评估Foo()一个值。在这种情况下，这将创建表示序列生成器的状态机。我们实际上并没有执行方法体中的任何代码。

接下来，我们调用MoveNext. 我们点击我们的第一个yield块，产生一个值，然后打印出来。

之后，最外层MoveNext再次调用。在这里，我们的状态机的MoveNext方法到达它自己的foreach块。与该方法一样，它将Main评估Foo()为一个值，从而创建第二个状态机。然后它将立即调用MoveNext该状态机。第二个状态机将到达它的第一个状态机yield，它将向第一个迭代器产生值，该迭代器将把它返回给将打印它的 main 方法。

然后再次调用 main 方法MoveNext。第一个迭代器向第二个迭代器询问它的第二个项目，第二个迭代器到达它的foreach方法，创建第三个迭代器，并从中获取一个值。该值一直向上传递。

正如我们在这里看到的，每次我们作为另一个项目的顶级迭代器时，堆栈总是比以前更深一层。尽管我们正在使用状态机，并且创建迭代器并不会消耗大量堆栈空间，但获取序列中的下一项将消耗越来越多的堆栈空间，直到我们用完为止。

运行代码时，我们可以看到事情完全按照这里描述的那样工作，并且堆栈将溢出。

那么，这怎么可能优化呢？

好吧，我们希望在这里做的是让顶级迭代器意识到，当它到达foreach“从现在开始，我序列中的其余项目与递归调用中的所有项目相同”时. 这听起来很像典型的 TCO 情况。

所以在这一点上，我们有两个问题需要解决。首先，如果我们认识到我们处于这种情况，我们实际上是否可以避免创建额外的状态机，从而避免不断增加的堆栈空间。它不会那么容易，可能不像传统的非迭代器块 TCO 那样容易。您需要将状态机的所有实例字段设置为如果您调用Foo. 在这一点上，我只是挥手说这听起来可能，但并不是每个都超级好。

然后我们有另一个问题。我们如何才能认识到我们实际上处于 TCO 有效的位置？我们需要递归调用自己，我们需要对该方法调用不做任何事情，除了迭代整个事物并按原样产生每个项目，我们不需要在一个try或using块中（否则finally块会丢失） ，并且在该迭代之后不能有任何方法。

现在，如果有一个yield foreach运营商，那么这不会那么糟糕。您只需设置规则，如果迭代器块中的最后一条语句是一个在最后yield foreach对方法进行递归调用的运算符，则应用 TCO。遗憾的是，在 C# 中（与其他一些 .NET 语言不同）我们没有yield foreach运算符。我们需要输入整个foreach运算符，同时除了按原样生成项目之外什么也不做。好像……有点尴尬。

回顾一下：

  • 编译器是否可以对递归迭代器块使用尾调用优化？
    • 最有可能的。
  • 它是由编译器完成的吗？
    • 看起来并非如此。
  • 将这种支持添加到编译器中是否特别可行？
    • 可能不是。
于 2014-08-14T19:42:05.950 回答