时间戳

首页 > 解决方案 > 为什么编译时执行比运行时执行快得多？

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

问题描述

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

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) 在 ~700ms 内编译，-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

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

标签： c++performance

解决方案

基本上，对于那一小段代码，编译时间并不重要。

甚至，如果您进行编译时评估。

主要问题是这里使用的最糟糕的算法。使用 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 以下运行。

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

进行以下实验。

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

现在到编译器时间版本。此外，编译器将在内部使用优化代码。它将无意义的递归方法转换为迭代方法。并且计算该值将比编译器开销函数花费更少的时间。

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

并且斐波那契数字总是可以在编译时完全编译。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';
}

推荐阅读