C编译器和循环优化

8

我对编译器的优化实际上没有太多经验,也不知道不同级别之间的区别(例如gcc中的-O2和-O3)。因此,我不确定对于任意一种编译器来说,下面这两个语句是否等价:

for(i=0;i<10;++i){
variable1*variable2*gridpoint[i];
}

并且

variable3=variable1*variable2;
for(i=0;i<10;++i){
variable3*gridpoint[i];
}

从处理时间的角度来看,只计算变量1和变量2的乘积一次似乎是有意义的,因为它们在循环中不会改变。然而,这需要额外的内存,我不确定优化器会如何考虑这种开销。如果你从论文/书籍中得到一个方程式并想将其转换为计算机可读的形式,那么第一个表达式最容易阅读,但第二个表达式可能是最快的——特别是对于在循环中有许多未更改变量的更复杂的方程式(我有一些相当恶心的非线性微分方程,我希望代码中人类可以读懂)。如果我将我的变量声明为常量,这些情况是否会发生变化?我希望我的问题对任意编译器都有意义,因为我使用gcc、Intel和Portland编译器。

2
这被称为“公共子表达式消除”。 - Cat Plus Plus
6
在这种情况下,除非一个变量被标记为volatile,否则由于循环体中的表达式没有副作用,整个循环将被优化掉。 - Jonathan Leffler
2
或者称为死代码消除,因为上述两个代码片段可以被安全地从程序中删除,因为它们什么也不做 :) - user405725
1
就记录而言,volatile变量是与内存空间的一个区域相关联的变量,它可以在代码正常流程之外发生变化...例如,映射到微处理器的输入寄存器的变量,或者映射到时钟寄存器的变量。因此,每次访问它时,它可能已经改变,即使没有代码分配给它一个值。因此,编译器不会将其提取到循环的外部。 - Dancrumb
2
答案是编译器“可能”执行这些优化,但不是必须的,并且由于各种原因可能不会执行任何优化。与其假设某些内容将被优化掉,不如尽力编写最佳代码。 - Variable Length Coder
显示剩余2条评论
3个回答

4
这个问题很难为任意编译器做出充分的回答。对于这段代码来说,能够做什么不仅取决于编译器,还取决于目标架构。我将尝试解释一下一个具有良好功能的生产编译器可以如何处理这段代码。
从处理时间的角度来看,只计算variable1和variable2的乘积一次是有意义的,因为它们在循环中不会改变。
你是正确的。正如Cat先生所指出的那样,这被称为公共子表达式消除。因此,编译器可以生成代码仅计算一次表达式(甚至在编译时计算它,如果两个操作数的值在某个时刻已知为常量)。
如果编译器能够确定函数没有副作用,一个体面的编译器也可以对函数执行子表达式消除。例如,GCC可以分析一个函数,如果其主体可用,但也有pureconst属性可用于特别标记应该受到此优化的函数(请参阅函数属性)。

鉴于没有副作用并且编译器能够确定它(在您的示例中,没有任何障碍),这方面的两个代码片段是等效的(我已经用clang进行了检查:-)。

然而,这需要额外的内存,我不确定优化器如何强烈地考虑这种开销。

实际上,这不需要任何额外的内存。乘法是在处理器寄存器中完成的,并且结果也存储在寄存器中。这是消除大量代码并使用单个寄存器存储结果的问题,这总是很好的(并且在寄存器分配方面肯定会使生活更轻松,特别是在循环中)。因此,如果可以进行此优化,则将不会产生额外的成本。

第一个表达式最容易阅读..

无论如何GCC和Clang都将执行此优化。但是我不确定其他编译器,所以您需要自己检查。但是很难想象没有进行子表达式消除的好编译器。

如果我将变量声明为常量,这会改变什么吗?

可能会有所不同。这被称为常量表达式,即只包含常量的表达式。常量表达式可以在编译期间而不是运行时进行评估。因此,例如,如果你将A和B都定义为常量并将它们相乘,编译器将仅预先计算A*B表达式,然后将C与该预先计算的值相乘。编译器甚至可以对非常量值进行此操作,如果它们可以确定其值在编译时且确定其不会更改。例如:

$ cat test.c
inline int foo(int a, int b)
{
    return a * b;
}

int main() {
    int a;
    int b;
    a = 1;
    b = 2;
    return foo(a, b);
}
$ clang -Wall -pedantic -O4 -o test ./test.c
$ otool -tv ./test
./test:
(__TEXT,__text) section
_main:
0000000100000f70    movl    $0x00000002,%eax
0000000100000f75    ret

除了上述代码片段,还有其他可以进行优化的地方。以下是一些我想到的:

第一个也是最明显的是循环展开。由于迭代次数在运行时已知,编译器可以决定展开循环。是否应用此优化取决于架构(即某些CPU可以“锁定您的循环”并比其展开版本更快地执行代码,这也通过使用更少的空间、避免额外的µOP融合阶段等使代码更加缓存友好)。

第二个优化可以将速度提高50倍,即使用 SIMD指令(SSE、AVX等)。例如,GCC非常擅长这方面的优化(如果不是更好的话,英特尔也必须如此)。我已经验证了以下功能:

uint8_t dumb_checksum(const uint8_t *p, size_t size)
{
    uint8_t s = 0;
    size_t i;
    for (i = 0; i < size; ++i)
        s = (uint8_t)(s + p[i]);
    return s;
}

...被转化成一个循环,每一步都会同时累加16个值(例如,像_mm_add_epi8一样),并且还有额外的代码处理对齐和奇数(<16)迭代计数。然而,最近一次检查时,Clang失败了。因此,即使迭代次数未知,GCC也可能以这种方式缩小您的循环。

如果我可以的话,我建议您不要优化代码,除非您发现它是瓶颈。否则,您可能会浪费大量时间进行虚假和过早的优化。

希望这回答了您的问题。祝你好运!


这被称为常量表达式。我认为发帖者的意思是将variable1等声明为const类型。 - Daniel Fischer
感谢您提供这个非常有用的回答。然而,我指的是将变量声明为"const float variable1"等,因此不一定是编译时常量。我可以安全地假设更清晰的符号表示也将被优化吗?例如,定义"const float a = NastyObject->TediousVariableName"并使用变量a代替冗长的变量名称?我不明白为什么编译器不会将其识别为简单的别名。 - user787267
@user787267:是的,这也可以帮助进行优化。原因是有时编译器无法确定是否存在副作用。例如,如果您使用 obj->value 并执行其他操作(即调用某个函数并将 obj 传递给它),编译器将不知道值是否正在更改,并且将始终从内存中读取它,而如果您明确执行 const type var = obj->var;,它可以将此值保留在寄存器中而不是读取内存,并进行其他优化。但是,如果没有副作用并且编译器可以确定,则无关紧要。 - user405725

3
是的,您可以信任编译器在执行子表达式消除方面做得很好,即使是通过循环。这可能会导致轻微的内存使用增加,但是任何体面的编译器都会考虑到所有这些情况,并且执行子表达式消除基本上总是有利的(因为我们所讨论的内存是寄存器和 L1 缓存)。
以下是一些快速测试,可以“证明”这一点。结果表明,基本上不应该尝试通过手动进行子表达式消除来胜过编译器,只需自然编写代码,让编译器做它擅长的事情(例如确定哪些表达式应真正被消除,哪些不应该根据目标架构和周围的代码。)
稍后,如果您对代码的性能不满意,您应该对代码进行分析,查看哪些语句和表达式占用了最多的时间,然后尝试确定是否可以重新组织代码以帮助编译器,但我认为大部分时间不会像这样简单,而是要做一些减少缓存停顿的工作(例如更好地组织数据),消除冗余的程序间计算等等。
(请注意,下面代码中随机数的使用只是为了确保编译器不能太过热衷于变量消除和循环展开。) prog1:
#include <stdlib.h>
#include <time.h>

int main () {
    srandom(time(NULL));
    int i, ret = 0, a = random(), b = random(), values[10];
    int loop_end = random() % 5 + 1000000000;
    for (i=0; i < 10; ++i) { values[i] = random(); }

    for (i = 0; i < loop_end; ++i) {
        ret += a * b * values[i % 10];
    }

    return ret;
}

prog2:

#include <stdlib.h>
#include <time.h>

int main () {
    srandom(time(NULL));
    int i, ret = 0, a = random(), b = random(), values[10];
    int loop_end = random() % 5 + 1000000000;
    for (i=0; i < 10; ++i) { values[i] = random(); }

    int c = a * b;
    for (i = 0; i < loop_end; ++i) {
        ret += c * values[i % 10];
    }

    return ret;
}

以下是结果:
> gcc -O2 prog1.c -o prog1; time ./prog1  
./prog1  1.62s user 0.00s system 99% cpu 1.630 total

> gcc -O2 prog2.c -o prog2; time ./prog2
./prog2  1.63s user 0.00s system 99% cpu 1.636 total

这是测量墙钟时间(wall time),因此不要关注0.01秒的差异,运行几次后它们都在1.62-1.63秒范围内波动,因此速度相同。

有趣的是,当没有进行优化编译时,prog1更快。

> gcc -O0 prog1.c -o prog1; time ./prog1  
./prog1  2.83s user 0.00s system 99% cpu 2.846 total

> gcc -O0 prog2.c -o prog2; time ./prog2 
./prog2  2.93s user 0.00s system 99% cpu 2.946 total

同样有趣的是,使用-O1编译提供了最佳性能。
gcc -O1 prog1.c -o prog1; time ./prog1 
./prog1  1.57s user 0.00s system 99% cpu 1.579 total

gcc -O1 prog2.c -o prog2; time ./prog2
./prog2  1.56s user 0.00s system 99% cpu 1.563 total

GCC和Intel都是优秀的编译器,对于这样的工作非常聪明。我没有使用过Portland编译器,但这些对于一个编译器来说都是基本的操作,所以如果它不能很好地处理这种情况,我会感到非常惊讶。


这些开关 O2 O1 O0 的意义是什么? - sr01853
这些是GCC的优化标志。-O0不执行任何主要优化,-O1进行一些优化,-O2执行更多的优化等等。 - hexist
不总是使用O2优化好。在哪些情况下可以使用O0优化呢?谢谢。 - sr01853
2
O0编译速度最快,也是最容易调试的。O2可能会优化掉变量定义和内联代码,因此在调试器中查看时,有时您无法检查某些变量的值等信息。O0则不会这样做。 - hexist
谢谢您的回答。您有什么猜测为什么在这种情况下-O1是最快的?以及为什么prog1在没有优化的情况下是最快的? - user787267
我们需要深入分析输出汇编代码,才能真正弄清楚O1与O2以及我们的O0情况。尽管有时优化可能会产生不利影响,但大多数情况下它们所带来的好处要大于坏处(我们希望如此!)。如果我必须猜测,那么可能是一些微妙的东西,比如指令排序,CPU能够利用这个进行优化,速度上只有非常微小的差别。不过,不要把这当作经验法则,在生产代码中,O2或O3仍然可能会产生更好的代码,但你可能需要进行检查 :)。 - hexist

0
如果我是编译器,我会认识到这两个循环都没有左操作数,并且完全没有副作用(除了将“i”设置为“10”),所以我会完全优化掉这两个循环。
我不是说这确实发生了;从您提供的代码来看,它只是看起来可能会发生。

1
这确实会发生 :) 但我认为他只是想提供一个简单的例子... - hexist
我确实只是想做一个简单的例子。如果循环里有左边的内容,那么可能会更有意义。 - user787267

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接