与GCC 5.4.0一起昂贵的跳跃

2018-07-01 03:21:30

我有一个看起来像这样的功能（仅显示重要部分）：

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++;
     }
     ...
  }
...
}

这样写的，功能在我的机器上花了约34ms。将条件更改为布尔乘法（使代码如下所示）：

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++;
     }
     ...
  }
...
}

执行时间减少到~19ms。

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

找出这种方式来加速代码是相当可怕的，并花了相当长的时间。为什么编译器的行为如此？它是有意的，它是程序员应该留意的东西吗？还有更多类似的东西吗？

编辑：链接到godbolt https://godbolt.org/g/5lKPF3

逻辑AND运算符（ && ）使用短路评估，这意味着只有在第一次比较评估为真时才进行第二次测试。这通常正是你所需要的语义。例如，请考虑以下代码：

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 ），但这并不重要。你可以看到它仍然像第一个条件那样执行compare-and-branch，就像旧版本一样，并且使用相同的setCC指令为第二个条件生成无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）是add编到nontopOverlap 。如果你想要无分代码，这实际上可以确保你得到它。

GCC 7变得更加聪明。它现在生成几乎相同的代码（除了一些轻微的指令重新排列）作为原始代码的上述技巧。所以，对于你的问题的答案，“编译器为什么这样做？”，可能是因为它们并不完美！他们尝试使用启发式技术来生成最佳代码，但他们并不总是做出最佳决策。但至少他们可以随着时间的推移变得更聪明！

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

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

重要的是要注意的是

(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()为true

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

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

这意味着，对于原来的代码段，例如，编译器不能只写一个循环执行两种比较和确实的and操作，除非编译器也可证明l[i + shift]绝不会引起在段错误这是一个不需要的情况。

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

您可以通过改为修复原始版本

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

&&运营商实施短路评估。这意味着第二个操作数仅在第一个操作数的计算结果为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的管道和其他事情，如推测性执行。通常分支预测是有帮助的，但是如果你的数据是随机的，那么可以预测的数据就不多。

链接地址: http://www.djcxy.com/p/86849.html

上一篇: An expensive jump with GCC 5.4.0

下一篇: error: comma, colon, decorator or end of line expected after operand