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

Question

The following program will call fun 2 ^ (MAXD + 1) times. The maximum recursion depth should never go above MAXD, though (if my thinking is correct). Thus it may take some time to compile, but it should not eat 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 eating my RAM is exactly what it does. When I turn MAXD up to 30, my laptop starts to swap after GCC 4.7.2 quickly allocates 3 gb or so. I have not yet tried it with clang 3.1, as I don't have access to it right now.

My only guess is that this has something to do with GCC trying to be too clever and memoize the function calls, like it does with templates. If this is so, does it not seem strange that they don't have a limit on how much memoization they do, like the size of a MRU cache table or something? I have not found a switch to disable it.

Why would I do this? I am toying with the idea of making an advanced compile time library, like genetic programming or something. Since the compilers do not have compile time tail call optimization, I am worried that anything that loops will need recursion and (even if I turn up the maximum recursion depth parameter, which seems slightly ugly to require) will quickly allocate all my RAM and fill it with pointless stack frames. Thus I came up with the above solution for getting arbitrarily many function calls without a deep stack. Such a function could be used for folding/looping or trampolining.

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

Answer 1

This may not be the definitive document regarding constexpr, but it's the primary doc linked to from the gcc constexpr wiki.

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

... and it says...

We (still) prohibit recursion in all its form in constant expressions. That is not strictly necessary because an implementation limit on recursion depth in constant expression evaluation would save us from the possibility of the compiler recursing forever. However, until we see a convincing use case for recursion, we don’t propose to allow it.

So, I expect you're bumping up against language boundary and the way that gcc has chosen to implement constexpr (maybe attempting to generate the entire function inline, then evaluating/executing it)

Answer 2

Your answer is in your comment "by running the function runtime and observing that while I can make it run for a long time", which is caused by your inner most recursive call to fun(x + 1, depth + 1).

When you changed it to a runtime function rather than a compile time function by removing constexpr and observed that it ran a long time that's an indicator that it is recursing very deeply.

When the function is executed by the compiler it has to recurse deeply, but doesn't use the stack for recursion since it isn't actually generating and executing machine code.