当前位置： 文江博客话题详情

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

发布于 2024-07-12 12:52:31 字数 499 浏览 7 评论 0原文

我发现这个问题关于哪些语言优化尾递归。 为什么 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);
}
原文

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

For a concrete case, why isn't this method optimized into a loop (Visual Studio 2008 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);
}

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（7）

疧_╮線 2024-07-19 12:52:31

JIT 编译是一种棘手的平衡行为，既不花太多时间进行编译阶段（从而大大减慢短期应用程序的速度），又不进行足够的分析以通过标准提前编译保持应用程序的长期竞争力。 。

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

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

请参阅此博文了解一些详细信息（很可能现在已经过时了）考虑到最近的 JIT 变化）。 请注意，4.0 的 CLR 发生了变化 x86、x64 和 ia64 将尊重它。

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.

Interestingly the NGen compilation 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.

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

See this blog post for 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.

回复 原文
暖伴 2024-07-19 12:52:31

这Microsoft Connect 反馈提交应该可以回答您的问题。 它包含 Microsoft 的官方回复，因此我建议您遵循该回复。

谢谢你的建议。 我们已经
考虑发出尾调用
中多个点的说明
C#编译器的开发。
然而，还有一些微妙的问题
这促使我们避免这种情况，所以
远：1）实际上有一个
使用的开销成本不菲
CLR 中的 .tail 指令（它是
不仅仅是尾部的跳转指令
通话最终变得更少
严格的环境，例如功能
语言运行时环境
尾部调用经过大量优化）。 2）
真正的 C# 方法很少
发出尾调用是合法的
（其他语言鼓励编码
有更多尾巴的图案
递归，以及许多严重依赖
尾部调用优化实际上是这样做的
全局重写（如
连续传递变换）
增加尾部的数量
递归）。 3) 部分原因是 2),
C# 方法堆栈溢出的情况
由于深度递归应该有
成功的情况相当罕见。

综上所述，我们继续关注
这，我们可能会在未来的版本中
编译器发现一些模式
在有意义的地方发出 .tail
说明。

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

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

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.

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

回复 原文
纸伞微斜 2024-07-19 12:52:31

C# 不会针对尾部调用递归进行优化，因为这正是 F# 的用途！

有关阻止 C# 编译器执行尾调用优化的条件的深入信息，请参阅本文：JIT CLR 尾部调用条件。

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

C# 和 F# 的互操作性非常好，并且由于 .NET 公共语言运行时 (CLR) 在设计时就考虑到了这种互操作性，因此每种语言都根据其特定意图进行了优化和目的。 有关说明从 C# 代码调用 F# 代码是多么容易的示例，请参阅调用 F#来自 C# 代码的代码； 有关从 F# 代码调用 C# 函数的示例，请参阅从 F# 调用 C# 函数。

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

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

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

以下文章包含一些 C#、F# 和 C++\CLI 示例： C#、F# 和 C++\CLI 中的尾递归历险

主要的理论区别是 C# 设计有循环，而 F# 设计有循环基于 Lambda 演算原理。 有关 Lambda 演算原理的好书，请参阅这本免费书：计算机程序的结构和解释，作者：Abelson 、萨斯曼和萨斯曼。

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

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

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

Interoperability between C# and 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#.

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

Theoretical and practical differences between C# and 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#.

Here is an article with some examples in C#, F#, and C++\CLI: Adventures in Tail Recursion in C#, F#, and 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.

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.

回复 原文
梦冥 2024-07-19 12:52:31

最近有人告诉我，64 位的 C# 编译器确实优化了尾递归。

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

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

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

回复 原文
紫轩蝶泪 2024-07-19 12:52:31

今天我有一个惊喜:-)

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

我正在使用 NET5 和 LINQPad 6（已激活优化）。

这是我使用的 Tail 调用可优化阶乘函数：

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

这是为此函数生成的 X64 汇编代码：

汇编代码

看，没有call，只有一个jmp. 该函数也被积极优化（无堆栈帧设置/拆卸）。 哦是的！

I had a happy surprise today :-)

I am reviewing my teaching material for my upcoming course on recursion with C#.
And it seems that finally tail call optimization has made its way into C#.

I am using NET5 with LINQPad 6 (optimization activated).

Here is the Tail call optimizable Factorial function I used:

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

And here is the X64 assembly code generated for this function:

Assembly code

See, there is no call, only a jmp. The function is agressively optimized as well (no stack frame setup/teardown). Oh Yes!

回复 原文
云柯 2024-07-19 12:52:31

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

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

回复 原文
七婞 2024-07-19 12:52:31

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

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

让我说说我所知道的。

有时尾调用是性能双赢。 它可以节省CPU。 jmp 是
比 call/ret 便宜 它可以节省堆栈。 接触更少的堆栈使得
更好的地点。

有时尾调用是性能损失，堆栈胜利。
CLR 有一个复杂的机制，可以将更多参数传递给
被调用者收到的消息比调用者收到的消息多。 我的意思是更多的堆栈
参数空间。 这很慢。 但它节省了堆栈。 它会
仅对尾巴执行此操作。 前缀。

如果调用者参数是
堆栈比被调用者参数大，通常是一个非常容易的双赢
转换。 可能有参数位置改变等因素
从托管到整数/浮点，并生成精确的 StackMap 和
这样。

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

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

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

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


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

var myFunc =  myFuncExpression.Compile();

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 Proposal issue in the git repository for the design of the C# programming language Support tail recursion #2544.

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

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.

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

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();
回复 原文
~没有更多了~

关于作者

烂柯人

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

隔纱相望

文章 0 评论 0

昵称有卵用

文章 0 评论 0

梨涡

文章 0 评论 0

蓝咒

文章 0 评论 0

白芷

文章 0 评论 0

樱娆

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文