Dlaczego ten kod constexpr powoduje, że GCC pobiera całą moją pamięć RAM?

Question

Następujący program zadzwoni pod numer fun 2^(MAXD + 1) razy. Maksymalna głębokość rekursji nigdy nie powinna przekraczać MAXD (jeśli moje myślenie jest poprawne). W związku z tym kompilacja może zająć trochę czasu, ale nie powinna jeść mojej pamięci 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; 
} 

Problem polega na tym, że jedzenie mojej pamięci RAM jest dokładnie tym, co robi. Kiedy zmieniam MAXD na 30, mój laptop zaczyna się zamieniać po GCC 4.7.2 szybko przydziela 3 GB lub tak. Jeszcze nie próbowałem tego z clang 3.1, ponieważ nie mam do niego dostępu w tej chwili.

My się tylko domyślać, że ma to coś wspólnego z GCC stara się być zbyt mądry i memoize wywołania funkcji, jak to robi z szablonów. Jeśli tak jest, czy nie wydaje się dziwne, że nie mają limitu na to, ile robią na pamięć, jak na przykład wielkość tabeli pamięci podręcznej MRU? Nie znalazłem przełącznika, aby go wyłączyć.

Dlaczego miałbym to zrobić? Mam do czynienia z pomysłem stworzenia zaawansowanej biblioteki czasu kompilacji, takiej jak programowanie genetyczne lub coś takiego. Ponieważ kompilatory nie mają optymalizacji połączeń w czasie kompilacji, martwię się, że wszystkie pętle będą wymagać rekursji i (nawet jeśli ustawię maksymalny parametr głębokości rekursji, który wydaje się nieco brzydki), szybko przydzielę całą moją pamięć RAM i wypełnienie to z bezcelowymi ramkami stosu. Tak więc wymyśliłem powyższe rozwiązanie, aby uzyskać dowolnie wiele wywołań funkcji bez głębokiego stosu. Taką funkcję można wykorzystać do składania/zapętlania lub trampolinowania.

EDYTOWANIE: Teraz próbowałem go w klang 3.1, i nie wycieka wcale pamięci, bez względu na to, jak długo działam (tj. Jak wysoko robię MAXD). Wykorzystanie procesora wynosi prawie 100%, a zużycie pamięci wynosi prawie 0%, tak jak oczekiwano. Być może to tylko błąd w GCC.

Answer 1

Twoja odpowiedź jest w twoim komentarzu "przez uruchomienie środowiska wykonawczego funkcji i obserwowanie, że podczas gdy mogę sprawić, aby działał przez długi czas", co jest spowodowane przez twoje wewnętrzne najbardziej rekurencyjne wezwanie do zabawy (x + 1, głębokość + 1).

Kiedy zmieniłeś go na funkcję runtime, a nie na funkcję czasu kompilacji przez usunięcie constexpr i zaobserwowano, że działał przez długi czas, jest to wskaźnik, który powtarza się bardzo głęboko.

Gdy funkcja jest wykonywana przez kompilator, musi głęboko rekurencjonować, ale nie używa stosu do rekursji, ponieważ w rzeczywistości nie generuje i nie wykonuje kodu maszyny.

Answer 2

To nie może być ostateczny dokument w sprawie constexpr, ale jest to podstawowy dokument powiązany z gcc constexpr wiki.

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

... i to mówi ...

My (still) zabrania rekursji w całej jej formie w stałych wyrażeniach. To nie jest to bezwzględnie konieczne, ponieważ granica realizacja na głębokość rekurencji w stałej oceny ekspresji uratuje nas od możliwość kompilatora recursing zawsze. Jednak dopóki nie zobaczymy przekonującego argumentu za rekurencją, nie proponujemy dopuszczenia go.

Tak, spodziewam jesteś wpadając przeciwko granicy językowej i sposób gcc postanowiła zrealizować constexpr (może próby generowania funkcji całą inline, a następnie oceny/wykonanie go)