为什么编译时执行比运行时执行快得多？

Question

与这个问题所说的相反，这段代码表现出一些奇怪的行为：

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

在我的机器上，使用 (GCC) 编译大约需要 700 毫秒-O3，输出为：

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

如果你使用这个函数，那么，无论是否优化，你的main运行时间都会低于1ms。

在你原来的main函数中，如果不使用计算结果，那么变量“X”，那么优化编译器就可以消除完整的函数调用。没有必要调用该函数。结果没用。

做如下实验。

添加std::cout << x << '\n';作为主函数中的最后一条语句。你会感到惊讶的。启用优化后，该函数将在最后调用。而你的时间测量什么也测量不了。

现在到编译时版本。编译器也会在内部使用优化的代码。它将把无意义的递归方法转换为迭代方法。计算该值所需的时间比编译器开销函数要少。

所以，这才是真正的原因。

并且斐波那契数总是可以在编译时完全编译。64 位结果值只有 93 种可能的结果。

请参阅以下方法，该方法创建所有斐波那契数的编译时数组。如果你想要第 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';
}