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

The secret for the fast compile time evaluation is that there are only very very few Fibonacci numbers that would fit into the nowadays maximum data type unsigned long long.

The basic message for Fibonacci number calculation is: Any calculation at runtime is not necessary at all! Everything can and should be done at compile time. And then, a simple lookup mechanism can be used. That will always be the most efficient and fastest solution.

So, with Binet's formula, we can calculate that there are only very few Fibonacci numbers that will fit in a C++ unsigned long long data type, which has usually 64 bit now in 2021 and is the "biggest" available data type. Roundabout 93. That is nowadays a really low number.

With modern C++ 17 (and above) features, we can easily create a std::array of all Fibonacci numbers for a 64bit data type at compile time. Because there are, as mentioned above, only 93 numbers.

So, we will spend only 93*8= 744 BYTE of none-runtime memory for our lookup array. That is really negligible. And, the compiler can get those values fast.

After the compile time calculation, we can easily get the Fibonacci number n by writing FIB[n]. For detailed explanation, please see below.

And, if we want to know, if a number is Fibonacci, then we use std::binary_search for finding the value. So, this function will be for example:

bool isFib(const unsigned long long numberToBeChecked) {
    return std::binary_search(FIB.begin(), FIB.end(), numberToBeChecked);
}

FIB (of course any other name possible) is a compile time, constexpr std::array. So, how to build that array?

We will first define the default approach for calculation a Fibonacci number as a constexpr function (non-recursive):

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) noexcept {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // Calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}

With that, Fibonacci numbers can easily be calculated at compile time as constexpr values. Then, we fill a std::array with all Fibonacci numbers. We use also a constexpr and make it a template with a variadic parameter pack.

We use std::integer_sequence to create a Fibonacci number for indices 0,1,2,3,4,5, ....

That is straigtforward and not complicated:

template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

This function will be fed with an integer sequence 0,1,2,3,4,... and return a std::array<unsigned long long, ...> with the corresponding Fibonacci numbers.

We know that we can store maximum 93 values. And therefore we make a next function, that will call the above with the integer sequence 1,2,3,4,...,92,93, like so:

constexpr auto generateArray() noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

And now, finally,

constexpr auto FIB = generateArray();

will give us a compile-time std::array<unsigned long long, 93> with the name FIB containing all Fibonacci numbers. And if we need the i'th Fibonacci number, then we can simply write FIB[i]. There will be no calculation at runtime.

---

The whole example program will look like this:

#include <iostream>
#include <array>
#include <utility>
#include <algorithm>
#include <iomanip>
// ----------------------------------------------------------------------
// All the following will be done during compile time

// Constexpr function to calculate the nth Fibonacci number
constexpr unsigned long long getFibonacciNumber(size_t index) noexcept {
    // Initialize first two even numbers 
    unsigned long long f1{ 0 }, f2{ 1 };

    // calculating Fibonacci value 
    while (index--) {
        // get next value of Fibonacci sequence 
        unsigned long long f3 = f2 + f1;
        // Move to next number
        f1 = f2;
        f2 = f3;
    }
    return f2;
}
// We will automatically build an array of Fibonacci numbers at compile time
// Generate a std::array with n elements 
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { getFibonacciNumber(ManyIndices)... } };
};

// Max index for Fibonaccis that for an 64bit unsigned value (Binet's formula)
constexpr size_t MaxIndexFor64BitValue = 93;

// Generate the required number of elements
constexpr auto generateArray()noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

// This is an constexpr array of all Fibonacci numbers
constexpr auto FIB = generateArray();

// All the above was compile time
// ----------------------------------------------------------------------


// Check, if a number belongs to the Fibonacci series
bool isFib(const unsigned long long numberToBeChecked) {
    return std::binary_search(FIB.begin(), FIB.end(), numberToBeChecked);
}

// Test
int main() {

    const unsigned long long testValue{ 498454011879264ull };

    std::cout << std::boolalpha << "Does '" <<testValue << "' belong to Fibonacci series?  --> " << isFib(testValue) << "\n\n";

    for (size_t i{}; i < 10u; ++i)
        std::cout << i << '\t' << FIB[i] << '\n';

    return 0;
}

---

Developed and tested with Microsoft Visual Studio Community 2019, Version 16.8.2

Additionally tested with gcc 10.2 and clang 11.0.1

Language: C++ 17

Answer 2

A short compilation time is not proof that the calls weren't evaluated at compile time. You can look at the compiled assembly to see that it was in fact evaluated at compile time using constexpr in my test here: https://godbolt.org/z/vbWaxe

In my tests with a newer compiler, const wasn't measurably slower than constexpr. It could be a quality of implementation issue with your version of the compiler.

Answer 3

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.