GCC 5.4.0下的昂贵跳跃

Question

GCC 5.4.0下的昂贵跳跃

c++gccx86conditional-statementsbranch-prediction

172

我是一名有用的助手，可以为您翻译文本。

我有一个函数，代码如下（仅显示重要部分）：

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) && (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

按照这种方式编写的函数在我的机器上需要约34毫秒。将条件改为布尔乘法后（使代码看起来像这样）：

double CompareShifted(const std::vector<uint16_t>& l, const std::vector<uint16_t> &curr, int shift, int shiftY)  {
...
  for(std::size_t i=std::max(0,-shift);i<max;i++) {
     if ((curr[i] < 479) * (l[i + shift] < 479)) {
       nontopOverlap++;
     }
     ...
  }
...
}

执行时间减少到约19毫秒。

使用的编译器是GCC 5.4.0，使用-O3参数。在检查了使用godbolt.org生成的汇编代码后，我发现第一个示例生成了一条跳转指令，而第二个示例则没有。我决定尝试GCC 6.2.0，它在使用第一个示例时也会生成一条跳转指令，但是GCC 7似乎不再生成跳转指令。

发现这种加速代码的方法相当困难，需要花费相当长的时间。为什么编译器会这样行为？这是否是有意的，程序员应该注意吗？还有类似这样的事情吗？

- Jakub Jůza

18

编译器为什么会表现出这种行为？只要生成的代码正确，编译器可以随心所欲地进行操作。有些编译器比其他编译器更擅长优化处理。 - Jabberwocky

27

我猜测这是由于 && 的短路求值所引起的。 - Jens

10

请注意，这也是为什么我们还有“&”符号的原因。 - rubenvb

7

按照概率，排序很可能会提高执行速度，请参见这个问题。 - rubenvb

8

“must not be evaluated（禁止评估）”对于没有副作用的表达式实际上并没有意义。我怀疑这个向量正在进行边界检查，而GCC无法证明它不会越界。编辑：实际上，我认为你并没有采取任何措施防止i + shift越界。 - Random832

显示剩余13条评论

4个回答

23

需要注意的一件重要事情是

(curr[i] < 479) && (l[i + shift] < 479)

并且

(curr[i] < 479) * (l[i + shift] < 479)

它们在语义上不等同！特别是，如果您遇到以下情况：

0 <= i 和 i < curr.size() 都为真
curr[i] < 479 为假
i + shift < 0 或 i + shift >= l.size() 为真

那么表达式 (curr[i] < 479) && (l[i + shift] < 479) 保证是一个良好定义的布尔值。例如，它不会导致分段错误。

然而，在这些情况下，表达式 (curr[i] < 479) * (l[i + shift] < 479) 是未定义行为；它可能导致分段错误。

这意味着对于原始的代码片段，例如，编译器不能只写一个循环来执行两个比较并进行and操作，除非编译器还能证明在需要时l[i + shift]永远不会导致segfault。

简而言之，原始代码提供的优化机会比后者少。（当然，编译器是否认识到这个机会是完全不同的问题）

您可以通过以下方式修复原始版本

bool t1 = (curr[i] < 479);
bool t2 = (l[i + shift] < 479);
if (t1 && t2) {
    // ...

- user1084944

这里存在未定义行为（UB），取决于 shift（和 max）的值... - Matthieu M.

18

&& 运算符实现短路求值。这意味着仅在第一个操作数求值为 true 时才会对第二个操作数求值。在这种情况下，会立即跳转到第二个操作数的位置。

你可以创建一个小示例来展示这一点：

#include <iostream>

bool f(int);
bool g(int);

void test(int x, int y)
{
  if ( f(x) && g(x)  )
  {
    std::cout << "ok";
  }
}

这里可以找到汇编输出。

你可以看到生成的代码首先调用了f(x)，然后检查输出并在为true时跳转到g(x)的评估。否则它就离开了函数。

使用“布尔”乘法强制每次评估两个操作数，因此不需要跳转。

取决于数据，跳转可能会导致减速，因为它干扰了CPU管道和其他诸如推测执行之类的东西。通常分支预测有帮助，但如果您的数据是随机的，则可以预测的内容不多。

- Jens

1

为什么你说每次乘法都会强制评估两个操作数？无论x的值如何，0x=x0=0。作为优化，编译器也可以“短路”乘法。例如，请参见https://dev59.com/ZV3Ua4cB1Zd3GeqP_Ecj。此外，与“&&”运算符不同，乘法可以使用第一个或第二个参数进行惰性评估，从而允许更多的优化自由。 - SomeWittyUsername

1

@SomeWittyUsername 好的，编译器当然可以自由地进行任何优化，只要保持可观察行为即可。这可能会转换它并省略计算。如果您计算 0 * f() 并且 f 具有可观察行为，则编译器必须调用它。不同之处在于，对于 &&，短路评估是强制性的，但如果可以证明对于 * 是等效的，则允许使用。 - Jens

只有在可以从变量或常量中预测到0值的情况下，@SomeWittyUsername才能进行优化。我猜这种情况非常非常少。当然，在涉及数组访问的情况下，无法对OP进行优化。 - Diego Sevilla

3

@ Jens：短路求值不是强制要求的。代码只需要表现得好像它进行了短路计算；编译器可以使用任何手段来实现结果。 - user1084944

@DiegoSevilla 你认为为什么会有预测的限制？ - SomeWittyUsername

显示剩余3条评论

-2

这可能是因为当您使用逻辑运算符&&时，编译器必须检查两个条件以使if语句成功。然而，在第二种情况下，由于您将int值隐式转换为bool，编译器基于传递的类型和值以及（可能）单个跳转条件做出一些假设。编译器还可以通过位移完全优化jmps。

- CustodianSigma

8

跳跃的原因在于第二个条件只有在第一个条件为真时才会被评估。除此之外，代码不得以其他方式进行评估，因此编译器不能更好地优化它并仍然保持正确性（除非它能推断第一个语句始终为真）。 - rubenvb

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cody Gray · Accepted Answer

逻辑 AND 运算符（&&）使用短路评估，这意味着仅当第一个比较的结果为 true 时才执行第二个测试。这往往恰好是您所需要的语义。例如，请考虑以下代码：

if ((p != nullptr) && (p->first > 0))

在解引用指针之前，必须确保指针非空。如果这不是一个短路求值，那么由于您将解引用一个空指针，您的行为将是未定义的。

此外，在条件的计算过程是一个昂贵的操作时，采用短路求值也可能会带来性能上的提升。例如：

if ((DoLengthyCheck1(p) && (DoLengthyCheck2(p))

如果 DoLengthyCheck1 失败，那么调用 DoLengthyCheck2 就没有意义。

然而，在结果二进制文件中，短路操作通常会导致两个分支，因为这是编译器保留这些语义最简单的方法。（这也是为什么在另一方面，短路求值有时会抑制优化潜力。）您可以通过查看由 GCC 5.4 为您的 if 语句生成的相关对象代码部分来看到这一点：

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L5

    cmp     ax, 478           ; (l[i + shift] < 479)
    ja      .L5

    add     r8d, 1            ; nontopOverlap++

您可以在这里看到两个比较（cmp指令），每个比较后面都跟着单独的条件跳转/分支（ja，或者如果大于则跳转）。

一般的经验法则是应该避免在紧密循环中使用分支，因为分支速度慢。这几乎适用于所有的x86处理器，从不起眼的8088（其缓慢的取指时间和极小的预取队列[可与指令高速缓存相比]，再加上完全缺乏分支预测，意味着执行分支需要清空缓存），到现代实现（由于长流水线，分支预测错误同样代价高昂）。请注意我刚才所说的小小警告。自Pentium Pro以来，现代处理器已经拥有了先进的分支预测引擎，旨在最小化分支的代价。如果分支的方向能够被正确预测，则代价是极小的。大多数情况下，这很有效，但是如果你陷入了分支预测器不支持的特殊情况，则你的代码可能会变得极慢。这可能是你来到这里的原因，因为你说你的数组是未排序的。

您说基准测试确认将&&替换为*可以使代码明显加快。这是由于当我们比较相关的目标代码部分时，原因就很明显了:

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    xor     r15d, r15d        ; (curr[i] < 479)
    cmp     r13w, 478
    setbe   r15b

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     ax, 478
    setbe   r14b

    imul    r14d, r15d        ; meld results of the two comparisons

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

有点违反直觉的是，这种方法可能会更快，因为这里有更多的指令，但是这就是优化有时候的原理。在这里可以看到相同的比较（cmp），但现在每一个都在xor之前并在setbe之后。XOR只是一种清除寄存器的标准技巧。setbe是一种基于标记值设置位的x86指令，并且经常用于实现无分支代码。在这里，setbe是ja的反义词。如果比较小于等于，它将其目标寄存器设置为1（由于寄存器预先被置零，否则它将为0），而ja则在比较大于时跳转。一旦这两个值在r15b和r14b寄存器中获取，它们将使用imul相乘。传统上，乘法是一种相对较慢的操作，但在现代处理器上非常快，尤其是因为它只是在两个字节大小的值之间进行乘法运算。

你也可以用按位与运算符（&）来替换乘法运算符，它不会做短路评估。这使得代码更加清晰，并且是编译器通常能够识别的一种模式。但是，当你将代码用GCC 5.4编译并使用按位与运算符替换乘法时，它仍然会发出第一个分支。

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13w, 478         ; (curr[i] < 479)
    ja      .L4

    cmp     ax, 478           ; (l[i + shift] < 479)
    setbe   r14b

    cmp     r14d, 1           ; nontopOverlap++
    sbb     r8d, -1

从技术上讲，它没有必要以这种方式发出代码，但由于某种原因，它的内部启发式告诉它这样更快。如果分支预测器在您的一侧，则可能会更快，但是如果分支预测失败的次数比成功的次数多，则可能会更慢。

新一代编译器（以及其他编译器，如Clang）知道这个规则，并且有时会使用它来生成您手动优化所寻求的相同代码。我经常看到Clang将&&表达式转换为与使用&时发出的相同代码。以下是使用普通的&&运算符您的代码在GCC 6.2中的相关输出：

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L7

    xor     r14d, r14d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r14b

    add     esi, r14d         ; nontopOverlap++

请注意这个方法实现得有多么巧妙！它使用了带符号条件(jg和setle)而不是无符号条件(ja和setbe)，但这并不重要。你可以看到它仍然像老版本一样对第一个条件进行比较和分支，使用相同的setCC指令为第二个条件生成无分支代码，但在增量方面效率提高了很多。它不再执行第二个冗余比较来设置sbb操作的标志，而是利用r14d将是1或0的知识，将这个值无条件地添加到nontopOverlap中。如果r14d为0，则加法是空操作；否则，它与应该执行的完全相同，加1。

当你使用短路运算符&&时，GCC 6.2实际上会产生更有效率的代码，而不是按位&运算符：

    movzx   r13d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r13d, 478         ; (curr[i] < 479)
    jg      .L6

    cmp     eax, 478          ; (l[i + shift] < 479)
    setle   r14b

    cmp     r14b, 1           ; nontopOverlap++
    sbb     esi, -1

这里仍然有分支和条件设置，但现在它回到了不那么聪明的递增nontopOverlap的方式。这是一个重要的教训，告诉我们在试图超越编译器时应该小心！

但是，如果你能用基准测试证明分支代码实际上更慢，那么尝试超越编译器可能会产生回报。你只需要仔细检查反汇编代码，并准备好在升级到编译器的较新版本时重新评估你的决策。例如，你可以将代码重写为：

nontopOverlap += ((curr[i] < 479) & (l[i + shift] < 479));

这里根本没有if语句，绝大多数编译器都不会考虑生成分支代码。GCC也不例外；所有版本都会生成类似以下的内容：

    movzx   r14d, WORD PTR [rbp+rcx*2]
    movzx   eax,  WORD PTR [rbx+rcx*2]

    cmp     r14d, 478         ; (curr[i] < 479)
    setle   r15b

    xor     r13d, r13d        ; (l[i + shift] < 479)
    cmp     eax, 478
    setle   r13b

    and     r13d, r15d        ; meld results of the two comparisons
    add     esi, r13d         ; nontopOverlap++

如果您一直在关注之前的示例，这对您来说应该非常熟悉。两个比较都是以无分支的方式完成的，中间结果进行and运算，然后将此结果（可能为0或1）添加到nontopOverlap。如果您想要无分支代码，这几乎可以确保您得到它。

GCC 7变得更加智能了，它现在生成的代码与原始代码基本相同（除了一些指令的略微重新排列）。所以，回答你的问题，“为什么编译器会这样做？”可能是因为它们不完美！它们试图使用启发式方法生成最优化的代码，但并不总是做出最佳决策。但至少它们可以随着时间变得更加智能！

从某种角度来看，这种情况下，具有分支的代码具有更好的最佳性能。如果分支预测成功，跳过不必要的操作将导致稍快的运行时间。但是，无分支代码具有更好的最坏性能。如果分支预测失败，则执行一些额外的指令以避免分支肯定比错误预测的分支更快。即使是最聪明和最巧妙的编译器也很难做出这个选择。

至于您是否需要注意这种情况，答案几乎肯定是否定的，除非在您试图通过微优化来加快某些热循环的速度时。然后，您可以通过反汇编来查找调整方法。正如我之前所说的，要准备好在更新到新版本编译器时重新审视这些决策，因为它可能会对您的棘手代码做出愚蠢的操作，或者它可能已经改变了其优化启发式方法，从而您可以回到使用原始代码。注释要充分！