How does the C++ compiler evaluate recursive constexpr functions so quickly?

Question

I've been learning about C++ constexpr functions, and I implemented a constexpr recursive function to find the nth fibonacci number.

#include <iostream> #include <fstream> #include <cmath> #include <algorithm> #include <vector>  constexpr long long fibonacci(int num) {     if (num <= 2) return 1;     return fibonacci(num - 1) + fibonacci(num - 2); }  int main() {     auto start = clock();     long long num = fibonacci(70);     auto duration = (clock() - start) / (CLOCKS_PER_SEC / 1000.);     std::cout << num << "\n" << duration << std::endl; } 

If I remove the constexpr identifier from the fibonacci() function, then fibonacci(70) takes a very long time to evaluate (more than 5 minutes). When I keep it as-is, however, the program still compiles within 3 seconds and prints out the correct result in less than 0.1 milliseconds.

I've learned that constexpr functions are evaluated at compile time, so this would mean that fibonacci(70) is calculated by the compiler in less than 3 seconds! However, it doesn't seem quite right that the C++ compiler would have such better calculation performance than C++ code.

My question is, does the C++ compiler actually evaluate the function between the time I press the "Build" button and the time the compilation finishes? Or am I misunderstanding the keyword constexpr?

EDIT: This program was compiled with g++ 7.5.0 with --std=c++17.

Answer 1

constexpr functions have no side-effects and can thus be memoized without worry. Given the disparity in runtime the simplest explanation is that the compiler memoizes constexpr functions during compile-time. This means that fibonacci(n) is only computed once for each n, and all other recursive calls get returned from a lookup table.