C++ 编译器如何如此快速地评估递归 constexpr 函数？

Question

我一直在学习 C++ constexpr 函数，并且我实现了一个 constexpr 递归函数来查找第 n 个斐波那契数。

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

如果我从 fibonacci() 函数中删除 constexpr 标识符，那么 fibonacci(70) 需要很长的时间来评估（超过5分钟）。然而，当我保持原样时，程序仍然会在 3 秒内编译并在不到 0.1 毫秒内打印出正确的结果。

我了解到 constexpr 函数在编译时求值，所以这意味着 fibonacci(70) 由编译器计算不到3秒！但是，C++编译器的计算性能会比C++代码好那么多，似乎不太对。

我的问题是，C++ 编译器是否真的在我按下“构建”按钮和编译完成之间计算函数？还是我误解了关键字 constexpr?

编辑：这个程序是用 g++ 7.5.0 和 --std=c++17 编译的。

Answer 1

constexpr 函数没有副作用，因此可以放心地记忆。考虑到运行时的差异，最简单的解释是编译器在编译时记忆了 constexpr 函数。这意味着 fibonacci(n) 只为每个 n 计算一次，所有其他递归调用都从查找 table.

中返回

Answer 2

向其他人指出的内容添加一些细节：constexpr 函数不必在运行时计算，可能影响它的参数之一是 -fconstexpr-ops-limit .

在 GCC 10.2.0 上，-fconstexpr-ops-limit=1000000000 (1B) 和 fibonacci(40) 生成预编译值，但如果您将限制降低到 10000000 (10M)，则函数在运行-时间。如果要确保该值始终在编译时计算，除了 fibonacci 函数之外，还需要将 long long num 标记为 constexpr。

注意：相反的例子是在编译时计算的非 constexpr 函数（优化掉）并用 __attribute__ ((const)) 标记它可能有助于编译器做出这样的决定。但是，我的编译器并没有优化它。

Answer 3

在 g++ 8.3.0 中，如果您在这种情况下使用 constexpr，它会计算您正在使用的值并将结果作为常量输出。这甚至没有优化：

//#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 0392490709135, %rax
        movq    %rax, -8(%rbp)
        movl    [=11=], %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

我想知道为什么代码和编译器在执行时间方面会有如此巨大的差异。

它似乎没有递归地计算它。递归太慢了。

令我惊讶的是，它可以在编译时将递归函数转换为迭代函数，甚至无需优化。至少看起来是这样。

Answer 4

如上评论所述constexpr 问题中的函数调用：

long long num = fibonacci(70);

在运行时间内执行。由于超时，在线编译器简单地杀死了运行ning 程序：https://gcc.godbolt.org/z/G8MvYTf9h

如果你想在编译期间评估函数，那么要么再添加一个constexpr:

constexpr long long num = fibonacci(70);

或在 C++20 中使用 consteval:

将函数定义为立即函数

consteval long long fibonacci(int num)

在任何一种情况下，由于“计算超出步长限制”或类似情况，您将在任何现代编译器中遇到编译错误，演示：https://gcc.godbolt.org/z/9919G4sTh

在编译时简单快速地计算斐波那契递归函数的一个很好的替代方法是通过模板 constexpr 常量：

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

演示：https://gcc.godbolt.org/z/ce35vYPa7

C++ 编译器如何如此快速地评估递归 constexpr 函数？

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

c++

recursion

function

constexpr