Вопрос от constexpr, почему эти две разные программы работают с g++ в такое разное время?

Question

Я использую gcc 4.6.1 и получаю интересное поведение, связанное с вызовом constexpr функция. Эта программа работает очень хорошо и сразу распечатывает 12200160415121876738,

#include <iostream>

extern const unsigned long joe;

constexpr unsigned long fib(unsigned long int x)
{
   return (x <= 1) ? 1 : (fib(x - 1) + fib(x - 2));
}

const unsigned long joe = fib(92);

int main()
{
   ::std::cout << "Here I am!\n";
   ::std::cout << joe << '\n';
   return 0;
}

Эта программа работает вечно, и у меня никогда не было терпения ждать, пока она напечатает значение:

#include <iostream>

constexpr unsigned long fib(unsigned long int x)
{
   return (x <= 1) ? 1 : (fib(x - 1) + fib(x - 2));
}

int main()
{
   ::std::cout << "Here I am!\n";
   ::std::cout << fib(92) << '\n';
   return 0;
}

Почему такая огромная разница? Я что-то не так делаю во второй программе?

Редактировать: я собираю это с g++ -std=c++0x -O3 на 64-битной платформе.

Answer 1

joe является выражением интегральной константы; он должен использоваться в границах массива. По этой причине разумный компилятор оценит его во время компиляции.

В вашей второй программе, даже если компилятор может рассчитать его во время компиляции, нет причин, по которым он должен это делать.

Answer 2

Моим лучшим предположением было бы то, что во время компиляции программа номер один была оценена как fib(92), с множеством таблиц и прочего для компилятора, чтобы отслеживать, какие значения уже были оценены... делая запуск программы почти тривиальным,

Где, поскольку вторая версия фактически оценивается во время выполнения без поиска таблиц оцененных константных выражений, это означает, что вычисление fib(92) делает что-то вроде 2**92 рекурсивных вызовов.

Другими словами, компилятор не оптимизирует тот факт, что fib(92) является константным выражением.

Answer 3

У компилятора есть место для маневра, чтобы он решил не оценивать во время компиляции, если он считает, что что-то "слишком сложно". Это в тех случаях, когда не обязательно проводить оценку, чтобы сгенерировать правильную программу, которая действительно может быть запущена (как указывает @MSalters).

Я подумал, что решение о лени во время компиляции будет ограничением глубины рекурсии. (Это предлагается в спецификации как 512, но вы можете увеличить его с помощью флага командной строки -fconstexpr-depth если бы вы этого хотели.) Но скорее это контролировало бы его отказ в любых случаях... даже когда для запуска программы требовалась постоянная времени компиляции. Так что не влияет на ваше дело.

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

Answer 4

Я также хотел посмотреть, как gcc оптимизировал код для этого нового ключевого слова constexpr, и на самом деле это просто потому, что вы вызываете fib(92) в качестве параметра оператора ofstream::operator<<

::std::cout << fib(92) << '\n';

что он не оценивается во время компиляции, если вы попытаетесь вызвать его не как параметр другой функции (как вы это делали в)

const unsigned long joe = fib(92);

он оценивается во время компиляции, я написал в блоге об этом, если вы хотите больше информации, я не знаю, стоит ли упоминать об этом разработчикам gcc.