8

以下程序将调用fun 2 ^ (MAXD + 1) 次。不过，最大递归深度不应该超过 MAXD（如果我的想法是正确的）。因此编译可能需要一些时间，但它不应该吃掉我的 RAM。

#include<iostream>

const int MAXD = 20;

constexpr int fun(int x, int depth=0){
  return depth == MAXD ? x : fun(fun(x + 1, depth + 1) + 1, depth + 1);
}

int main(){
  constexpr int i = fun(1);
  std::cout << i << std::endl;
}

问题是吃我的内存正是它的作用。当我将 MAXD 提高到 30 时，我的笔记本电脑在 GCC 4.7.2 快速分配 3 GB 左右后开始交换。我还没有尝试使用 clang 3.1，因为我现在无法访问它。

我唯一的猜测是，这与 GCC 试图过于聪明并记住函数调用有关，就像它对模板所做的那样。如果是这样，他们没有限制他们做多少记忆似乎并不奇怪，比如 MRU 缓存表的大小或其他什么？我还没有找到禁用它的开关。

我为什么要这样做？我正在考虑制作一个高级编译时库的想法，比如基因编程之类的。由于编译器没有编译时尾调用优化，我担心任何循环都需要递归并且（即使我调高最大递归深度参数，这看起来有点难看）会快速分配我所有的 RAM 并填充它带有毫无意义的堆栈帧。因此，我想出了上述解决方案，用于在没有深堆栈的情况下获得任意多个函数调用。这样的功能可用于折叠/循环或蹦床。

编辑：现在我已经在clang 3.1中尝试过了，它根本不会泄漏内存，无论我让它工作多长时间（即我做MAXD多高）。CPU 使用率几乎是 100%，内存使用率几乎是 0%，正如预期的那样。也许这只是 GCC 中的一个错误。

4

2 回答 2

2

这可能不是关于 constexpr 的最终文档，但它是从gcc constexpr wiki 链接到的主要文档。

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2235.pdf

...它说...

我们（仍然）禁止常量表达式中所有形式的递归。这并不是绝对必要的，因为在常量表达式求值中对递归深度的实现限制将使我们免于编译器永远递归的可能性。然而，在我们看到一个令人信服的递归用例之前，我们不建议允许它。

所以，我希望你遇到语言边界和 gcc 选择实现 constexpr 的方式（可能试图内联生成整个函数，然后评估/执行它）

于 2012-11-16T09:30:08.580 回答
1

您的答案在您的评论中“通过运行函数运行时并观察到虽然我可以让它运行很长时间”，这是由您对 fun(x + 1, depth + 1) 的内部最递归调用引起的。

当您通过删除 constexpr 将其更改为运行时函数而不是编译时函数并观察到它运行了很长时间时，这表明它正在非常深入地递归。

当编译器执行该函数时，它必须深度递归，但不使用堆栈进行递归，因为它实际上并没有生成和执行机器代码。

于 2012-11-15T16:39:20.513 回答