C语言 使用全局变量的递归函数中的 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(错误-？优化。这就是我研究这个的程度。

我修改了您的代码以在全局范围内进行#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 扩展到数百条指令，其中包含一系列移位、加法、减法、比较、分支和堆栈上的大数组。看起来它试图将一个或两个递归部分转换为迭代，然后展开该循环。不过，有一件事让我印象深刻，非全局函数对自身只有一个递归调用(第二个是来自 main 的调用(：

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

而全球的有：

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

我

受过教育的(我以前见过很多次(猜？Gcc 试图变得聪明，在其热情中，理论上应该更容易优化的函数生成了更糟糕的代码，而写入全局变量使其足够混乱，以至于它无法如此努力地优化，以至于它导致了更好的代码。这种情况一直在发生，gcc(以及其他编译器，我们不要挑出它们(使用的许多优化都非常特定于他们使用的某些基准，并且在许多其他情况下可能不会生成更快的运行代码。事实上，根据经验，我只使用 -O2，除非我非常仔细地对标进行基准测试，以确定 -O3 是有意义的。它通常不会。

如果你真的想进一步研究这个问题，我建议阅读 gcc 文档，了解哪些优化是用-O3而不是-O2启用的(-O2不这样做(，然后一个接一个地尝试，直到你找到导致这种行为的一个，并且优化应该是一个很好的提示正在发生的事情。我正要这样做，但我没时间了(必须做最后一分钟的圣诞购物(。

Answer 2

在我的机器上(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 启用所有 -O3 优化。 它还支持并非对所有符合标准的程序都有效的优化。 它打开 -ffast-math 和特定于 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 3

这是由于在第二个版本中较早的内联限制所致。因为带有全局变量的版本执行更多操作。这强烈表明，在此特定示例中，内联会使运行时性能变差。

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

或者，只需用 __attribute__((noinline)) 标记函数。