为什么GCC在这个递归Fibonacci代码中生成的程序比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;
}

当然，有更快的方法来计算斐波那契数，但这是一个很好的小压力测试，专注于递归函数调用。除了使用计时器来测量时间之外，代码中没有其他内容。

首先，我使用-O3优化在OSX上的Xcode中运行了几次测试（所以这是clang）。跑了大约9秒。

然后，我在Ubuntu上用gcc（g++）编译了同样的代码（再次使用-O3），那个版本只花了大约6.3秒就可以运行了！此外，我在mac上的VirtualBox中运行Ubuntu，这只会对性能产生负面影响。

所以你开始了：

• Clang on OS X->~9秒
• 在VirtualBox->~6.3秒的Ubuntu上运行gcc

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

那么，在这个特定的例子中，为什么gcc以英里数击败clang，有什么合乎逻辑的解释吗？

Answer 1

GCC 4.9.2确实进行了循环展开并内联了许多函数调用，而Clang 3.5.1在每次迭代中调用fib两次，甚至没有像下面那样的尾调用优化

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指令，而且它还在main中内联fib调用9次，但它没有将递归代码转换为迭代

以下是用于比较的编译器输出

注意，您可以像这样修改代码，使输出更容易读取

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

现在，编译器资源管理器将用不同的颜色突出显示汇编输出中指令对应的源代码行，您将很容易看到这两个调用是如何进行的。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,

Answer 2

我不会说gcc比clang好几英里。在我看来，性能差异（6.3秒对9秒）相当小。在我的FreeBSD系统上，clang需要26.12秒，gcc需要10.55秒。

但是，调试它的方法是使用g++ -S和clang++ -S来获得程序集输出。

我在我的FreeBSD系统上测试了这个。汇编语言文件太长，无法发布在此处，但gcc似乎在Fibonacci计算函数中执行多个级别的内联（其中有20个fib()调用！），而clang只是调用fib(n-1)和fib(n-2)，没有任何级别的内联。

顺便说一句，我的gcc版本是4.2.1 20070831补丁[FreeBSD]，clang版本是3.1（branches/release_31 156863）20120523。这些是FreeBSD 9.1-REEESE基本系统附带的版本。CPU为AMD Turion II Neo N40L双核处理器（1497.54-MHz）。