c++ - GCC 5.4.0 的昂贵跳跃

Question

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

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

执行时间减少到~19ms。
使用的编译器是 GCC 5.4.0 和 -O3检查后the generated asm code using godbolt.org我发现第一个例子产生了一个跳跃，而第二个没有。我决定尝试 GCC 6.2.0，它在使用第一个示例时也会生成跳转指令，但 GCC 7 似乎不再生成跳转指令。
找到这种加速代码的方法是相当可怕的，而且需要花费相当长的时间。为什么编译器会这样？它是有意为之吗，程序员应该注意什么？还有更多类似的东西吗？

Answer 1

逻辑 AND 运算符 ( && ) 使用短路评估，这意味着仅当第一次比较评估为真时才进行第二次测试。这通常正是您需要的语义。例如，考虑以下代码:

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

在取消引用它之前，您必须确保该指针不为空。如果这不是短路评估，您将有未定义的行为，因为您将取消引用空指针。

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

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

如 DoLengthyCheck1失败，拨打 DoLengthyCheck2 毫无意义.

但是，在生成的二进制文件中，短路操作通常会导致两个分支，因为这是编译器保留这些语义的最简单方法。 (这就是为什么，另一方面，短路评估有时会抑制优化潜力。)您可以通过查看为您的 if 生成的目标代码的相关部分来了解这一点。 GCC 5.4 的声明:

    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 以来的现代处理器具有先进的分支预测引擎，旨在最大限度地降低分支成本。如果可以正确预测分支的方向，则成本最小。大多数情况下，这很有效，但如果您遇到分支预测器不在您身边的病理情况，your code can get extremely slow .这大概是你在这里的地方，因为你说你的数组是未排序的。

你说基准测试确认替换&&与 *使代码明显更快。当我们比较目标代码的相关部分时，原因很明显:

    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 相乘.乘法传统上是一种相对较慢的操作，但在现代处理器上它非常快，而且这将特别快，因为它只乘以两个字节大小的值。

您可以很容易地用按位 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，则加法为空操作；否则，它会加 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声明在这里，绝大多数编译器永远不会考虑为此发出分支代码。海湾合作委员会也不异常(exception)；所有版本都会生成类似于以下内容的内容:

    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 变得更加智能。它现在为上述技巧生成与原始代码几乎相同的代码(除了一些轻微的指令重新排列)。所以，你的问题的答案，“为什么编译器会这样？”，可能是因为它们并不完美!他们尝试使用启发式方法来生成尽可能最佳的代码，但他们并不总是做出最好的决定。但至少他们可以随着时间的推移变得更聪明!

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

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