为什么在运行时而不是在编译时评估带有 constexpr 的变量初始化

Question

据我了解，关键字 constexpr 告诉编译器可以在编译时对表达式求值。具体来说，变量上的 constexpr 意味着可以在编译时评估变量的值，而函数上的 constexpr 意味着可以调用该函数并评估其 return 值编译时间。如果在运行时调用函数，它只是作为一个普通函数。

今天写了一段代码尝试使用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;
}

我原以为代码的编译会花很多时间，但我错了。编译只用了0.0290s:

$ time g++ test.cpp
real    0m0.290s
user    0m0.252s
sys     0m0.035s

但是如果我将constexpr long int res = fib(32);改成const long int res = fib(32);，令我惊讶的是，它在编译上花费了更多时间：

$ time g++ test.cpp
real    0m5.830s
user    0m5.568s
sys     0m0.233s

一句话，好像 const让函数fib(32)在编译时被求值，但是constexpr让它在运行时进行评估。我真的很困惑。

我的系统：Ubuntu18.04

我的 gcc: g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0

Answer 1

编译时间短并不能证明调用未在编译时求值。您可以查看编译后的程序集，看看它实际上是在我的测试中使用 constexpr 在编译时评估的：https://godbolt.org/z/vbWaxe

在我使用更新的编译器进行的测试中，const 并不比 constexpr 慢多少。这可能是您的编译器版本的实现质量问题。

Answer 2

通过 inspecting 生成的程序集，我们可以确认在 两种情况下 G++ 7.5 在编译时计算了 fib(32) 值：

    movl    78309, %esi

G++ 如此快速地评估 constexpr 上下文的原因是由于 memoization 它在评估 constexpr 和 template 上下文时执行。

记忆化通过将复杂度降低到 O(N) 来完全消除斐波那契计算复杂度。

那么为什么非 constexpr 评估要慢得多？我认为这是优化器中的 bug/shortcoming 。如果我尝试使用 G++ 8.1 或更高版本，编译时间没有差异，所以大概已经解决了。

Answer 3

快速编译时间评估的秘诀在于，只有非常少的斐波那契数可以适合当今最大数据类型 unsigned long long。

Fibonacci 数计算的基本信息是：根本不需要任何运行时计算！一切都可以而且应该在编译时完成。然后，可以使用简单的查找机制。这将永远是最有效和最快的解决方案。

因此，根据 Binet 的公式，我们可以计算出只有很少适合 C++ unsigned long long 数据类型的斐波那契数，通常有 64现在是 2021 年，是“最大”的可用数据类型。 环岛 93。这在如今是一个非常低的数字。

借助现代 C++ 17（及更高版本）功能，我们可以在 编译时 轻松创建 64 位数据类型的所有斐波那契数的 std::array。因为如前所述，只有93个号码。

因此，我们将仅花费 93*8= 744 BYTE 的 none-runtime 内存用于我们的查找数组。这实在是微不足道。而且，编译器可以快速获取这些值。

经过编译时计算，我们可以通过写FIB[n]轻松得到斐波那契数n。详细解释见下文

而且，如果我们想知道，如果一个数字是斐波那契数列，那么我们使用 std::binary_search 来查找值。所以，这个函数将是例如：

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

FIB（当然可以是任何其他名称）是一个编译时间，constexpr std::array。那么，如何构建该数组？

我们首先将计算斐波那契数的默认方法定义为 constexpr 函数（非递归）：

// 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;
}

这样，斐波那契数可以在编译时轻松计算为constexpr values。然后，我们用所有斐波那契数填充 std::array。我们还使用 constexpr 并使其成为带有可变参数包的模板。

我们使用 std::integer_sequence 为索引 0,1,2,3,4,5, ....

创建斐波那契数列

这很简单，也不复杂：

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

此函数将输入整数序列 0,1,2,3,4,... 和 return 一个 std::array<unsigned long long, ...> 以及相应的斐波那契数列。

我们知道我们最多可以存储 93 个值。因此我们创建了一个 next 函数，它将使用整数序列 1,2,3,4,...,92,93 调用上面的函数，如下所示：

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

现在，终于，

constexpr auto FIB = generateArray();

将为我们提供一个名为 FIB 的编译时 std::array<unsigned long long, 93>，其中包含所有斐波那契数列。如果我们需要第 i 个斐波那契数，那么我们可以简单地写 FIB[i]。运行时不会有计算。

整个示例程序如下所示：

#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;
}

使用 Microsoft Visual Studio Community 2019 版本 16.8.2 开发和测试

额外测试了 gcc 10.2 和 clang 11.0.1

语言：C++ 17

为什么在运行时而不是在编译时评估带有 constexpr 的变量初始化

Why is initialization of variable with constexpr evaluated at runtime instead of at compile time

c++

compilation

constants

constexpr

c++11