为什么 .NET/C# 不针对尾调用递归进行优化？

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

提问by ripper234

I found this questionabout which languages optimize tail recursion. Why C# doesn't optimize tail recursion, whenever possible?

我发现这个问题有关的语言优化尾递归。为什么 C# 尽可能不优化尾递归？

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

对于具体情况，为什么不将此方法优化为循环（Visual Studio 200832 位，如果重要的话）？：

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

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

    Foo(i+1);
}

采纳答案by ShuggyCoUk

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.

JIT 编译是在不花费太多时间进行编译阶段（从而大大减慢短期应用程序的速度）与没有进行足够的分析以通过标准的提前编译保持应用程序长期竞争力之间的微妙平衡.

Interestingly the NGencompilation steps are not targeted to being more aggressive in their optimizations. I suspect this is because they simply don't want to have bugs where the behaviour is dependent on whether the JIT or NGen was responsible for the machine code.

有趣的是，NGen编译步骤的目标并不是更积极地进行优化。我怀疑这是因为他们根本不希望出现行为取决于 JIT 还是 NGen 对机器代码负责的错误。

The CLRitself does support tail call optimization, but the language-specific compiler must know how to generate the relevant opcodeand the JIT must be willing to respect it. F#'sfsc will generate the relevant opcodes (though for a simple recursion it may just convert the whole thing into a whileloop directly). C#'s csc does not.

在CLR本身不支持尾调用优化，但语言的编译器特定必须知道如何生成相关的操作码和JIT必须愿意尊重它。 F# 的fsc 将生成相关的操作码（尽管对于简单的递归，它可能只是将整个事情while直接转换为循环）。C# 的 csc 没有。

See this blog postfor some details (quite possibly now out of date given recent JIT changes). Note that the CLR changes for 4.0 the x86, x64 and ia64 will respect it.

有关详细信息，请参阅此博客文章（鉴于最近的 JIT 更改，现在很可能已过时）。请注意，4.0 的 CLR 更改x86、x64 和 ia64 将尊重它。

回答by Noldorin

This Microsoft Connect feedback submissionshould answer your question. It contains an official response from Microsoft, so I'd recommend going by that.

此Microsoft Connect 反馈提交应能回答您的问题。它包含来自微软的官方回应，所以我建议你去看看。

Thanks for the suggestion. We've considered emiting tail call instructions at a number of points in the development of the C# compiler. However, there are some subtle issues which have pushed us to avoid this so far: 1) There is actually a non-trivial overhead cost to using the .tail instruction in the CLR (it is not just a jump instruction as tail calls ultimately become in many less strict environments such as functional language runtime environments where tail calls are heavily optimized). 2) There are few real C# methods where it would be legal to emit tail calls (other languages encourage coding patterns which have more tail recursion, and many that rely heavily on tail call optimization actually do global re-writing (such as Continuation Passing transformations) to increase the amount of tail recursion). 3) Partly because of 2), cases where C# methods stack overflow due to deep recursion that should have succeeded are fairly rare.

All that said, we continue to look at this, and we may in a future release of the compiler find some patterns where it makes sense to emit .tail instructions.

谢谢你的建议。在 C# 编译器的开发过程中，我们曾考虑在多个点发出尾调用指令。然而，到目前为止，有一些微妙的问题促使我们避免这种情况：1) 在 CLR 中使用 .tail 指令实际上有一个非常重要的开销成本（它不仅仅是一条跳转指令，因为尾调用最终变成在许多不太严格的环境中，例如尾调用经过大量优化的函数式语言运行时环境）。2) 很少有真正的 C# 方法可以合法地发出尾调用（其他语言鼓励具有更多尾递归的编码模式，许多严重依赖尾调用优化的实际上会进行全局重写（例如继续传递转换）以增加尾递归的数量）。3) 部分原因是 2)，C# 方法由于应该成功的深度递归而导致堆栈溢出的情况相当罕见。

综上所述，我们将继续研究这一点，我们可能会在编译器的未来版本中找到一些模式，在这些模式中发出 .tail 指令是有意义的。

By the way, as it has been pointed out, it is worth noting that tail recursion isoptimised on x64.

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

回答by Alexandre Brisebois

I was recently told that the C# compiler for 64 bit does optimize tail recursion.

我最近被告知 64 位的 C# 编译器确实优化了尾递归。

C# also implements this. The reason why it is not always applied, is that the rules used to apply tail recursion are very strict.

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

回答by naiem

You can use the trampoline techniquefor tail-recursive functions in C# (or Java). However, the better solution (if you just care about stack utilization) is to use this small helpermethod to wrap parts of the same recursive function and make it iterative while keeping the function readable.

您可以在 C#（或 Java）中对尾递归函数使用蹦床技术。但是，更好的解决方案（如果您只关心堆栈利用率）是使用这个小的辅助方法来包装同一递归函数的部分并使其迭代，同时保持函数的可读性。

回答by devinbost

C# does not optimize for tail-call recursion because that's what F# is for!

C# 没有针对尾调用递归进行优化，因为这就是 F# 的用途！

For some depth on the conditions that prevent the C# compiler from performing tail-call optimizations, see this article: JIT CLR tail-call conditions.

要深入了解阻止 C# 编译器执行尾调用优化的条件，请参阅这篇文章：JIT CLR 尾调用条件。

Interoperability between C# and F#

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

C# and F# interoperate very well, and because the .NET Common Language Runtime (CLR) is designed with this interoperability in mind, each language is designed with optimizations that are specific to its intent and purposes. For an example that shows how easy it is to call F# code from C# code, see Calling F# code from C# code; for an example of calling C# functions from F# code, see Calling C# functions from F#.

C# 和 F# 的互操作性非常好，并且因为 .NET 公共语言运行时 (CLR) 的设计考虑到了这种互操作性，所以每种语言的设计都针对其意图和目的进行了优化。有关显示从 C# 代码调用 F# 代码是多么容易的示例，请参阅从 C# 代码调用 F# 代码；有关从 F# 代码调用 C# 函数的示例，请参阅从 F#调用 C# 函数。

For delegate interoperability, see this article: Delegate interoperability between F#, C# and Visual Basic.

有关委托互操作性，请参阅这篇文章：在 F#、C# 和 Visual Basic 之间委托互操作性。

Theoretical and practical differences between C# and F#

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

Here is an article that covers some of the differences and explains the design differences of tail-call recursion between C# and F#: Generating Tail-Call Opcode in C# and F#.

这里有一篇文章涵盖了一些差异并解释了 C# 和 F# 之间尾调用递归的设计差异：在 C# 和 F# 中生成尾调用操作码。

Here is an article with some examples in C#, F#, and C++\CLI: Adventures in Tail Recursion in C#, F#, and C++\CLI

这是一篇包含 C#、F# 和 C++\CLI 示例的文章：C#、F# 和 C++\CLI中的尾递归历险记

The main theoretical difference is that C# is designed with loops whereas F# is designed upon principles of Lambda calculus. For a very good book on the principles of Lambda calculus, see this free book: Structure and Interpretation of Computer Programs, by Abelson, Sussman, and Sussman.

主要的理论区别是 C# 是用循环设计的，而 F# 是根据 Lambda 演算原理设计的。有关 Lambda 演算原理的一本非常好的书，请参阅这本免费书：计算机程序的结构和解释，Abelson、Sussman 和 Sussman 合着。

For a very good introductory article on tail calls in F#, see this article: Detailed Introduction to Tail Calls in F#. Finally, here is an article that covers the difference between non-tail recursion and tail-call recursion (in F#): Tail-recursion vs. non-tail recursion in F sharp.

有关 F# 中尾调用的非常好的介绍性文章，请参阅这篇文章：F# 中尾调用的详细介绍。最后，这里有一篇文章介绍了非尾递归和尾调用递归之间的区别（在 F# 中）：尾递归与非尾递归在 FSharp 中。

回答by lifestyle

As other answers mentioned, CLR does support tail call optimization and it seems it was under progressive improvements historically. But supporting it in C# has an open Proposalissue in the git repository for the design of the C# programming language Support tail recursion #2544.

正如其他答案所提到的，CLR 确实支持尾调用优化，而且它似乎在历史上一直在逐步改进。但是在 C# 中支持它在Proposalgit 存储库中存在一个未解决的问题，用于设计 C# 编程语言Support tail recursion #2544。

You can find some useful details and info there. For example @jaykrell mentioned

您可以在那里找到一些有用的详细信息和信息。例如@jaykrell 提到

Let me give what I know.

Sometimes tailcall is a performance win-win. It can save CPU. jmp is cheaper than call/ret It can save stack. Touching less stack makes for better locality.

Sometimes tailcall is a performance loss, stack win. The CLR has a complex mechanism in which to pass more parameters to the callee than the caller recieved. I mean specifically more stack space for parameters. This is slow. But it conserves stack. It will only do this with the tail. prefix.

If the caller parameters are stack-larger than callee parameters, it usually a pretty easy win-win transform. There might be factors like parameter-position changing from managed to integer/float, and generating precise StackMaps and such.

Now, there is another angle, that of algorithms that demand tailcall elimination, for purposes of being able to process arbitrarily large data with fixed/small stack. This is not about performance, but about ability to run at all.

让我说出我所知道的。

有时尾声是性能双赢。它可以节省CPU。jmp 比 call/ret 便宜 它可以节省堆栈。接触更少的堆栈可以实现更好的局部性。

有时尾调用是性能损失，堆栈赢。CLR 有一个复杂的机制，可以将比调用者接收到的参数更多的参数传递给被调用者。我的意思是专门为参数提供更多的堆栈空间。这很慢。但它节省了堆栈。它只会用尾巴来做到这一点。字首。

如果调用方参数的堆栈大于被调用方参数，则通常是一个非常简单的双赢转换。可能有一些因素，例如参数位置从托管更改为整数/浮点数，以及生成精确的 StackMap 等。

现在，还有另一个角度，即需要消除尾调用的算法，目的是能够处理具有固定/小堆栈的任意大数据。这与性能无关，而与运行能力有关。

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

另外让我提一下（作为额外信息），当我们使用System.Linq.Expressions命名空间中的表达式类生成编译的 lambda 时，有一个名为“tailCall”的参数，如其注释中所述，它是

A bool that indicates if tail call optimization will be applied when compiling the created expression.

一个布尔值，指示在编译创建的表达式时是否应用尾调用优化。

I was not tried it yet, and I am not sure how it can help related to your question, but Probably someone can try it and may be useful in some scenarios:

我还没有尝试过，我不确定它如何帮助解决您的问题，但可能有人可以尝试，并且在某些情况下可能有用：

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

var myFunc =  myFuncExpression.Compile();