Why does this constexpr code force GCC to eat all of my RAM?

Question

The following program will cause fun 2 ^ (MAXD + 1) times. The maximum recursion depth should never exceed MAXD, though (if my thinking is correct). Thus, it may take some time to compile, but it should not have my 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; } 

The problem is that there is my RAM - this is exactly what it does. When I transfer MAXD to 30, my laptop starts replacing after GCC 4.7.2 quickly allocates 3 GB or so. I have not tried this with clang 3.1 since I do not have access to it right now.

My only assumption is that it has something to do with the fact that GCC is trying to be too smart and memoize function calls, as it happens with templates. If so, doesn’t it seem strange that they have no limit to how many memos they do, for example, the size of the MRU cache table or something else? I did not find a switch to turn it off.

Why should I do this? I play with the idea of ​​creating an advanced compile-time library such as genetic programming or something like that. Since compilers do not have optimized compilation tail processing time, I worry that all that loops will require recursion and (even if I go back to the maximum recursion depth parameter, which seems a little ugly to require) will quickly allocate all of my RAM and it will populate with meaningless stack frames. So I came up with the above solution to get arbitrarily many function calls without a deep stack. Such a function can be used for bending / looping or springboard.

EDIT: Now I tried this in clang 3.1 and it will not leak memory at all, no matter how long I make it work (that is, how high I do MAXD). CPU usage is almost 100%, and memory usage is almost 0%, as expected. Perhaps this is just a bug in GCC.

Answer 1

This may not be the final document regarding constexpr, but it is the primary document related to the gcc constexpr wiki.

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

... and he says ...

We (nevertheless) prohibit recursion in all its form in constant expressions. This is not strictly necessary, since the limit of implementation to the depth of the recursion in the constant evaluation of the expression will save us from the possibility of recompiling the compiler forever. However, while we see a convincing precedent for recursion, we do not propose to allow it.

So, I expect that you will come across a language boundary and the way gcc decided to implement constexpr (maybe try to generate the whole built-in function, then evaluate / execute it)

Answer 2

Your answer is in your comment, "by running the runtime of the function and observing that although I can make it work for a long time", which is caused by your inner most recursive appeal for entertainment (x + 1, depth + 1).

When you change it to a run-time function, rather than a compile-time function, removing constexpr and noticing that for a long time it starts an indicator, which it recurses very deeply.

When a function is executed by the compiler, it must be written deeply, but does not use the stack for recursion, since it does not actually generate or execute machine code.