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.

Which compiler? godbolt timed out on your code with GCC 10.2 and clang 11.0 when compiled with -std=c++17 (with or without -O3). Both compilers decided the constexpr was too deeply recursive, compiled it to compute at runtime, then timed out at runtime. — ShadowRanger
– ShadowRanger, Commented Dec 3, 2020 at 23:13
Brute force Fibonacci is slow as hell. the compiler found a better way. — user4581301
– user4581301, Commented Dec 3, 2020 at 23:16
At a guess - recognising an equivalent iterative form of the recursion, combined with memoisation. But, ultimately, it will depend on quality of compiler implementation. — Peter
– Peter, Commented Dec 3, 2020 at 23:20
@bloody: Sigh... "Wrong" implies there is one right answer. I have two examples where it didn't do compile time optimization; that doesn't exclude the possibility that other compilers, flags, etc. might work, but the OP needs to be clear. If I made long long num = fibonacci(70); become constexpr long long num = fibonacci(70); to force compile-time evaluation, they both died complaining about excessive recursion. That's why I asked how the OP compiled their code; I don't think they're wrong, but it's needed to reproduce their result. — ShadowRanger
– ShadowRanger, Commented Dec 3, 2020 at 23:28
(off-topic nitpick: If you cared about performance, you wouldn't be using std::endl to force pointless flushing of cout between lines, even when the output is a pipe.) — Peter Cordes
– Peter Cordes, Commented Dec 4, 2020 at 16:33

orlp · Accepted Answer · 2020-12-03 23:15:32Z

62

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.

answered Dec 3, 2020 at 23:15

orlp

119k39 gold badges226 silver badges324 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

orlp Over a year ago

@ahskdjfk Correct. It's an optimization that constexpr allows simply due to its nature. I don't believe compilers are required to do this optimization however, so your mileage may vary.

user4581301 Over a year ago

It's probably a play on the as-if rule. The compiler can do whatever the hell it wants to your code if it thinks it'll be faster and not change the observable behaviour. No reason the compiler can't do it internally when computing the result of a constxepr function. The interesting question is if it can see this optimization at compile time for the constexpr function, why doesn't it apply the same to the runtime version?

ShadowRanger Over a year ago

@orlp: As I mention in the comments above, different versions of gcc definitely don't apply this optimization (the OP's 7.5 does, the most recent 10.2 release does not, at least not by default), so yeah, definitely a mileage varying case.

Peter Over a year ago

@user4581301 - Many possible explanations for why the compiler would "see" the optimisation at compile time for a constexpr function and not for the "runtime version". constexpr allows the compiler to assume things but must do analysis to conclude those things for the "runtime" version. That analysis may not be done (it can be expensive), so the optimisation is not done. Conversely, a compiler might gallop ahead attempting to evaluate a constexpr function until it exhausts memory. Compiler quality of implementation depends on many things.

Alex Reinking Over a year ago

I wouldn't be happy with my compiler introducing an invisible, uncontrollable, hash table to memoize my functions at runtime. Memory at compile time is "cheap", though, so that transformation seems reasonable while evaluating constexpr.

|

twasilczyk · Accepted Answer · 2020-12-04 20:50:08Z

6

To add some details to what other's pointed out: constexpr function doesn't have to be computed at runtime and one of the parameters that can affect it is -fconstexpr-ops-limit.

On GCC 10.2.0, -fconstexpr-ops-limit=1000000000 (1B) and fibonacci(40) results in a pre-compiled value, but if you drop the limit to 10000000 (10M) then function is computed at run-time. If you want to make sure the value is always computed at compile time, you need to mark long long num as constexpr in addition to the fibonacci function.

Note: the opposite example would be a non-constexpr function computed at compile time (optimized out) and marking it with __attribute__ ((const)) might help compiler make such decision. However, my compiler didn't optimize it out.

edited Dec 4, 2020 at 20:50

answered Dec 4, 2020 at 0:16

twasilczyk

1864 bronze badges

1 Comment

ShadowRanger Over a year ago

Note: If you use constexpr long long num, that guarantees it won't be computed at run-time. It doesn't guarantee it will be computed at compile-time; it just ensures that when the compiler might otherwise fall back to run-time evaluation, the compilation fails instead.

Manuel · Accepted Answer · 2020-12-05 17:26:27Z

In g++ 8.3.0, if you use constexpr in this case, it computes the value you are using and outputs the result as a constant. This is even without optimizations:

//#include <iostream>

constexpr long long fibonacci(int num){
    if(num <= 2){return 1;}
    return fibonacci(num - 1) + fibonacci(num - 2);
}

int main(int argc, char** argv)
{

    //double start = clock();
    long long num = fibonacci(70);
    //std::cout << num << std::endl;
    //cout << (clock()-start)/(CLOCKS_PER_SEC/1000) << endl;

    return 0;
}

        .file   "constexpr.cc"
        .text
        .globl  main
        .type   main, @function
main:
.LFB1:
        .cfi_startproc
        pushq   %rbp
        .cfi_def_cfa_offset 16
        .cfi_offset 6, -16
        movq    %rsp, %rbp
        .cfi_def_cfa_register 6
        movl    %edi, -20(%rbp)
        movq    %rsi, -32(%rbp)
        movabsq $190392490709135, %rax
        movq    %rax, -8(%rbp)
        movl    $0, %eax
        popq    %rbp
        .cfi_def_cfa 7, 8
        ret
        .cfi_endproc
.LFE1:
        .size   main, .-main
        .ident  "GCC: (Debian 8.3.0-6) 8.3.0"
        .section        .note.GNU-stack,"",@progbits

I was wondering why there is so huge difference between the code and the compiler in terms of execution time.

It seems it computes it without recursion. With recursion is just too slow.

What surprises me is that it can convert a recursive function into a iterative one, even without optimization, at compile time. At least that's what it seems.

Fedor · Accepted Answer · 2021-09-03 13:49:22Z

As already mentioned in the comments above constexpr function call as in the question:

long long num = fibonacci(70);

is performed in run-time. On-line compilers simply kill the running program due to timeout: https://gcc.godbolt.org/z/G8MvYTf9h

If you want to evaluate the function during compilation, then either add one more constexpr:

constexpr long long num = fibonacci(70);

or in C++20 define the function as immediate with consteval:

consteval long long fibonacci(int num)

In either case you will get a compilation error in any modern compiler due to "evaluation exceeding step limit" or similar, demo: https://gcc.godbolt.org/z/9919G4sTh

A good alternative to easy and very fast compute Fibonacci recursive function in compile-time is via template constexpr constants:

#include <iostream>

template<int N> constexpr size_t fib = fib<N-1> + fib<N-2>;
template<> constexpr size_t fib<1> = 1;
template<> constexpr size_t fib<2> = 1;

int main() { std::cout << fib<70>; }

Demo: https://gcc.godbolt.org/z/ce35vYPa7

Collectives™ on Stack Overflow

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

4 Answers 4

12 Comments

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

12 Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related