为什么.NET/C#没有针对尾递归进行优化?

125

我在StackOverflow上找到了一个关于哪些语言支持尾递归优化的问题。这里是链接。为什么C#不会在可能的情况下优化尾递归?

举个具体例子,为什么这个方法不能被优化成循环(在Visual Studio 2008 32位版本中,如果有影响的话):

private static void Foo(int i)
{
    if (i == 1000000)
        return;

    if (i % 100 == 0)
        Console.WriteLine(i);

    Foo(i+1);
}

今天我在阅读一本关于数据结构的书,其中将递归函数分为两种,即“抢占式”(例如阶乘算法)和“非抢占式”(例如Ackermann函数)。作者只给出了这两个例子,但没有给出这种分叉背后的合理原因。这种分叉是否与尾递归函数和非尾递归函数相同? - RBT
7
Jon Skeet和Scott Hanselman在2016年进行了有关此问题的有益讨论。 链接:https://youtu.be/H2KkiRbDZyc?t=3302 - Daniel B
@RBT:我认为这是不同的。它指的是递归调用的次数。尾调用是指出现在尾部位置的调用,即函数执行的最后一件事情,因此它直接从被调用者返回结果。 - J D
值得一提的是,.Net Framework 4.8的64位发布版本支持TCO。然而,这似乎在Core中被取消了。 - StuartLC
7个回答

90
JIT编译是一个棘手的平衡行为,既要避免在编译阶段花费太多时间(从而严重减慢短期应用程序的速度),又要做足够的分析以使应用程序在长期内与标准的预先编译相竞争。有趣的是,NGen 编译步骤并不针对更积极的优化。我怀疑这是因为他们根本不想出现行为取决于 JIT 还是 NGen 负责机器代码的错误。CLR 本身支持尾调用优化,但语言特定的编译器必须知道如何生成相关 opcode,并且 JIT 必须愿意尊重它。F# 的 fsc 将生成相关的操作码(尽管对于简单的递归,它可能直接将整个内容转换为 while 循环)。而 C# 的 csc 则不会。

请查看这篇博客文章以了解一些细节(可能已经过时,因为最近的JIT更改)。请注意,CLR 4.0的更改x86、x64和ia64将予以尊重


2
请参阅此帖子:http://social.msdn.microsoft.com/Forums/en-US/netfxtoolsdev/thread/67b6d908-8811-430f-bc84-0081f4393336?StatusCode=1,其中我发现尾调用比常规调用慢。哎呀! - plinth

81

这个Microsoft Connect反馈提交应该可以回答你的问题。它包含了来自Microsoft的官方回复,所以建议按照那个做。

感谢您的建议。在C#编译器的开发过程中,我们曾经考虑过在许多时候发出尾调用指令。然而,有一些微妙的问题迫使我们迄今为止避免使用.tail指令:1)在CLR中使用.tail指令实际上会产生非常显著的开销成本(它不仅仅是一个跳转指令,就像在许多较不严格的环境中最终变成的尾调用一样,例如函数式语言运行时环境,在那里尾调用得到了大量优化)。2)实际上很少有真正的C#方法可以合法地发出尾调用(其他语言鼓励具有更多尾递归的编码模式,并且许多依赖于尾调用优化的语言实际上进行全局重写(例如Continuation Passing 转换)来增加尾递归的数量)。3)部分是因为2),由于深度递归导致C#方法堆栈溢出的情况相当罕见。

总之,我们继续研究这个问题,可能会在未来的编译器版本中找到一些模式,在这些模式下发出.tail指令是有意义的。

顺便说一句,正如已经指出的那样,在x64上尾递归被优化了。


3
这也许对你有帮助:http://weblogs.asp.net/podwysocki/archive/2008/07/07/recursing-into-linear-tail-and-binary-recursion.aspx - Noldorin
没问题,很高兴你觉得有帮助。 - Noldorin
20
谢谢你引用它,因为现在它已经成为了一个404页面! - Roman Starkov
3
链接现在已修复。 - luksan

16

C#并没有优化尾递归,因为这正是F#的目的所在!

关于C#编译器无法执行尾调用优化的详细条件,请参阅这篇文章:JIT CLR tail-call conditions

C#和F#之间的互操作性

C#和F#之间的互操作性非常良好,由于.NET公共语言运行时(CLR)是设计用于此互操作性的,因此每种语言都具有特定于其意图和目的的优化。一个示例显示了从C#代码中调用F#代码有多容易,见Calling F# code from C# code;调用C#函数的F#代码示例,请参阅Calling C# functions from F#

有关委托互操作性,请参阅此文章:F#、C#和Visual Basic之间的委托互操作性

C#和F#之间的理论和实际差异

这是一篇涵盖了一些差异并解释了尾递归设计差异的文章,它适用于C#和F#:在C#和F#中生成尾调用操作码

这是一篇包含C#、F#和C++\CLI示例的文章:在C#、F#和C++\CLI中进行尾递归探险

主要的理论区别在于,C#是基于循环设计的,而F#则是基于Lambda演算原理设计的。关于Lambda演算原理的一本非常好的书籍,请参见此免费书籍:计算机程序的构造和解释,作者Abelson、Sussman和Sussman
关于F#中尾调用的一个很好的介绍文章,请参见此文章:详细介绍F#中的尾调用。最后,这篇文章涵盖了非尾递归和尾调用递归之间的区别(在F#中):F#中的尾递归与非尾递归之间的区别

10

我最近得知C#的64位编译器可以优化尾递归。

C#同样实现了这一点。但它没有被总是应用的原因是,用于应用尾递归的规则非常严格。


8
x64 jitter 可以做到这一点,但是 C# 编译器则不能。 - Mark Sowul
谢谢提供这些信息。这与我之前的想法完全不同。 - Alexandre Brisebois
4
为了澄清这两条评论,C#在任何情况下都不会生成CIL中的“tail”操作码。我相信这个情况在2017年仍然如此。然而,对于所有语言来说,“tail”操作码始终只是建议性的,也就是说,如果不满足各种条件(好的,除了可能的堆栈溢出错误之外),各自的JIT编译器(x86、x64)将会默默地忽略它。这解释了为什么你被迫在“tail”后面添加“ret” - 就是为了这种情况。同时,当CIL中没有“tail”前缀时,各个JIT编译器还可以自由地应用优化,无论.NET语言如何,视情况而定。 - Glenn Slayden

4
今天我有个令人开心的惊喜 :-)
我正在准备我的C#递归课程教材,看起来最终尾调用优化已经在C#中得到了应用。
我使用带有LINQPad 6(已经激活优化)的NET5。
下面是我使用的可进行尾调用优化的阶乘函数:
long Factorial(int n, long acc = 1)
{
    if (n <= 1)
        return acc;
    return Factorial(n - 1, n * acc);
}

以下是此功能生成的X64汇编代码:

Assembly code

注意,没有call,只有jmp。此函数也经过了激进的优化(没有堆栈帧设置/拆卸)。太好了!


3
你可以在C#(或Java)中使用蹦床技术来处理尾递归函数。然而,更好的解决方案(如果你只关心堆栈利用率)是使用这个小帮手方法来包装同一递归函数的部分,并使其迭代,同时保持函数的可读性。

2
蹦床是具有侵入性的(它们是对调用约定的全局更改),比正确的尾调用消除慢大约10倍,并且它们混淆了所有堆栈跟踪信息,使得调试和分析代码变得更加困难。 - J D

1
作为其他答案提到的,CLR确实支持尾递归优化,并且在历史上似乎一直在不断改进。但在C#中支持它在git存储库中有一个开放的建议问题,用于设计C#编程语言 Support tail recursion #2544
您可以在那里找到一些有用的细节和信息。例如@jaykrell提到
让我说一下我所知道的。有时候尾调用是性能上的双赢,可以节省CPU。jmp比call/ret更便宜,可以节省堆栈。触及更少的堆栈可以使局部性更好。有时候尾调用会导致性能损失,但堆栈会获胜。CLR有一个复杂的机制,可以将更多参数传递给被调用者而不是调用者接收到的。我的意思是特别指参数的更多堆栈空间。这很慢。但它保护了堆栈。它只会在tail.前缀中执行此操作。如果调用者的参数比被调用者的参数大,通常很容易实现双赢转换。可能存在诸如参数位置从托管到整数/浮点数的变化以及生成精确的StackMaps等因素。现在,还有另一种角度,即需要消除尾调用的算法,以便能够使用固定/小型堆栈处理任意大的数据。这不是关于性能,而是关于能够运行的能力。
此外,让我提到(作为额外信息),当我们使用System.Linq.Expressions命名空间中的表达式类生成编译的lambda时,有一个名为“tailCall”的参数,正如其注释所解释的那样。
一个布尔值,指示在编译创建的表达式时是否将应用尾调用优化。
我还没有尝试过它,也不确定它如何有助于您的问题,但可能有人可以尝试并在某些情况下有用:

var myFuncExpression = System.Linq.Expressions.Expression.Lambda<Func< … >>(body: … , tailCall: true, parameters: … );

var myFunc =  myFuncExpression.Compile();


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接