c++ - 为什么编译时执行明显快于运行时执行？

Question

与什么相反 this问题说，这段代码表现出一些奇怪的行为:

long long int fibonacci(int num) {
    if (num <= 2) return 1;
    return fibonacci(num - 1) + fibonacci(num - 2);
}

int main() {
    auto t1 = std::chrono::high_resolution_clock::now();
    long long int x = fibonacci(45);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> time(t2 - t1);
    std::cout << "Time taken: " << time.count() << "ms";
}

在我的机器上，编译时间约为 700 毫秒， -O3 (GCC) 和输出是:

Time taken: 2667.55ms

我用 constexpr 重写了上面的代码如下:

constexpr long long int fibonacci(int num) {
    if (num <= 2) return 1;
    return fibonacci(num - 1) + fibonacci(num - 2);
}

int main() {
    auto t1 = std::chrono::high_resolution_clock::now();
    constexpr long long int x = fibonacci(45);
    auto t2 = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> time(t2 - t1);
    std::cout << "Time taken: " << time.count() << "ms";
}

其编译时间大致相同，但输出为:

Time taken: 0ms

就目前而言，评估 fibonacci(45)在编译时比在运行时评估它快得多。为了消除多核编译的原因(这绝对不是)，我用 fibonacci(60) 重新运行了上面的第二个块.同样，代码在相同的时间内编译，但输出是:

Time taken: 29499.6ms

是什么导致了如此大的性能差距？

Answer 1

基本上，对于那段短代码，编译时间并不重要。
甚至，如果您进行编译时评估。
这里的主要问题是这里使用的最糟糕的算法。使用 2 个递归调用，然后再次调用 2 个递归函数，依此类推，对于这样一个简单的算法来说，确实具有最坏情况下的时间复杂度。
这个问题可以而且必须通过迭代方法来解决。
类似的东西:

unsigned long long fibonacci(size_t index) noexcept {
    unsigned long long f1{ 0ull }, f2{ 1ull }, f3{};
    while (index--) { f3 = f2 + f1; f1 = f2; f2 = f3; }
    return f2;
}

如果你使用这个函数，那么无论优化与否，你的主程序都会在 1ms 以下运行。
在你原来的main函数中，如果你不使用计算的结果，那么变量“X”，那么优化编译器就可以消除完整的函数调用。没有必要调用该函数。结果未使用。
进行以下实验。
添加 std::cout << x << '\n';作为主函数中的最后一条语句。你会感到惊讶。启用优化后，该函数将在最后被调用。而你的时间测量没有任何意义。
现在到编译器时间版本。此外，编译器将在内部使用优化的代码。它会将无意义的递归方法转换为迭代方法。并且计算这些值将比编译器开销函数花费更少的时间。
所以，这才是真正的原因。
并且斐波那契数列始终可以在编译时完全编译。对于 64 位结果值，只有 93 个可能的结果。
请参阅以下方法，该方法创建所有 Fibonacci 数的编译时间数组。如果你想要第 n 个数字，它只是一个查找值。
这将在非优化或优化模式下非常快速地工作。
这是该问题的快速可能解决方案。

#include <iostream>
#include <utility>
#include <array>
#include <algorithm>
#include <iterator>

// All done during compile time -------------------------------------------------------------------
constexpr unsigned long long getFibonacciNumber(size_t index) noexcept {
    unsigned long long f1{ 0ull }, f2{ 1ull }, f3{};
    while (index--) { f3 = f2 + f1; f1 = f2; f2 = f3; }
    return f2;
}
// Some helper to create a constexpr std::array initilized by a generator function
template <typename Generator, size_t ... Indices>
constexpr auto generateArrayHelper(Generator generator, std::index_sequence<Indices...>) {
    return std::array<decltype(std::declval<Generator>()(size_t{})), sizeof...(Indices) > { generator(Indices)... };
}
template <size_t Size, typename Generator>
constexpr auto generateArray(Generator generator) {
    return  generateArrayHelper(generator, std::make_index_sequence<Size>());
}
constexpr size_t MaxIndexFor64BitFibonacci = 93;

// This is the definition of a std::array<unsigned long long, 93> with all Fibonacci numbers in it
constexpr auto Fib = generateArray<MaxIndexFor64BitFibonacci>(getFibonacciNumber);
// End of: All done during compile time -----------------------------------------------------------


// The only code executed during runtime
int main() {

    // Show all Fibonacci numbers up to border value
    for (const auto fib : Fib) std::cout << fib << '\n';
}