160

C と C++ の両方で末尾再帰の最適化を行うと完全にうまくいくように思えますが、デバッグ中に、この最適化を示すフレーム スタックが表示されないようです。スタックが再帰の深さを教えてくれるので、これは良いことです。ただし、最適化も同様に優れています。

この最適化を行う C++ コンパイラはありますか? なんで？なぜだめですか？

コンパイラにそれを行うように指示するにはどうすればよいですか?

  • MSVC の場合:/O2または/Ox
  • GCC の場合:-O2または-O3

特定のケースでコンパイラがこれを行ったかどうかを確認するのはどうですか?

  • MSVC の場合、PDB 出力を有効にしてコードをトレースできるようにしてから、コードを検査します。
  • GCCの場合..?

特定の関数がコンパイラによってこのように最適化されているかどうかを判断する方法については、引き続き提案を行います（Konradがそれを想定するように指示してくれたので安心しましたが）

無限再帰を作成し、無限ループまたはスタック オーバーフローが発生するかどうかを確認することで、コンパイラがこれを行うかどうかを常に確認できます (GCC でこれを行い、それで-O2十分であることがわかりました)。とにかく終了することがわかっている特定の機能を確認できます。これを簡単に確認する方法があれば幸いです:)

いくつかのテストの後、デストラクタがこの最適化を行う可能性を台無しにすることを発見しました。特定の変数と一時変数のスコープを変更して、return ステートメントが開始される前にそれらが確実にスコープ外になるようにすることは、価値がある場合があります。

末尾呼び出しの後にデストラクタを実行する必要がある場合、末尾呼び出しの最適化は実行できません。

4

5 に答える 5

139

現在の主流のコンパイラはすべて、次のような相互再帰呼び出しに対しても、末尾呼び出しの最適化をかなりうまく実行します (そして 10 年以上実行しています) 。

int bar(int, int);

int foo(int n, int acc) {
    return (n == 0) ? acc : bar(n - 1, acc + 2);
}

int bar(int n, int acc) {
    return (n == 0) ? acc : foo(n - 1, acc + 1);
}

コンパイラーに最適化をさせるのは簡単です: 速度のために最適化をオンにするだけです:

  • MSVC の場合は、/O2またはを使用します/Ox。
  • GCC、Clang、および ICC の場合は、次を使用します-O3

コンパイラが最適化を行ったかどうかを確認する簡単な方法は、スタック オーバーフローが発生する呼び出しを実行するか、アセンブリの出力を確認することです。

興味深い歴史的なメモとして、C のテール コールの最適化は、Mark Probst による卒業論文の過程で GCC に追加されました。この論文では、実装におけるいくつかの興味深い注意事項について説明しています。読む価値があります。

于 2008-08-29T07:40:32.280 に答える
21

gcc 4.3.2 は、この関数 (くだらない/些細なatoi()実装) を に完全にインライン化しmain()ます。最適化レベルは-O1です。それをいじってみると気がつきます ( からstaticに変更してもextern、末尾の再帰はかなり速く消えてしまうので、プログラムの正確さについてはそれに依存しません。

#include <stdio.h>
static int atoi(const char *str, int n)
{
    if (str == 0 || *str == 0)
        return n;
    return atoi(str+1, n*10 + *str-'0');
}
int main(int argc, char **argv)
{
    for (int i = 1; i != argc; ++i)
        printf("%s -> %d\n", argv[i], atoi(argv[i], 0));
    return 0;
}
于 2008-10-21T03:13:20.523 に答える
21

明らかなこと (コンパイラーは、ユーザーが要求しない限り、この種の最適化を行いません) と同様に、C++ での末尾呼び出しの最適化には、デストラクタという複雑さがあります。

次のようなものが与えられます：

   int fn(int j, int i)
   {
      if (i <= 0) return j;
      Funky cls(j,i);
      return fn(j, i-1);
   }

再帰呼び出しが戻ったcls 後にデストラクタを呼び出す必要があるため、コンパイラはこれを末尾呼び出しで最適化することはできません (一般に) 。

コンパイラは、デストラクタに外部から見える副作用がないことを確認できる場合がありますが (そのため、早期に実行できます)、多くの場合、そうではありません。

これの特に一般的な形式は、Funky実際には where is astd::vectorまたは similar です。

于 2016-02-26T10:28:46.927 に答える
11

ほとんどのコンパイラは、デバッグ ビルドでいかなる種類の最適化も行いません。

VC を使用している場合は、PDB 情報をオンにしてリリース ビルドを試してください。これにより、最適化されたアプリをトレースできるようになり、必要なものが表示されるはずです。ただし、最適化されたビルドのデバッグとトレースを行うと、あちこち飛び回ることになることに注意してください。多くの場合、変数は最終的にレジスタに格納されるか、完全に最適化されてしまうため、変数を直接検査することはできません。それは「面白い」経験です...

于 2008-08-29T07:48:26.940 に答える
7

グレッグが述べているように、コンパイラはデバッグモードではそれを行いません。デバッグビルドがprodビルドよりも遅くても問題ありませんが、頻繁にクラッシュすることはありません。末尾呼び出しの最適化に依存している場合は、まさにそれを行う可能性があります。このため、多くの場合、末尾呼び出しを通常のループとして書き直すのが最適です。:-(

于 2008-09-16T10:42:07.840 に答える