C++编译器如何如此快速地评估递归constexpr函数？
我一直在学习 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;
}
如果我constexpr从fibonacci()函数中删除标识符，则fibonacci(70)需要很长时间来评估（超过 5 分钟）。然而，当我保持原样时，程序仍然在 3 秒内编译，并在不到0.1几毫秒的时间内打印出正确的结果。
我了解到constexpr函数是在编译时计算的，所以这意味着fibonacci(70)编译器在不到 3 秒的时间内计算出来！但是，C++ 编译器比 C++ 代码具有更好的计算性能似乎不太正确。
我的问题是，在我按下“构建”按钮和编译完成之间，C++ 编译器是否真的评估了函数？还是我误解了关键字constexpr？
编辑：这个程序是g++ 7.5.0用--std=c++17.
回答
constexpr函数没有副作用，因此可以放心地记忆。鉴于运行时的差异，最简单的解释是编译器在编译时记忆 constexpr 函数。这意味着fibonacci(n)对于 each 只计算一次n，并且所有其他递归调用都从查找表中返回。
- 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.
- It's probably a play on [the as-if rule](https://en.cppreference.com/w/cpp/language/as_if). 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?
- @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.
- @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.
- @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.
- `constexpr` functions having no side-effects is news to me. Could you point to somewhere in the standard that requires this? It seems like it is implied in [expr.const:5.16](https://eel.is/c++draft/expr.const#5.16): "An expression E is a core constant expression unless the evaluation of E [...] would evaluate [...] a modification of an object [...] unless it is applied to a non-volatile lvalue of literal type that refers to a non-volatile object whose lifetime began within the evaluation of E." IIUC, this rules out modifying objects not local to the constant expression, i.e. side effects
回答
为其他人指出的内容添加一些细节：constexpr不必在运行时计算函数，并且可以影响它的参数之一是-fconstexpr-ops-limit.
在 GCC 10.2.0 上，-fconstexpr-ops-limit=1000000000(1B) 并fibonacci(40)生成预编译值，但如果将限制降低到 10000000 (10M)，则函数将在运行时计算。如果要确保始终在编译时计算该值，则需要在函数之外标记long long num为。constexprfibonacci
注意：相反的例子是在编译时计算的非 constexpr 函数（优化后），并用 标记它__attribute__ ((const))可能有助于编译器做出这样的决定。但是，我的编译器没有优化它。
- 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.