Warum bewirkt dieser constexpr-Code, dass GCC all meinen RAM verbraucht?

Question

Das folgende Programm ruft Spaß 2^(MAXD + 1) mal auf. Die maximale Rekursionstiefe sollte jedoch niemals über MAXD hinausgehen (wenn mein Denken korrekt ist). Daher kann es einige Zeit dauern, um zu kompilieren, aber es sollte nicht meinen RAM essen.

#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; 
} 

Das Problem ist, dass Essen mein RAM ist genau das, was es tut. Wenn ich MAXD auf 30 stelle, beginnt mein Laptop zu tauschen, nachdem GCC 4.7.2 schnell 3 GB zugewiesen hat. Ich habe es noch nicht mit clang 3.1 probiert, da ich momentan keinen Zugriff darauf habe.

Meine einzige Vermutung ist, dass dies etwas damit zu tun hat, dass GCC versucht, zu clever zu sein und die Funktionsaufrufe zu protokollieren, wie es bei Vorlagen der Fall ist. Wenn das so ist, scheint es nicht seltsam, dass sie keine Begrenzung haben, wie viel Memoization sie tun, wie die Größe einer MRU-Cache-Tabelle oder etwas? Ich habe keinen Schalter gefunden, um es zu deaktivieren.

Warum sollte ich das tun? Ich spiele mit der Idee, eine erweiterte Kompilierzeitbibliothek zu erstellen, wie genetische Programmierung oder so etwas. Da die Compiler keine Kompilierzeit-Tail-Call-Optimierung haben, mache ich mir Sorgen, dass alles, was Schleifen benötigt Rekursion und (auch wenn ich die maximale Rekursion Tiefe Parameter, die etwas hässlich zu erfordern scheint) schnell alle meine RAM zuweisen und füllen es mit sinnlosen Stapelrahmen. Daher habe ich die obige Lösung gefunden, um beliebig viele Funktionsaufrufe ohne einen Deep Stack zu erhalten. Eine solche Funktion könnte zum Falten/Schleifen oder Trampolinspringen verwendet werden.

EDIT: Jetzt habe ich es in Clang 3.1 versucht, und es wird Speicher überhaupt nicht auslaufen, egal wie lange ich es arbeiten (d. H. Wie hoch ich MAXD machen). Die CPU-Auslastung beträgt fast 100% und die Speicherauslastung beträgt wie erwartet fast 0%. Vielleicht ist das nur ein Fehler in GCC.

Answer 1

Ihre Antwort ist in Ihrem Kommentar "durch Ausführen der Funktion Runtime und beobachten, dass, während ich es für eine lange Zeit ausführen kann", die von Ihrem innersten rekursiven Aufruf an Spaß verursacht wird (x + 1, Tiefe + 1).

Wenn Sie es in eine Laufzeitfunktion anstelle einer Kompilierzeitfunktion geändert haben, indem Sie conexpr entfernt haben, und festgestellt haben, dass es lange gedauert hat, ist das ein Hinweis darauf, dass es sehr tief rekurriert.

Wenn die Funktion vom Compiler ausgeführt wird, muss sie tief recursen, aber sie verwendet den Stack nicht zur Rekursion, da sie keinen Maschinencode erzeugt und ausführt.

Answer 2

Dies kann nicht das endgültige Dokument über constexpr sein, aber es ist die primäre doc verknüpfen aus dem gcc constexpr wiki.

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

... und es sagt ...

Wir (immer noch) Rekursion in ihrer ganzen Form in konstanten Ausdrücken zu verbieten. Das ist nicht unbedingt notwendig, da ein Implementierungslimit auf Rekursionstiefe bei der Auswertung von konstanten Ausdrücken uns von die Möglichkeit des Compilers für immer rekursiv speichern würde. Bis wir jedoch einen überzeugenden Anwendungsfall für Rekursion sehen, schlagen wir nicht vor, dies zuzulassen.

Also erwarte ich, dass Sie stoßen gegen Sprachgrenze und die Art und Weise, dass gcc constexpr zu implementieren hat sich dafür entschieden (vielleicht die gesamte Funktion inline zu erzeugen versucht, dann Auswerten/Ausführen it)