C ++编译器如何如此快速地评估递归constexpr函数? [英] How does the C++ compiler evaluate recursive constexpr functions so quickly?

问题描述

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

I've been learning about C++ constexpr functions, and I implemented a constexpr recursive function to find the nth fibonacci number.

#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 毫秒的时间内打印出正确的结果.

If I remove the constexpr identifier from the fibonacci() function, then fibonacci(70) takes a very long time to evaluate (more than 5 minutes). When I keep it as-is, however, the program still compiles within 3 seconds and prints out the correct result in less than 0.1 milliseconds.

我了解到 constexpr 函数在编译时被评估 ，所以这意味着 fibonacci(70)是由编译器不到3秒！但是，似乎C ++编译器的计算性能要比C ++代码更好.

I've learned that constexpr functions are evaluated at compile time, so this would mean that fibonacci(70) is calculated by the compiler in less than 3 seconds! However, it doesn't seem quite right that the C++ compiler would have such better calculation performance than C++ code.

我的问题是，C ++编译器实际上在我按"Build"(生成)按钮的时间之间会评估该功能吗?按钮，编译时间何时结束?还是我误解了关键字 constexpr ?

My question is, does the C++ compiler actually evaluate the function between the time I press the "Build" button and the time the compilation finishes? Or am I misunderstanding the keyword constexpr?

该程序是使用-std = c ++ 17 和 g ++ 7.5.0 编译的.

This program was compiled with g++ 7.5.0 with --std=c++17.

推荐答案

constexpr 函数没有副作用，因此可以轻松记住它.考虑到运行时的差异，最简单的解释是编译器会在编译时记住constexpr函数.这意味着 fibonacci(n)仅对每个 n 计算一次，并且所有其他递归调用都将从查找表中返回.

constexpr functions have no side-effects and can thus be memoized without worry. Given the disparity in runtime the simplest explanation is that the compiler memoizes constexpr functions during compile-time. This means that fibonacci(n) is only computed once for each n, and all other recursive calls get returned from a lookup table.

这篇关于C ++编译器如何如此快速地评估递归constexpr函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！