GCC 5.4.0的一次昂贵的跳跃

我有一个这样的函数(只显示重要部分) :

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毫秒。在将条件更改为 bool 乘法(使代码看起来像这样)之后:

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似乎不再生成这样的指令了。

找到这种加速代码的方法是相当可怕的，而且花了相当长的时间。为什么编译器会这样？它是否是有意的，是否是程序员应该注意的东西？还有其他类似的东西吗？

10273 次浏览
小开

这可能是因为在使用逻辑运算符 &&时，编译器必须检查两个条件才能使 if 语句成功。但是在第二种情况下，由于您隐式地将 int 值转换为 bool，编译器根据传入的类型和值以及(可能)单个跳转条件做出一些假设。也有可能编译器通过位移完全优化了 jmps。

小开

操作员执行短路求值。这意味着只有当第一个操作数的计算结果为 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)，然后检查输出并跳转到 g(x)的计算，当 true为 true时。否则它将离开函数。

相反，使用“布尔”乘法每次都会强制对两个操作数求值，因此不需要跳转。

根据不同的数据，跳转可能会导致速度变慢，因为它会干扰 CPU 的管道和其他东西，比如 Speculative_execution。通常分支预测会有所帮助，但是如果您的数据是随机的，那么可以预测的东西就不多了。

小开
最佳答案

逻辑 AND 操作符(&&)使用短路求值，这意味着只有当第一个比较的结果为 true 时，才会进行第二个测试。这通常正是您所需要的语义。例如，考虑以下代码:

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

在解除引用之前，必须确保指针是非空的。如果这个 abc0是一个短路求值，那么你就有了未定义行为，因为你解除了一个空指针的引用。

在评估条件是一个昂贵的过程的情况下，短路评估也有可能产生性能增益。例如:

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

这有点违反直觉，因为这里有 xor0指令，所以可以更快，但有时优化就是这样工作的。您可以在这里看到同样的比较(cmp) ，但是现在，每个比较前面都有一个 xor，后面跟着一个 setbe。异或只是清除寄存器的标准技巧。setbe是一个 x86指令，它根据标志的值设置一个位，通常用于实现无分支代码。在这里，setbe是 ja的倒数。如果比较低于或等于(因为寄存器已经预先归零，否则它的目标寄存器将为0) ，则它将其目标寄存器设置为1，而如果比较高于此值，则 ja将分支。一旦在 r15b和 r14b寄存器中获得了这两个值，就可以使用 imul将它们相乘。乘法传统上是一个相对较慢的操作，但它在现代处理器上非常快，这将是特别快的，因为它只是乘以两个字节大小的值。

你可以很容易地用按位 AND 运算符(&)替换乘法运算，因为它不做短路求值运算。这使得代码更加清晰，并且是编译器通常能够识别的模式。但是，当您使用代码执行此操作并使用 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，则加法为 no-op; 否则，它将添加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语句，绝大多数编译器也不会考虑为此发出分支代码。海湾合作委员会也不例外; 所有版本都生成类似于以下内容的东西:

    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)是 add到 nontopOverlap。如果您想要无分支代码，这实际上可以确保您得到它。

海湾合作委员会第七届会议变得更聪明了。它现在为上述技巧生成与原始代码几乎相同的代码(除了一些轻微的指令重新排列)。所以，你的问题的答案，“为什么编译器会这样?”，可能是因为他们不是完美的！他们尝试使用启发式方法来生成尽可能最优的代码，但是他们并不总是做出最好的决定。但至少他们可以随着时间变得更聪明！

观察这种情况的一种方法是分支代码具有更好的 最好的情况性能。如果分支预测成功，那么跳过不必要的操作将导致运行时间稍微快一些。但是，无分支代码具有更好的 最坏的情况性能。如果分支预测失败，执行一些必要的额外指令以避免分支，那么 当然会比预测错误的分支更快。即使是最聪明、最聪明的编译器也很难做出这样的选择。

对于程序员是否需要注意这个问题，答案几乎可以肯定是否定的，除了在某些热循环中，您正试图通过微优化来加速这些热循环。然后，你坐下来进行反汇编，并找到调整它的方法。而且，正如我之前所说的，当你更新到一个新版本的编译器时，要准备好重新考虑这些决定，因为它可能会对你的复杂代码做一些愚蠢的事情，或者它可能已经改变了它的优化启发式，足以让你可以回到使用你的原始代码。彻底的评论！

小开

值得注意的一点是

(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) {
// ...

提交答案