GCC 5.4.0 的昂贵跳跃
An expensive jump with 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 毫秒。将条件更改为布尔乘法后（使代码看起来像这样）：
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，在检查 the generated asm code using godbolt.org 之后，我发现第一个示例会生成跳转，而第二个则不会。我决定尝试 GCC 6.2.0，它在使用第一个示例时也会生成跳转指令，但 GCC 7 似乎不再生成跳转指令。
找出这种加速代码的方法是相当可怕的，需要相当长的时间。为什么编译器会这样？它是有意的吗？程序员应该注意吗？还有类似的吗？
这可能是因为当您使用逻辑运算符 && 时，编译器必须检查两个条件才能使 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";
}
}
The assembler output can be found here.
您可以看到生成的代码首先调用 f(x)，然后检查输出并跳转到 g(x) 的计算，当时这是 true。否则它离开函数。
改为使用 "boolean" 乘法，每次都强制计算两个操作数，因此不需要跳转。
根据数据的不同，跳转可能会导致速度变慢，因为它会干扰 CPU 的管道和推测执行等其他事情。通常分支预测会有所帮助，但如果你的数据是随机的，那么就没有多少可以预测的了。
逻辑与运算符 (&&) 使用短路评估，这意味着只有在第一次比较的评估结果为真时才进行第二次测试。这通常正是您需要的语义。例如，考虑以下代码：
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 指令），每个比较后跟一个单独的条件 jump/branch（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 将它们相乘。乘法传统上是一个相对较慢的操作，但在现代处理器上它非常快，而且这将特别快，因为它只乘以两个字节大小的值。
您可以轻松地将乘法替换为按位与运算符 (&)，它不进行短路计算。这使代码更加清晰，并且是编译器普遍认可的模式。但是当你对你的代码执行此操作并使用 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 语句，绝大多数编译器永远不会考虑为此发出分支代码。海湾合作委员会也不例外；所有版本都会生成类似于以下内容的内容：
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 变得更加智能。它现在为上述技巧生成与原始代码几乎相同的代码（除了指令的一些轻微重新排列）。所以，您的问题 "Why does the compiler behave this way?" 的答案可能是因为它们并不完美！他们尝试使用启发式方法生成尽可能最佳的代码，但他们并不总是做出最佳决策。但至少他们可以随着时间的推移变得更聪明！
查看这种情况的一种方式是分支代码具有更好的最佳情况性能。如果分支预测成功，跳过不必要的操作将导致 运行 时间稍快。但是，无分支代码具有更好的 worst-case 性能。如果分支预测失败，执行一些必要的附加指令以避免分支将 绝对 比错误预测的分支更快。即使是最聪明最聪明的编译器也很难做出这个选择。
关于您是否认为这是程序员需要注意的问题，答案几乎肯定是否定的，除了在您试图通过微优化加速的某些热循环中。然后，您坐下来进行反汇编并找到调整它的方法。而且，正如我之前所说，当您更新到较新版本的编译器时，请准备好重新审视这些决定，因为它可能会对您的棘手代码做一些愚蠢的事情，或者它可能已经改变了它的优化启发式方法，以至于您可以返回使用您的原始代码。评论彻底！
需要注意的一件重要事情是
(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] 在不需要的情况下永远不会导致段错误。
简而言之，原始代码提供的优化机会少于后者。 （当然，编译器是否识别机会是一个完全不同的问题）
您可以通过以下方式修复原始版本
bool t1 = (curr[i] < 479);
bool t2 = (l[i + shift] < 479);
if (t1 && t2) {
// ...
我有一个看起来像这样的函数（只显示重要部分）：
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 毫秒。将条件更改为布尔乘法后（使代码看起来像这样）：
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，在检查 the generated asm code using godbolt.org 之后，我发现第一个示例会生成跳转，而第二个则不会。我决定尝试 GCC 6.2.0，它在使用第一个示例时也会生成跳转指令，但 GCC 7 似乎不再生成跳转指令。
找出这种加速代码的方法是相当可怕的，需要相当长的时间。为什么编译器会这样？它是有意的吗？程序员应该注意吗？还有类似的吗？
这可能是因为当您使用逻辑运算符 && 时，编译器必须检查两个条件才能使 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";
}
}
The assembler output can be found here.
您可以看到生成的代码首先调用 f(x)，然后检查输出并跳转到 g(x) 的计算，当时这是 true。否则它离开函数。
改为使用 "boolean" 乘法，每次都强制计算两个操作数，因此不需要跳转。
根据数据的不同，跳转可能会导致速度变慢，因为它会干扰 CPU 的管道和推测执行等其他事情。通常分支预测会有所帮助，但如果你的数据是随机的，那么就没有多少可以预测的了。
逻辑与运算符 (&&) 使用短路评估，这意味着只有在第一次比较的评估结果为真时才进行第二次测试。这通常正是您需要的语义。例如，考虑以下代码：
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 指令），每个比较后跟一个单独的条件 jump/branch（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 将它们相乘。乘法传统上是一个相对较慢的操作，但在现代处理器上它非常快，而且这将特别快，因为它只乘以两个字节大小的值。
您可以轻松地将乘法替换为按位与运算符 (&)，它不进行短路计算。这使代码更加清晰，并且是编译器普遍认可的模式。但是当你对你的代码执行此操作并使用 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 语句，绝大多数编译器永远不会考虑为此发出分支代码。海湾合作委员会也不例外；所有版本都会生成类似于以下内容的内容：
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 变得更加智能。它现在为上述技巧生成与原始代码几乎相同的代码（除了指令的一些轻微重新排列）。所以，您的问题 "Why does the compiler behave this way?" 的答案可能是因为它们并不完美！他们尝试使用启发式方法生成尽可能最佳的代码，但他们并不总是做出最佳决策。但至少他们可以随着时间的推移变得更聪明！
查看这种情况的一种方式是分支代码具有更好的最佳情况性能。如果分支预测成功，跳过不必要的操作将导致 运行 时间稍快。但是，无分支代码具有更好的 worst-case 性能。如果分支预测失败，执行一些必要的附加指令以避免分支将 绝对 比错误预测的分支更快。即使是最聪明最聪明的编译器也很难做出这个选择。
关于您是否认为这是程序员需要注意的问题，答案几乎肯定是否定的，除了在您试图通过微优化加速的某些热循环中。然后，您坐下来进行反汇编并找到调整它的方法。而且，正如我之前所说，当您更新到较新版本的编译器时，请准备好重新审视这些决定，因为它可能会对您的棘手代码做一些愚蠢的事情，或者它可能已经改变了它的优化启发式方法，以至于您可以返回使用您的原始代码。评论彻底！
需要注意的一件重要事情是
(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] 在不需要的情况下永远不会导致段错误。
简而言之，原始代码提供的优化机会少于后者。 （当然，编译器是否识别机会是一个完全不同的问题）
您可以通过以下方式修复原始版本
bool t1 = (curr[i] < 479);
bool t2 = (l[i + shift] < 479);
if (t1 && t2) {
// ...