GCC 5.4.0 的一次昂贵的跳跃

逻辑 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

这可能会更快，这有点违反直觉，因为这里有 more 指令，但有时优化就是这样工作的。您会在此处看到相同的比较 (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++

注意 this 是多么的聪明！它使用有符号条件（jg 和 setle）而不是无符号条件（ja 和 setbe），但这并不重要。您可以看到它仍然像旧版本一样对第一个条件执行比较和分支，并使用相同的 setCC 指令为第二个条件生成无分支代码，但它的效率要高得多做增量。它没有进行第二次冗余比较来设置 sbb 操作的标志，而是使用 r14d 将是 1 或 0 的知识简单地无条件地将此值添加到 nontopOverlap。如果 r14d 为 0，则加法是空操作；否则，它会加 1，就像它应该做的那样。

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

    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一起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 为假

+ shift < 0 或 i + shift >= l.size() 为真

那么表达式 (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";
  }
}

The assembler output can be found here。

您可以看到生成的代码首先调用 f(x)，然后检查输出并在 true 时跳转到 g(x) 的评估。否则它将离开该功能。

使用“布尔”乘法代替每次都强制计算两个操作数，因此不需要跳转。

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

---

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

---