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

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

Answer 1

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

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

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

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

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

    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++

    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。异或只是清除寄存器的标准技巧。setbe是一个x86指令，它根据标志的值设置一个位，通常用于实现无分支代码。这里，setbe是ja的反义词。如果比较值低于或等于，它将目标寄存器设置为1（由于寄存器已预置零，否则将为0)，而如果比较值高于，则ja分支。在R15b和R14b寄存器中获得这两个值后，使用IMUL将它们相乘。乘法在传统上是一个相对较慢的操作，但在现代处理器上它的速度非常快，这将是特别快的，因为它只乘两个字节大小的值。

您也可以很容易地用按位AND运算符(&)替换乘法，该运算符不进行短路评估。这使得代码更加清晰，并且是编译器普遍认可的一种模式。但当您使用代码执行此操作并使用GCC5.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将&表达式转换为与使用&时发出的代码相同的代码。以下是GCC6.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++

    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 += ((curr[i] < 479) & (l[i + shift] < 479));

    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++

如果您一直在学习前面的示例，那么您应该对此非常熟悉。这两个比较都是以无分支的方式完成的，中间结果是和ed，然后这个结果（将是0或1）是added tonontopoverlap。如果你想要无分支的代码，这实际上会确保你得到它。

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

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