c++ - 为什么在这个递归斐波那契代码中 GCC 生成的程序比 Clang 更快？

Question

这是我测试过的代码:

#include <iostream>
#include <chrono>
using namespace std;

#define CHRONO_NOW                  chrono::high_resolution_clock::now()
#define CHRONO_DURATION(first,last) chrono::duration_cast<chrono::duration<double>>(last-first).count()

int fib(int n) {
    if (n<2) return n;
    return fib(n-1) + fib(n-2);
}

int main() {
    auto t0 = CHRONO_NOW;
    cout << fib(45) << endl;
    cout << CHRONO_DURATION(t0, CHRONO_NOW) << endl;
    return 0;
}

当然，计算 Fibonacci 数的方法要快得多，但这是一个很好的小压力测试，侧重于递归函数调用。除了使用 chrono 来测量时间之外，代码没有其他内容。

首先，我使用 -O3 优化在 OS X 上的 Xcode 中运行了几次测试(这就是 clang)。运行大约需要 9 秒。

然后，我在 Ubuntu 上用 gcc (g++) 编译了相同的代码(再次使用 -O3)，那个版本只用了大约 6.3 秒来运行!另外，我在我的 Mac 上 inside VirtualBox 运行 Ubuntu，这只会对性能产生负面影响，如果有的话。

就这样吧

• OS X 上的 Clang -> ~9 秒
• Ubuntu 上的 gcc 在 VirtualBox 中 -> ~6.3 秒。

我知道这些是完全不同的编译器，所以它们做的事情不同，但我看到的所有以 gcc 和 clang 为特色的测试只显示出很小的差异，在某些情况下，差异是相反的 ( clang 更快)。

那么对于为什么 gcc 在这个特定示例中远远击败 clang 有什么合乎逻辑的解释吗？

Answer 1

GCC 4.9.2 compiler explorer Clang 3.5.1 调用 fib 两次 每次迭代 时确实展开循环并内联大量函数调用，甚至没有 tail call optimization如下图

fib(int):                                # @fib(int)
        push    rbp
        push    rbx
        push    rax
        mov     ebx, edi
        cmp     ebx, 2
        jge     .LBB0_1
        mov     eax, ebx
        jmp     .LBB0_3
.LBB0_1:
        lea     edi, dword ptr [rbx - 1]
        call    fib(int)       # fib(ebx - 1)
        mov     ebp, eax
        add     ebx, -2
        mov     edi, ebx
        call    fib(int)       # fib(ebx - 2)
        add     eax, ebp
.LBB0_3:
        add     rsp, 8
        pop     rbx
        pop     rbp
        ret

GCC 版本长了 10 多倍，只有一个 fib 调用和 20 多个用于内联调用的标签，这也意味着最后一个调用有已尾优化为 jmp 或 GCC 已将一些递归转换为迭代(因为它分配了一个大数组来存储中间值)

我还对 ICC 进行了透视，令人惊讶的是它在 fib 中有 10 个 call 指令，而且它还内联 fib 在 main 中调用了 9 次，但它没有将递归代码转换为迭代代码

Here's the compiler outputs for comparison

请注意，您可以像这样修改代码以使输出更易于阅读

int fib(int n) {
    if (n<2) return n;
    int t = fib(n-1);
    return t + fib(n-2);
}

现在 compiler explorer 将用不同的颜色突出显示汇编输出中指令对应的源代码行，您将很容易看到这两个调用是如何进行的。 return t + fib(n-2) 行被 GCC 编译为

.L3:
        mov     eax, DWORD PTR [rsp+112]  # n, %sfp
        add     edx, DWORD PTR [rsp+64]   # D.35656, %sfp
        add     DWORD PTR [rsp+60], edx   # %sfp, D.35656
        sub     DWORD PTR [rsp+104], 2    # %sfp,