7 
void foo(const int constant)
{
    for(int i = 0; i < 1000000; i++) {
        // do stuff
        if(constant < 10) {              // Condition is tested million times :(
            // inner loop stuff
        }
    }
}

对于外循环的每次执行，都会检查“常量”的值。但是，常量永远不会改变，因此浪费了大量 CPU 时间来测试条件常量 < 10？一遍又一遍地。人类会在最初的几次通过后意识到常数永远不会改变，并明智地避免一遍又一遍地检查它。编译器是否注意到这一点并对其进行智能优化，或者重复的 if 循环是否不可避免？

我个人认为这个问题是不可避免的。即使编译器将比较放在外部循环之前并设置某种布尔变量“skip_inner_stuff”，仍然必须检查外部for循环的每次传递。

你对此事有何看法？是否有更有效的方法来编写可以避免该问题的上述代码段？

4

7 回答 7

6

您描述的优化也称为循环取消切换。多年来，它一直是优化编译器的标准部分 - 但如果您想确保编译器执行它，请使用一些优化级别（例如 gcc 中的 -O2）编译示例代码并检查生成的代码。

但是，如果编译器无法证明一段代码在整个循环中是不变的——例如，调用在编译时不可用的外部函数——那么实际上，手动将代码提升到循环之外可以净非常大的性能提升。

于 2013-09-08T07:16:05.190 回答
3

编译器可以优化代码，但你不能指望它会对你的代码施展魔法。

优化很大程度上取决于您的代码和代码的使用。例如，如果您foo像这样使用：

foo(12345);

编译器可以非常优化代码。即使它可以在编译时计算结果。

但是如果你像这样使用它：

int k;
cin >> k;
foo(k);

在这种情况下，它无法摆脱内部if（该值在运行时提供）。

我用 MinGW/GCC-4.8.0 写了一个示例代码：

void foo(const int constant)
{
    int x = 0;
    for (int i = 0; i < 1000000; i++)
    {
        x++;
        if (constant < 10)
        {
            x--;
        }
    }
    cout << x << endl;
}

int main()
{
    int k;
    cin >> k;
    foo(k);
}

让我们看看生成的汇编代码：

004015E1  MOV EAX,0F4240                 // i = 1000000
004015E6  MOV EBP,ESP
004015E8  XOR EDX,EDX
004015EA  PUSH ESI
004015EB  PUSH EBX
004015EC  SUB ESP,10
004015EF  MOV EBX,DWORD PTR SS:[EBP+8]
004015F2  XOR ECX,ECX                    // set ECX to 0
004015F4  CMP EBX,0A                     // if constant < 10
          ^^^^^^^^^^
004015F7  SETGE CL                       // then set ECX to 1
004015FA  ADD EDX,ECX                    // add ECX to i
004015FC  SUB EAX,1                      // i--
004015FF  JNE SHORT 004015F2             // loop if i is not zero

如您所见，内部if存在于代码中。见CMP EBX,0A。

我再重复一遍，它在很大程度上取决于带有循环的行。

于 2013-09-08T08:20:23.650 回答
2

其他人已经涵盖了相关的编译器优化：循环取消切换，它将测试移到循环之外并提供两个单独的循环体；和代码内联，在某些情况下会为编译器提供实际值，constant以便它可以删除测试，或者无条件地执行“内部循环的东西”，或者完全删除它。

还要注意，除了编译器所做的任何事情之外，现代 CPU 设计实际上做了一些类似于“人类会在前几次通过后意识到常量永远不会改变”的事情。这称为动态分支预测。

关键是检查一个整数非常便宜，甚至采用一个分支也可能非常便宜。可能代价高昂的是错误预测的分支。现代 CPU 使用各种策略来猜测分支的走向，但所有这些策略都会很快开始正确地预测连续一百万次以相同方式走向的分支。

我不知道的是，现代 CPU 是否足够聪明，可以发现constant循环不变量并在微码中执行完整的循环取消切换。但是假设正确的分支预测，循环取消切换可能是一个小的优化。编译器针​​对的处理器系列越具体，它就越了解其分支预测器的质量，编译器就越有可能确定循环取消切换的额外好处是否值得代码膨胀。

当然，仍然有最少的 CPU，编译器必须提供所有的聪明才智。您 PC 中的 CPU 不是其中之一。

于 2013-09-08T09:50:16.063 回答
1

你可以手动优化它：

void foo(const int constant)
{
    if (constant < 10) {
        for(int i = 0; i < 1000000; i++) {
            // do stuff

           // inner loop stuff here
        }
    } else {
        for(int i = 0; i < 1000000; i++) {
            // do stuff

            // NO inner loop stuff here
        }
    }
}

我不知道大多数编译器是否会做这样的事情，但这似乎并不过分。

于 2013-09-08T07:18:41.467 回答
1

一个好的编译器可能会优化它。

编译器基于成本分析进行优化。因此，一个好的编译器应该估计每个替代方案的成本（有和没有提升）并选择更便宜的那个。

这意味着如果内部代码很大，则可能不值得优化，因为这可能导致指令缓存垃圾。另一方面，如果价格便宜，则可以吊装。

如果它因为没有被优化而出现在分析器中，那么编译器就搞砸了。

于 2013-09-08T10:38:21.003 回答
0

一个好的编译器会优化它（启用优化时）。

如果使用GCC你可以

  • 编译优化和汇编代码生成

     gcc -Wall -O2 -fverbose-asm -S source.c

    然后查看（使用一些编辑器或类似的寻呼机less）生成的汇编代码source.s

  • 要求 GCC 转储大量（数百个！）中间文件并查看其中的中间 gimple 表示

     gcc -Wall -O2 -fdump-tree-all -c source.c

  • 使用MELT及其探针以交互方式查看 gimple 内部。

养成总是用-Wallfrom询问所有警告的习惯gcc（或者g++如果编译 C++ 代码。

顺便说一句，在实践中，这种优化（“循环不变代码提升”作为另一个答案解释）是必不可少的，因为这种中间代码经常发生，例如在函数内联之后......（想象几个调用foo被内联。 ..)

于 2013-09-08T07:15:40.520 回答
0

实际上，所有现代编译器都会进行优化，如果您认为编译器不应该进行这种优化，那么为了遵守这种优化，您应该将变量设置为“volatile”。

于 2013-09-08T07:28:17.790 回答