Why is initialization of variable with constexpr evaluated at runtime instead of at compile time

Question

As my understanding, the keyword constexpr is telling the compiler that the evaluation of expression can happen at compile time. Specifically, constexpr on a variable means that the value of the variable can be evaluated at compile time, whereas constexpr on a function means that this function may be invoked and evaluated its return value at compile time. If the funcion is invoked at runtime, it just acts as a common function.

Today, I wrote a piece of code to try to use constexpr:

#include <iostream>

using namespace std;

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

int main ()
{
    constexpr long int res = fib(32);
    // const long int res = fib(32);
    
    cout << res << endl;
    return 0;
}

I was expecting that the compilation of the code would spend much time but I'm wrong. It only spent 0.0290s to do the compilation:

$ time g++ test.cpp
real    0m0.290s
user    0m0.252s
sys     0m0.035s

But if I change constexpr long int res = fib(32); into const long int res = fib(32);, to my surprise, it spent much more time on the compilation:

$ time g++ test.cpp
real    0m5.830s
user    0m5.568s
sys     0m0.233s

In a word, it seems that const makes the function fib(32) to be evaluated at compile time, but constexpr makes it to be evaluated at runtime. I'm really confused.

My system: Ubuntu 18.04

My gcc: g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

Answer 1

By inspecting the generated assembly, we can confirm that in both cases G++ 7.5 computed the fib(32) value at compile time:

    movl    $2178309, %esi

The reason G++ evaluates constexpr context so fast is due to memoization which it performs when evaluating constexpr and template contexts.

Memoization completely kills fibonacci computational complexity by reducing it to O(N) complexity.

So why then is non-constexpr evaluation so much slower? I presume that's a bug/shortcoming in the optimizer. If I try with G++ 8.1 or later, there's no difference in compilation times, so presumably it had already been addressed.