Mutable static variables in consteval contxt

Question

I'm trying to implement a consteval lambda to compute the nth Fibonacci number. I want to create a result cache in the lambda which I can use if the result is already cached. Here's what I have up till now:

#include <map>

int main()
{
    auto fib = [](this const auto& fib, const int n) consteval noexcept -> int
    {
        static std::map<int, int> cache;
        if(cache.find(n) != cache.end())
            return cache[n];
        if(n <= 1)
            cache[n] = 1;
        else
            cache[n] = fib(n-1) + fib(n-2);
        return cache[n];
    };

    return fib(24);
}

Note that this code does not compile. The issue is that the cache is marked as static which is not supported in consteval context. If I change the this declaration from static to static constexpr, then I cannot assign values to the cache since by making it constexpr, I'm making it immutable.

Note that I'm compiling with GCC trunk on compiler explorer with the following arguments: -std=c++23 -fvisibility=hidden -fanalyzer -Ofast -Wall -Wextra -Wpedantic -Wconversion -Werror.

I have two questions:

1. Is it even possible to populate the cache at compile time? If yes, then how can I do so?
2. In this code the compiler knows that fib will only be called with one specific value (apart from the recursive calls), i.e. 24. How can I implement a look-up table of Fibonacci values which I can then refer to at runtime?

Answer 1

Here's something that does what you were after: create a partially populated compile time cache to use at runtime and speed up runtime execution.

#include <array>
#include <iostream> //for my debugging line below

consteval std::array<int, 25> fibsFunc (unsigned int n)
{
    if (n <= 1) return std::array<int, 25> { 0, 1 };
    else
    {
        auto tmpResult = fibsFunc(n - 1);
        tmpResult[n] = tmpResult[n - 1] + tmpResult[n - 2];
        return tmpResult;
    }
}

int main()
{
    constexpr std::array<int, 25> fibs = fibsFunc(24);

    std::cout << fibs[24] << " should be 46368.\n";

    return fibs[24];
}

Output is

46368 should be 46368.

Why this works:

• We're no longer using map, which uses the heap and so can't be consteval.
• We separate the function (which needs to be consteval) from the cache (which needs to be constexpr).

Other things to note:

• When I tried bigger numbers (50), the compiler complained that Fibonacci numbers are large (citation needed)
• This didn't work on Visual Studio even with language set to Preview, but it did work with g++ with the latest: g++ -std=c++2b so.cpp.
• I didn't bother with making fibsFunc a template, but you obviously could and probably should.
• ...nor did I bother with lambdas, in the spirit of keeping it simple.