Почему этот код constexpr заставляет GCC съесть всю мою оперативную память?

Следующая программа позвонит веселье 2 ^ (MAXD + 1) раз. Максимальная глубина рекурсии никогда не должна превышать MAXD (если мое мышление верно). Таким образом, сборка может занять некоторое время, но она не должна съесть мою оперативную память.

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

Проблема в том, что съесть мою оперативную память — это именно то, что она делает Когда я включаю MAXD до 30, мой ноутбук начинает меняться после того, как GCC 4.7.2 быстро выделяет 3 ГБ или около того. Я еще не пробовал это с clang 3.1, поскольку у меня нет доступа к этому прямо сейчас.

Мое единственное предположение, что это как-то связано с тем, что GCC пытается быть слишком умным и запоминать вызовы функций, как это происходит с шаблонами. Если это так, не кажется ли странным, что у них нет ограничения на то, сколько они запоминают, например, размер таблицы кэша MRU или что-то еще? Я не нашел переключатель, чтобы отключить его.

Зачем мне это делать?
Я занимаюсь идеей создания расширенной библиотеки времени компиляции, такой как генетическое программирование или что-то в этом роде. Поскольку компиляторы не имеют оптимизации вызовов хвоста времени компиляции, я обеспокоен тем, что все циклы потребуют рекурсии и (даже если я включу параметр максимальной глубины рекурсии, который кажется немного уродливым) быстро выделят всю мою оперативную память и заполнят это с бессмысленными кадрами стека. Таким образом, я придумал вышеупомянутое решение для получения произвольного количества вызовов функций без глубокого стека. Такая функция может быть использована для складывания / зацикливания или прыжков на батуте.

РЕДАКТИРОВАТЬ:
Теперь я попробовал это в clang 3.1, и он не будет пропускать память вообще, независимо от того, как долго я заставляю это работать (то есть, как высоко я делаю MAXD). Загрузка процессора составляет почти 100%, а использование памяти — почти 0%, как и ожидалось. Возможно, это просто ошибка в GCC.

7

Решение

Это может быть не окончательный документ, касающийся constexpr, но это основной документ, связанный с gcc constexpr wiki.

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

… и это говорит …

Мы (до сих пор) запрещаем рекурсию во всех ее формах в постоянных выражениях.
Это не является строго необходимым, поскольку ограничение реализации
глубина рекурсии в оценке константного выражения спасет нас от
возможность повторения компилятора навсегда. Однако пока мы
Посмотрите убедительный сценарий использования для рекурсии, мы не предлагаем его разрешать.

Итак, я ожидаю, что вы столкнетесь с языковой границей и способом, который gcc выбрал для реализации constexpr (возможно, пытаясь сгенерировать всю встроенную функцию, а затем оценить / выполнить ее)

2

Другие решения

Ваш ответ в вашем комментарии «запустив функцию времени выполнения и наблюдая за тем, как я могу заставить ее работать долго», что вызвано вашим самым рекурсивным внутренним вызовом fun (x + 1, глубина + 1).

Когда вы изменили его на функцию времени выполнения, а не на функцию времени компиляции, удалив constexpr, и заметили, что он работал долго, это показатель того, что он возвращается очень глубоко.

Когда функция выполняется компилятором, она должна глубоко рекурсировать, но не использует стек для рекурсии, поскольку фактически не генерирует и не выполняет машинный код.

1