为什么这个constexpr代码会导致GCC占用我所有的RAM？

Question

以下程序将调用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;
}

问题是吃掉我的RAM就是它的功能.当我将MAXD​​设置为30时,我的笔记本电脑在GCC 4.7.2快速分配3 gb左右后开始交换.我还没有尝试使用clang 3.1,因为我现在无法访问它.

我唯一的猜测是,这与GCC试图过于聪明并记住函数调用有关,就像它对模板一样.如果是这样的话,他们没有限制他们做多少memoization,如MRU缓存表的大小或其他东西,这似乎并不奇怪吗？我还没有找到一个禁用它的开关.

我为什么要这样做？我正在研究创建一个高级编译时库的想法,比如遗传编程或其他东西.由于编译器没有编译时尾部调用优化,我担心任何循环都需要递归(即使我调出最大递归深度参数,这看起来有点难看)将快速分配我的所有RAM和填充它与无意义的堆栈帧.因此,我想出了上面的解决方案,可以在没有深度堆栈的情况下获得任意多个函数调用.这种功能可用于折叠/循环或蹦床.

编辑:现在我已经在clang 3.1中尝试了它,它根本不会泄漏内存,无论我使它工作多久(即我制作MAXD有多高).CPU使用率几乎为100%,内存使用率几乎为0%,就像预期的那样.也许这只是GCC中的一个错误.

Answer 1

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

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

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