Why doesn't .NET/C# optimize for tail-call recursion?

我发现了 这个问题关于哪些语言优化了尾部递归。为什么 C # 不优化尾部递归，只要有可能？

For a concrete case, why isn't this method optimized into a loop (VisualStudio2008 32-bit, if that matters)?:

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


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


Foo(i+1);
}
35828 次浏览
小开

这个 Microsoft 连接反馈提交应该可以回答你的问题。它包含了来自微软的官方回复，所以我建议按照这个来。

谢谢你的建议 被认为是发出尾部呼叫 指令在许多点 the development of the C# compiler. 然而，还有一些微妙的问题 促使我们避免这样做 Far: 1)实际上有一个 非平凡的间接成本使用 。在 CLR 中的尾指令(它是 不仅仅是一个跳跃指令作为尾巴 电话最终变得很少 严格的环境，如功能 语言运行时环境，其中 尾部调用进行了大量优化) 很少有真正的 C # 方法 would be legal to emit tail calls (其他语言鼓励编码 patterns which have more tail 递归，以及许多严重依赖 在尾部呼叫优化实际上做 全球重写(例如 传递转换) 增加尾巴的数量 递归)。3)部分原因是2) , C # 方法堆栈溢出的情况 由于深度递归，应该有 成功的是相当罕见的。

尽管如此，我们继续关注 这个，我们可能在未来释放 找到一些模式 where it makes sense to emit .tail 指示。

顺便说一下，正如已经指出的，值得注意的是尾递归 是在 x64上进行了优化。

小开

最近有人告诉我，64位的 C # 编译器可以优化尾部递归。

C # 也实现了这一点。之所以不总是应用它，是因为用于应用尾递归的规则非常严格。

小开
最佳答案

JIT compilation is a tricky balancing act between not spending too much time doing the compilation phase (thus slowing down short lived applications considerably) vs. not doing enough analysis to keep the application competitive in the long term with a standard ahead-of-time compilation.

有趣的是，NGen编译步骤并没有针对更积极的优化。我怀疑这是因为他们只是不希望出现 bug，因为这些 bug 的行为取决于 JIT 或 NGen 是否对机器代码负责。

The CLR itself does support tail call optimization, but the language-specific compiler must know how to generate the relevant 代码 and the JIT must be willing to respect it. F # 的 fsc 将生成相关的操作码(尽管对于一个简单的递归，它可能只是将整个事情直接转换成一个 while循环)。C # 的 CSC 没有。

有关一些详细信息，请参阅 这篇博文(由于最近的 JIT 更改，现在很可能已经过时)。注意，对于4.0 X86 x64和 IA64会尊重它，CLR 发生了变化。

小开

在 C # (或 Java)中，可以对尾递归函数使用 蹦床技术。但是，更好的解决方案(如果您只关心堆栈利用率)是使用 this small helper方法来包装相同递归函数的部分，并使其在保持函数可读性的同时进行迭代。

小开

C # 不会优化尾部调用递归，因为这就是 F # 的用途！

有关阻止 C # 编译器执行尾部调用优化的条件的详细信息，请参阅本文: 尾部呼叫条件。

C # 与 F # 的互操作性

C # 和 F # 的互操作非常好，因为。NET 通用语言运行库(CLR)的设计考虑到了这种互操作性，每种语言的设计都针对其意图和目的进行了优化。有关从 C # 代码调用 F # 代码的示例，请参见 从 C # 代码调用 F # 代码; 有关从 F # 代码调用 C # 函数的示例，请参见 从 F # 调用 C # 函数。

有关委托互操作性，请参阅本文: F # 、 C # 和 VisualBasic 之间的委托互操作性。

C # 与 F # 在理论和实践上的差异

下面这篇文章介绍了 C # 和 F # 之间的一些差异，并解释了尾部调用递归的设计差异: 用 C # 和 F # 生成尾调操作码。

Here is an article with some examples in C#, F#, and C++\CLI: C # ，F # 和 C + + CLI 中的尾部递归冒险

主要的理论区别在于 C # 是用循环设计的，而 F # 是根据 Lambda 演算原理设计的。有关 Lambda 微积分原理的一本非常好的书，请参阅这本免费书: 计算机程序的构造和解释，由阿贝尔森，萨斯曼和萨斯曼。

有关 F # 中尾部调用的非常好的介绍性文章，请参阅本文: F # 中尾部呼叫的详细介绍。最后，这里有一篇文章介绍了非尾递归和尾调用递归之间的区别(在 F # 中) : F 调整下的尾递归与非尾递归。

小开

正如其他答案所提到的，CLR 确实支持尾部调用优化，而且它似乎在历史上一直处于逐步改进之中。但是在 C # 中支持它在设计 C # 编程语言 支持尾递归 # 2544的 git 存储库中有一个开放的 Proposal问题。

你可以在那里找到一些有用的细节和信息

让我说出我知道的。

有时候尾随呼叫是性能双赢。它可以节省 CPU cheaper than call/ret It can save stack. Touching less stack makes for 更好的地方。

有时候尾随是一种性能损失，堆栈赢。 CLR 有一个复杂的机制，可以将更多的参数传递给它 the callee than the caller recieved. I mean specifically more stack 空间的参数。这是缓慢的。但它节省堆栈。它将 只能用尾巴，前缀。

如果调用方参数是 stack-larger than callee parameters, it usually a pretty easy win-win 可能存在参数位置改变等因素 from managed to integer/float, and generating precise StackMaps and 这样。

现在，还有另外一个角度，算法需要 尾部呼叫消除，为了能够处理 具有固定/小堆栈的任意大数据 performance, but about ability to run at all.

Also let me mention (as extra info), When we are generating a compiled lambda using expression classes in System.Linq.Expressions namespace, there is an argument named 'tailCall' that as explained in its comment it is

指示在编译创建的表达式时是否应用尾部调用优化的 bool。

我还没有尝试过，我不知道它如何能帮助您的问题，但也许有人可以尝试它，并可能在某些情况下有用:


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


var myFunc =  myFuncExpression.Compile();
小开

I had a happy surprise today :-)

我正在复习我即将上的 C # 递归课程的教材。 似乎尾部调用优化最终进入了 C # 。

我使用 NET5与 LINQPad 6(优化激活)。

下面是我使用的 Tail 调用可优化的 Factorial 函数:

long Factorial(int n, long acc = 1)
{
if (n <= 1)
return acc;
return Factorial(n - 1, n * acc);
}

下面是为这个函数生成的 X64汇编代码:

Assembly code

看，没有 call只有 jmp。该函数也进行了积极的优化(没有堆栈帧设置/拆卸)。哦，是的！


提交答案