18

長いループの場合、C++11 で constexpr の末尾再帰を利用できるのだろうか?

4

5 に答える 5

21

のルールにより[implimits]、実装は計算に再帰深度制限を設定することが許可されていconstexprます。完全な実装を持つ2つのコンパイラconstexpr（gccとclang）は両方とも、標準で提案されているデフォルトの512の再帰呼び出しを使用して、このような制限を適用します。これらのコンパイラの両方、および標準の提案に従う他の実装の場合、末尾再帰の最適化は本質的に検出できません（コンパイラが再帰制限に達する前にクラッシュしない限り）。

代わりに、実装は、再帰の深さの制限で末尾再帰の最適化を適用できなかった呼び出しのみをカウントするか、そのような制限を提供しないかを選択できます。constexprただし、そのような実装は、（スタックオーバーフローが原因で）クラッシュするか、深くまたは無限に繰り返される評価で終了しない可能性があるため、ユーザーに不利益をもたらす可能性があります。

再帰の深さの制限に達したときに何が起こるかに関して、Pubbyの例は興味深い点を提起します。[expr.const]p2それを指定します

実装で定義された再帰制限を超えるconstexpr関数またはconstexprコンストラクターの呼び出し（付録Bを参照）。

定数式ではありません。したがって、定数式を必要とするコンテキストで再帰制限に達した場合、プログラムの形式は正しくありません。constexpr定数式を必要としないコンテキストで関数が呼び出された場合、実装は通常、変換時に関数を評価しようとする必要はありませんが、関数が評価することを選択し、再帰制限に達した場合は、代わりに実行する必要があります。実行時の呼び出し。完全でコンパイル可能なテストプログラムの場合：

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) {
  return n ? f(n-1,s+n) : s;
}
constexpr unsigned long long k = f(0xffffffff);

GCCは言う：

depthlimit.cpp:4:46:   in constexpr expansion of ‘f(4294967295ull, 0ull)’
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
[... over 500 more copies of the previous message cut ...]
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
depthlimit.cpp:4:46: error: constexpr evaluation depth exceeds maximum of 512 (use -fconstexpr-depth= to increase the maximum)

そしてclangは言う：

depthlimit.cpp:4:30: error: constexpr variable 'k' must be initialized by a constant expression
constexpr unsigned long long k = f(0xffffffff);
                             ^   ~~~~~~~~~~~~~
depthlimit.cpp:2:14: note: constexpr evaluation exceeded maximum depth of 512 calls
  return n ? f(n-1,s+n) : s;
             ^
depthlimit.cpp:2:14: note: in call to 'f(4294966784, 2194728157440)'
depthlimit.cpp:2:14: note: in call to 'f(4294966785, 2190433190655)'
depthlimit.cpp:2:14: note: in call to 'f(4294966786, 2186138223869)'
depthlimit.cpp:2:14: note: in call to 'f(4294966787, 2181843257082)'
depthlimit.cpp:2:14: note: in call to 'f(4294966788, 2177548290294)'
depthlimit.cpp:2:14: note: (skipping 502 calls in backtrace; use -fconstexpr-backtrace-limit=0 to see all)
depthlimit.cpp:2:14: note: in call to 'f(4294967291, 17179869174)'
depthlimit.cpp:2:14: note: in call to 'f(4294967292, 12884901882)'
depthlimit.cpp:2:14: note: in call to 'f(4294967293, 8589934589)'
depthlimit.cpp:2:14: note: in call to 'f(4294967294, 4294967295)'
depthlimit.cpp:4:34: note: in call to 'f(4294967295, 0)'
constexpr unsigned long long k = f(0xffffffff);
                                 ^

翻訳時に評価を行う必要がないようにコードを変更する場合：

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) {
  return n ? f(n-1,s+n) : s;
}
int main(int, char *[]) {
  return f(0xffffffff);
}

次に、両方のコンパイラがそれを受け入れ、実行時に結果を計算するコードを生成します。でビルドする場合-O0、スタックオーバーフローが原因でこのコードは失敗します。を使用してビルドする-O2場合、コンパイラのオプティマイザは、末尾再帰を使用するようにコードを変換し、コードは正しく機能します（ただし、この末尾再帰はconstexpr評価とは無関係であることに注意してください）。

于 2012-02-16T23:49:45.563 に答える
4

なぜそれが不可能なのかわかりませんが、それは実装の詳細の質です。

たとえば、テンプレートにメモ化を使用することは伝統的であり、コンパイラーはもはや窒息しません。

template <size_t N>
struct Fib { static size_t const value = Fib <N-1>::value + Fib<N-2>::value; };

template <>
struct Fib<1> { static size_t const value = 1; }

template <>
struct Fib<0> { static size_t const value = 0; }

代わりに、すでに計算された値をメモして、その評価の複雑さを O(N) に減らします。

末尾再帰 (および疑似末尾再帰) は最適化であり、ほとんどの最適化と同様に標準の対象ではないため、それが不可能な理由はありません。ただし、特定のコンパイラがそれを使用するかどうかを予測するのは困難です。

標準は 5.19 [expr.const]で次のように述べています。

2/条件式は、潜在的に評価される部分式として次のいずれかを含まない限り、コア定数式です (3.2) [...]:

  • 実装定義の再帰制限を超える constexpr 関数または constexpr コンストラクターの呼び出し (付録 B を参照)。

そして附属書Bを読む：

2/ 制限により、以下に説明するものやその他のものを含む数量が制限される場合があります。各数量に続く括弧内の数字は、その数量の最小値として推奨されます。ただし、これらの量は単なるガイドラインであり、準拠を決定するものではありません。

  • 再帰的な constexpr 関数の呼び出し [512]。

末尾再帰はブローチされていません。

于 2012-02-13T10:45:19.267 に答える
2

あなたが何を求めているのかよくわかりません。コンパイラが末尾再帰をループに変換するかどうかに関係する場合は、関数が a であるかどうかに関係なく、未指定constexprです。再帰関数が になり得るかどうかである場合、constexpr末尾再帰は関係ないと思います。標準を正しく読んだ場合：

constexpr unsigned ack( unsigned m, unsigned n )
{
    return m == 0
        ? n + 1
        : n == 0
        ? ack( m - 1, 1 )
        : ack( m - 1, ack( m, n - 1 ) );
}

は有効な constexpr です (ただし、少なくとも関数が定数式を必要とするコンテキストで使用されている場合、最小のnandを除くすべてのリソースの不足についてコンパイラが文句を言うと思います)。m

于 2012-02-13T11:10:10.033 に答える
-1

GCC がこの最適化を実行するのを見てきました。次に例を示します。

constexpr unsigned long long fun1(unsigned long long n, unsigned long long sum = 0) {
  return (n != 0) ? fun1(n-1,sum+n) : sum;
}
fun1(0xFFFFFFFF);

-O2 で動作しますが、それ以外の場合はクラッシュします。

驚くべきことに、これも最適化しています。

constexpr unsigned long long fun2(unsigned long long n) {
  return (n != 0) ? n + fun2(n-1) : 0;
}

非 conspexpr フォームの逆アセンブルを確認したところ、ループに最適化されていることが確認できました。

しかし、これではありません：

constexpr unsigned long long fun3(unsigned long long n) {
  return (n != 0) ? n + fun3(n-1) + fun3(n-1) : 0;
}

したがって、結論として、GCC は非 consexpr 関数の場合と同じようにループに最適化します。少なくとも -O2 以上を使用してください。

于 2012-02-13T10:33:31.780 に答える
-2

「テールコール」は、おそらく最初は誤称です。constexpr関数は数学関数に非常に近いです。数学関数の場合、次の 2 つの関数は同一です。

constexpr unsigned long long fun1(unsigned long long n) {
  if (n == 0) return 0 ;
  return n + fun1(n-1);
}
constexpr unsigned long long fun2(unsigned long long n) {
  if (n != 0) return n + fun2(n-1);
  return  0;
}

しかし、手続き型プログラミングの観点からは、そうではありません。テール コールの最適化に役立つように見えるのは、最初の 1 つだけです。

于 2012-02-13T11:44:04.390 に答える