120

末尾再帰を最適化する言語に関するこの質問を見つけました。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);
}
4

7 に答える 7

89

JIT コンパイルは、コンパイル フェーズにあまり時間を費やさないこと (したがって、短命のアプリケーションの速度が大幅に低下する) と、標準的な事前コンパイルでアプリケーションの競争力を長期的に維持するのに十分な分析を行わないこととの間のトリッキーなバランスをとる作業です。 .

興味深いことに、NGenのコンパイル手順は、最適化を積極的に行うことを目的としていません。これは、JIT または NGen がマシン コードを担当しているかどうかに依存して動作が発生するバグを単純に望んでいないためだと思われます。

CLR自体は末尾呼び出しの最適化をサポートしていますが、言語固有のコンパイラは関連するオペコードを生成する方法を認識している必要があり、JIT はそれを尊重する必要があります。 F# のwhilefsc は、関連するオペコードを生成します (単純な再帰の場合は、全体を直接ループに変換するだけかもしれません)。C# の csc はそうではありません。

詳細については、このブログ投稿を参照してください (最近の JIT の変更を考えると、かなり古い可能性があります)。4.0 では CLR が変更され、x86、x64、および ia64 がそれを尊重することに注意してください。

于 2009-01-29T12:42:15.690 に答える
81

このMicrosoft Connect フィードバックの提出は、あなたの質問に答える必要があります。マイクロソフトからの公式の回答が含まれているので、それに従うことをお勧めします。

提案をありがとう。C# コンパイラの開発の多くの時点で、テール コール命令を発行することを検討しました。ただし、これまでのところこれを回避するように促したいくつかの微妙な問題があります。末尾呼び出しが大幅に最適化されている関数型言語ランタイム環境など、それほど厳密ではない多くの環境で)。2) 末尾呼び出しを発行することが合法である実際の C# メソッドはほとんどありません (他の言語では、末尾再帰をより多く含むコーディング パターンが推奨されます。また、末尾呼び出しの最適化に大きく依存している多くの場合、実際にはグローバルな書き換え (Continuation Passing 変換など) を行って、末尾再帰の量を増やしています)。3) 2) のせいもあって、成功するはずの深い再帰によって C# メソッドのスタック オーバーフローが発生するケースはかなりまれです。

とはいえ、私たちは引き続きこれを調べており、コンパイラの将来のリリースで、.tail 命令を発行することが理にかなっているいくつかのパターンを見つけるかもしれません。

ところで、指摘されているように、末尾再帰がx64 で最適化されていることは注目に値します。

于 2009-01-29T12:34:11.213 に答える
17

C# は末尾呼び出し再帰を最適化しません。これが F# の目的だからです。

C# コンパイラが末尾呼び出しの最適化を実行できない条件の詳細については、次の記事を参照してください: JIT CLR 末尾呼び出し条件。

C# と F# の間の相互運用性

C# と F# は相​​互運用性が非常に高く、.NET 共通言語ランタイム (CLR) はこの相互運用性を念頭に置いて設計されているため、各言語はその意図と目的に固有の最適化を使用して設計されています。C# コードから F# コードを呼び出すことがいかに簡単かを示す例については、「C# コードから F# コードを呼び出す」を参照してください。F# コードから C# 関数を呼び出す例については、F# からC# 関数を呼び出すを参照してください。

デリゲートの相互運用性については、次の記事を参照してください: F#、C#、および Visual Basic 間のデリゲートの相互運用性。

C# と F# の理論的および実際的な違い

C# と F# の末尾呼び出し再帰のいくつかの違いを取り上げ、設計の違いを説明する記事を次に示します: C# と F# での末尾呼び出しオペコードの生成。

以下は、C#、F#、および C++\CLI のいくつかの例を含む記事です: C#、F#、および C++\CLIにおける末尾再帰の冒険

主な理論上の違いは、C# はループを使用して設計されているのに対し、F# はラムダ計算の原則に基づいて設計されていることです。ラムダ計算の原理に関する非常に優れた本については、この無料の本を参照してください: Structure and Interpretation of Computer Programs, by Abelson, Sussman, and Sussman .

F# でのテール コールに関する非常に優れた入門記事については、次の記事を参照してください: F# でのテール コールの詳細な紹介。最後に、非末尾再帰と末尾呼び出し再帰 (F# の場合) の違いをカバーする記事を次に示します。

于 2014-04-28T19:05:42.397 に答える
9

最近、64 ビット用の C# コンパイラは末尾再帰を最適化すると言われました。

C# もこれを実装しています。常に適用されるとは限らない理由は、末尾再帰の適用に使用される規則が非常に厳密であるためです。

于 2009-01-29T12:34:47.203 に答える
3

C# (または Java) では、末尾再帰関数にトランポリン手法を使用できます。ただし、より良い解決策 (スタックの使用率だけを気にする場合) は、この小さなヘルパーメソッドを使用して同じ再帰関数の一部をラップし、関数を読みやすくしながら反復的にすることです。

于 2012-05-23T11:52:11.863 に答える