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

以下程序将调用乐趣 2 ^（MAXD + 1）次。尽管（如果我的想法是正确的话），最大递归深度不应该超过MAXD。因此编译可能需要一些时间，但它不应该吃我的RAM。为什么这个constexpr代码会导致GCC吃掉我所有的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快速分配3GB左右后开始交换。我还没有尝试过与叮当3.1，因为我现在无法访问它。

我唯一的猜测是，这与GCC试图过于聪明并且记忆函数调用有关，就像模板一样。如果是这样的话，他们没有限制他们做多少记忆，例如MRU高速缓存表的大小或什么的没有限制吗？我还没有找到一个开关来禁用它。

为什么要这样做？我喜欢制作高级编译时间库的想法，比如遗传编程或其他东西。由于编译器没有编译时间尾部调用优化，所以我担心任何循环都需要递归，并且（即使我调出最大递归深度参数，这似乎有点难以要求）会快速分配所有的RAM并填充它与毫无意义的堆栈帧。因此，我提出了上述解决方案，可以在没有深度堆栈的情况下获取任意多个函数调用。这种功能可以用于折叠/循环或蹦床。

编辑：现在我已经在3.1版中尝试过了，不管我多长时间工作（即MAXD有多高），它都不会泄漏内存。与预期的一样，CPU使用率几乎为100％，内存使用率几乎为0％。也许这只是GCC中的一个bug。

来源

2012-11-15 Gurgeh

我已确认堆栈永远不会超越MAXD（如预期的那样），通过运行函数运行时并观察到，尽管我可以使其运行很长时间，但它根本不使用RAM。 – Gurgeh

可能您应该按照http://gcc.gnu.org/bugs/中的建议报告此问题吗？ – osgx

@osgx这不是一个真正的bug，不过，是吗？根据标准，我想他们可以对我的RAM做他们喜欢的事情。另外，我希望有人知道他们在做什么（你知道你是谁），告诉我是什么原因。 – Gurgeh

你的回答是在你的评论“通过运行函数运行时，并观察到，虽然我可以让它运行很长时间”，这是由你最内在的递归调用fun（x + 1，depth + 1 ）。

当您通过删除constexpr将其更改为运行时函数而非编译时函数并观察它运行了很长时间，这是一个指示器，它正在递归得非常深。

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

来源

2012-11-15 16:39:20

当然会。它返回很好。你有没有尝试过的代码？ – Gurgeh

深度递归不是唯一可以长时间运行的方法。它也可以广泛分支，这就是我的代码所做的。 – Gurgeh

您的代码不能广泛分支。它只有一个分支，它在每次递归时都采用分支的同一侧，直到它停止递归。 –

这可能不是关于constexpr明确的文件，但它是从gcc constexpr wiki.

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

链接到初级文档...和它说...

我们（仍然）在常量表达式中禁止所有形式的递归。这不是严格必要的，因为在常量表达式评估中递归深度的实现限制可以节省我们从到编译器永远递归的可能性。然而，直到我们看到一个令人信服的递归用例，我们不打算允许它。

所以，我希望你都撞在语言边界和海湾合作委员会已选择实施constexpr的方式（也许试图生成整个函数内联，然后评估/执行它）

来源

2012-11-16 09:30:08 Roddy

@Downvoter - 谨慎解释？ – Roddy

我认为该文档太旧了。该标准并不禁止递归，但是建议512次递归的默认限制，gcc和clang都尊重，但允许用户覆盖。你可能是对的，这个问题不是记忆（尽管我知道gcc对constexprs这么做），但它扩展了内联代码。 – Gurgeh

@Gurgeh - 是的 - 对于ISO标准来说，这似乎是一个常见的问题，除了实际的标准本身，Web分散在每一个可能的文档中:-)对“递归次数”或递归深度的推荐限制是什么？就像你的情况一样，深度是20，但是“递归次数”可以被认为是2^MAXD-1，如你所说... – Roddy

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

回答

相关问题