使用全局变量递归函数的GCC优化差异

Question

有一天，我遇到了一个奇怪的问题，使用GCC和'-Ofast'优化标志。使用'gcc -Ofast -o fib1 fib1.c'编译下面的程序。

#include <stdio.h> 

int f1(int n) { 
    if (n < 2) { 
     return n; 
    } 
    int a, b; 
    a = f1(n - 1); 
    b = f1(n - 2); 
    return a + b; 
} 

int main(){ 
    printf("%d", f1(40)); 
} 

当测量执行时间，其结果是：

peter@host ~ $ time ./fib1 
102334155 
real 0m0.511s 
user 0m0.510s 
sys  0m0.000s 

现在让我们来介绍我们的程序中的全局变量和编译再次使用 'GCC -Ofast -o FIB2 fib2.c'。

#include <stdio.h> 

int global; 

int f1(int n) { 
    if (n < 2) { 
     return n; 
    } 
    int a, b; 
    a = f1(n - 1); 
    b = f1(n - 2); 

    global = 0; 

    return a + b; 
} 

int main(){ 
    printf("%d", f1(40)); 
} 

现在的执行时间为：

peter@host ~ $ time ./fib2 
102334155 
real 0m0.265s 
user 0m0.265s 
sys  0m0.000s 

新的全局变量并没有做任何有意义。但是，执行时间的差异相当大。

除了问题（1）这种行为的原因是什么，如果（2）最后的表现可以在不引入无意义的变量的情况下实现，那也是很好的。有什么建议么？

感谢 彼得

Answer 1

在我的机器（gcc (Ubuntu 5.2.1-22ubuntu2) 5.2.1 20151010），我有这样的：
time ./fib1 0,36s user 0,00s system 98% cpu 0,364 total
time ./fib2 0,20s user 0,00s system 98% cpu 0,208 total

从man gcc：

-Ofast
否认严格符合标准。 -Ofast启用所有-O3优化。它还支持对所有符合标准的程序无效的优化。它打开了 - 数学和Fortran特定的-fno-protect-parens和-fstack-arrays。

不那么安全的选择，让我们尝试-O2：
time ./fib1 0,38s user 0,00s system 99% cpu 0,377 total
time ./fib2 0,47s user 0,00s system 99% cpu 0,470 total

我认为，一些激进的优化不会应用于fib1，但被应用到fib2。当我将-Ofast转换为-O2时 - 某些优化不适用于fib2，但适用于fib1。

让我们尝试-O0：
time ./fib1 0,81s user 0,00s system 99% cpu 0,812 total
time ./fib2 0,81s user 0,00s system 99% cpu 0,814 total

他们没有优化相等。
因此，在递归函数中引入全局变量可以一方面破坏一些优化，另一方面改善其他优化。

Answer 2

我相信你碰到了一些非常聪明和非常怪异的gcc（mis - ？）优化。就我研究这件事情而言，这就是大概。

我修改你的代码有大约全球的#ifdef G：

$ cc -O3 -o foo foo.c && time ./foo 
102334155 

real 0m0.634s 
user 0m0.631s 
sys  0m0.001s 
$ cc -O3 -DG -o foo foo.c && time ./foo 
102334155 

real 0m0.365s 
user 0m0.362s 
sys  0m0.001s 

所以我也有同样怪异的性能差异。

如果有疑问，请阅读生成的汇编程序。

$ cc -S -O3 -o foo.s -S foo.c 
$ cc -S -DG -O3 -o foog.s -S foo.c 

在这里它变得真正的离奇。通常我可以很容易地遵循gcc生成的代码。这里产生的代码只是不可理解的。什么应该是非常简单的递归和加法，应该适用于15-20条指令，gcc扩展到数百条指令，并且在栈上有一系列的移位，加法，减法，比较，分支和大数组。它看起来像试图将一个或两个递归部分转换为迭代，然后展开该循环。有一两件事让我吃惊，虽然，非全局函数只有一个递归调用本身（第二个是从主通话）：

$ grep 'call.*f1' foo.s | wc 
     2  4  18 

虽然全球一个人有：

$ grep 'call.*f1' foog.s | wc 
    33  66  297 

我的教育程度（我以前见过很多次）猜测？海湾合作委员会试图变得聪明并且激起了理论上应该更容易优化生成更糟糕的代码的功能，而写入全局变量使得它充分混淆，以至于无法优化以至于导致更好的代码。这种情况一直在发生，许多gcc（以及其他编译器，我们不会将它们单独列出）的优化对于它们使用的某些基准测试非常具体，并且在许多其他情况下可能不会生成更快的运行代码。事实上，从经验来看，我只会使用-O2，除非我已经非常仔细地对事情进行了基准测试，看看-O3是否合理。它通常不会。

如果你真的想进一步研究这个问题，我建议你阅读GCC文档哪些优化得到与-O3启用，而不是-O2（-O2并没有这样做），然后尝试逐一直到找到一个会导致这种行为，并且优化应该是一个很好的提示。我即将这样做，但我耗尽了时间（必须做最后一刻的圣诞购物）。

Answer 3

这是内联限制在第二版本早些时候踢的结果。因为具有全局变量的版本更多。这强烈地暗示内联使得在这个特定的例子中运行时性能变差。

编译这两个版本与-Ofast -fno-inline和时间的差异消失了。事实上，没有全局变量的版本运行得更快。

或者，只需用__attribute__((noinline))标记该功能即可。