可以对constexpr函数进行尾递归优化 [英] Can constexpr function evaluation do tail recursion optimization

问题描述

我想知道对于长循环，我们可以利用C ++ 11中的constexpr的尾递归吗？

I wonder whether for long loops we can take advantage of tail recursion for constexpr in C++11?

推荐答案

[implimits] 中的规则，允许实现对 constexpr 计算放置递归深度限制。具有完整 constexpr 实现（gcc和clang）的两个编译器都应用这样的限制，使用标准建议的默认的512个递归调用。对于这两个编译器，以及遵循标准建议的任何其他实现，尾递归优化基本上是不可检测的（除非编译器否则在达到其递归限制之前崩溃）。

By the rules in [implimits], an implementation is permitted to put a recursion depth limit on constexpr calculations. The two compilers which have complete constexpr implementations (gcc and clang) both apply such a limit, using the default of 512 recursive calls as suggested by the standard. For both of these compilers, as well as any other implementation which follows the standard's suggestion, a tail recursion optimization would be essentially undetectable (unless the compiler would otherwise crash before reaching its recursion limit).

一个实现可以改为选择仅对其在递归深度限制中不能应用尾递归优化的调用进行计数，或者不提供这样的限制。但是，这样的实现可能会损害其用户，因为它可能崩溃（由于堆栈溢出）或无法终止 constexpr 评估

An implementation could instead choose to only count calls for which it could not apply a tail-recursion optimization in its recursion depth limit, or to not provide such a limit. However, such an implementation would probably be doing a disservice to its users, since it would be likely to either crash (due to a stack overflow) or fail to terminate on constexpr evaluations which recurse deeply or infinitely.

关于在达到递归深度限制时会发生什么，Pubby的例子引发了一个有趣的问题。 [expr.const] p2 指定

With regard to what happens when the recursion depth limit is reached, Pubby's example raises an interesting point. [expr.const]p2 specifies that

调用constexpr函数一个超出实现定义的递归限制的constexpr构造函数（见附录B）;

an invocation of a constexpr function or a constexpr constructor that would exceed the implementation-defined recursion limits (see Annex B);

不是常量表达式。因此，如果在需要常量表达式的上下文中达到递归限制，则程序是不成形的。如果在不需要常量表达式的上下文中调用 constexpr 函数，则通常不需要实现在翻译时评估它，但是如果它选择，并且达到递归限制，则需要在运行时执行调用。在完整的可编译测试程序上：

is not a constant expression. Therefore, if the recursion limit is reached in a context which requires a constant expression, the program is ill-formed. If a constexpr function is called in a context which does not require a constant expression, the implementation is not generally required to attempt to evaluate it at translation time, but if it chooses to, and the recursion limit is reached, it is required to instead perform the call at runtime. On a complete, compilable test program:

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);
                                 ^

如果我们修改代码，以便在翻译时不需要进行评估时间：

If we modify the code so that the evaluation is not required to occur at translation time:

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 evaluation）。

then both compilers accept it, and generate code which computes the result at runtime. When building with -O0, this code fails due to stack overflow. When building with -O2, the compilers' optimizers transform the code to use tail recursion and the code functions correctly (but note that this tail recursion is unrelated to constexpr evaluation).

这篇关于可以对constexpr函数进行尾递归优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！