18

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

4

5 回答 5

21

根据 中的规则[implimits]，允许实现对constexpr计算设置递归深度限制。具有完整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);

海湾合作委员会 说：

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)

铿锵声 说：

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

我不明白为什么它不可能，但这是实现细节的质量。

例如，对模板使用 memoization 是传统的做法，这样编译器就不会再窒息了：

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。如果是递归函数是否可以是 a 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函数更接近于数学函数。对于数学函数，以下两个函数是相同的：

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;
}

但从程序编程的角度来看，它们绝对不是。只有第一个似乎适合尾调用优化。

于 2012-02-13T11:44:04.390 回答