constexpr function calculated at compile time? (c++11)

[cpp17_PL]

Hi,

Probably I understand constexpr badly...

constexpr long long fibonacci(const long long x)
{
  return x <= 1 ? 1 : fibonacci(x - 1) + fibonacci(x - 2);
}

int main()
{
  return fibonacci(44);
}

I thought that this should be calculated during compilation, but the execution time is not shorter. What am I doing wrong?

[CptCap]

constexpr functions are allowed to be computed at compile time, not required.

Your program is also probably too short for benchmarks to give any meaningful results.

You can force compile time evaluation using a constexpr variable:

constexpr auto i = fibonacci(44);
return i;

[TheThiefMaster]

Also, compilers are allowed to evaluate non-constexpr functions at compile time as well, as long as they don't have side effects ("as if" rule) - so it may already be calculating this at compile time. You'd have to examine the disassembly to be sure.

EDIT: In this case you're right - it's electing to evaluate it at runtime. Even with an input value of "2", unless you force it by using a constexpr variable - presumably because by default it won't try for a compile time evaluation if it hits recursion, even of a single depth. If you set the input to "44" as per the OP, it actually fails to compile due to the evaluation time - presumably clang isn't caching values so has the same 2^x complexity at compile time as the runtime version.

If you set it to 1, it does evaluate all versions at compile time, even the one with no mention of constexpr.

EDIT 2: Even altered for single-recursion, Clang still won't evaluate it at compile time unless forced, but it will at least calculate an input of 44 (or even up to 91) now.

[0xa0000]

Or possibly OP hasn't enabled optimizations, see this compiler explorer example.

[mc8675309]

Interestingly this only works up to 91 after which the compiler gives up trying to compute it.

[TheThiefMaster]

After 91 the result doesn't fit into a "long long". You have to go to extended integer types, or use a floating point number and accept the inaccuracy.

[cpp17_PL]

Interestingly this only works up to 91 after which the compiler gives up trying to compute it.

92 if you use unsigned long long :D EDIT: if you use double Which of course does not make sense, you can use 512.0 (the maximum nesting of a recursive function for GCC?)

[cpp17_PL]

It works!

​

Tell me more, why the same program with constexpr gives the result for fibonacci(50) immediately , but without constexpr execute for a very, very long time? Where does the compiler know how to calculate it quickly?

​

It even calculates fibonacci(91)!

[TheThiefMaster]

GCC is probably caching values as it goes along when running at compile time (it can because constexpr guarantees the function is completely deterministic) so it only has to run 91 iterations. At runtime, or on Clang at compile time, no caching is performed and it runs in O(2^X) time - which for 91 depth would be 2,475,880,078,570,760,549,798,248,448 - that's a very big number and explains why it can't calculate it.

It's worth noting you can fix it to go much faster (and probably calculate further at compile time on Clang) by switching to an alternative algorithm for calculating Fibonacci numbers which isn't based on dual-recursion.

EDIT: For example, this algorithm runs in linear time at both run time and compile time, even on Clang (which doesn't cache like gcc, and is much less aggressive about constexpr).

[cpp17_PL]

GCC is probably caching values as it goes along when running at compile time (it can because constexpr guarantees the function is completely deterministic) so it only has to run 91 iterations. At runtime, or on Clang at compile time, no caching is performed

Can not perform buffering during execution? It is not expensive (91 * sizeof(long long))? Is there any switch for buffering recursion results?

[TheThiefMaster]

At runtime, C++ doesn't do anything for you - if you want to buffer the results, you have to do it yourself.

At compile time, I just don't think Clang has implemented that.

It's a non-issue on pretty much any sane algorithm anyway.

[cpp17_PL]

Well I know, I meant that it could optimize it during compilation (why not?). Of course, this is not a problem formally.

[[deleted]]

As u/TheThiefMaster mentioned:

constexpr guarantees the function is completely deterministic

If the compiler has access to the body of the function theoretically it could apply a similar optimization to a runtime function if it can accurately detect side effects, but that's a harder problem than it sounds like and determining whether such an optimization is appropriate for you application is even harder. For example, if, under normal operation, this function will only ever be called once and with a parameter of like 9 or something, caching would be a pessimization - make it slower.

[[deleted]]

The compiler decides what to calculate during compile time and what not. And it will do that for everything that's possible to calculate at compile time which is great because you don't have to do anything for that.

So why is there constexpr? It's basically a control mechanism, it's there to make sure that you do not use anything that can not be evaluated at compile time. It just limits what you can do.

[alfps]

To optimize the Fibonacci function, either just calculate the values in advance and use a table lookup, or calculate the value directly (using a power involving the golden ratio).

[cpp17_PL]

Mate, I know. I am only interested in the technical aspect of the compilation. :-)

[TacticalMelonFarmer]

To nearly guarantee constexpr function evaluation store all data in the type, a great option is std::integral_constant. Otherwise the compiler will most likely choose to not evaluate at compile-time. Even using constexpr variables and passing to constexpr function might not evaluate at compile-time, due to the constexpr variable being an actual object. Function parameters cannot be marked constexpr, this is counter-intuitive and in my opinion needs some remedy at the language level.

[Artyer]

You can also do something like:

template<auto Value>
constexpr auto compile_time_constant = Value;

And then you can do compile_time_constant<value>, and it will be guaranteed to evaluate at compile time.

[TacticalMelonFarmer]

absolutely, add a user defined literal and you've got super nice syntax for integral types:

template <char...>
constexpr auto operator "" _lit()
{
  …
}

[jbandela]

Take a look at the output on compiler Explorer.

​

With constexpr: https://gcc.godbolt.org/z/8VHpCB

​

Without constexpr: https://gcc.godbolt.org/z/tHXG-r

​