我有一个函数，看起来像这样(只显示重要部分)：
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似乎不再生成跳转指令了。
找到这种加速代码的方法相当可怕，而且需要相当长的时间。为什么编译器会这样做？它是有意的吗？它是程序员应该注意的吗？还有类似的事情吗？
逻辑AND运算符(&&)使用短路评估，这意味着只有在第一次比较评估为true时才进行第二次测试。这通常正是您所需要的语义。例如，考虑以下代码：
if ((p != nullptr) && (p->first > 0))
在取消引用该指针之前，必须确保该指针为非null。如果此不是短路求值，则会有未定义的行为，因为您将取消引用null指针。
在条件评估是昂贵过程的情况下，短路评估也可能产生性能增益。例如：
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将它们相乘。传统上，乘法运算是一种相对较慢的运算，但在现代处理器上它非常快，而且速度会特别快，因为它只乘以两个字节大小的值。
您可以很容易地用逐位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语句，绝大多数编译器都不会考虑为此发出分支代码。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++
如果你一直在遵循前面的例子，这对你来说应该很熟悉。两个比较都是以无分支的方式进行的，中间结果是anded在一起，然后这个结果(将是0或1)是added到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()为真
则表达式(curr[i] < 479) && (l[i + shift] < 479)保证是一个定义良好的布尔值。例如，它不会导致分段故障。
然而，在这些情况下，表达式(curr[i] < 479) * (l[i + shift] < 479)是未定义的行为；允许导致分段故障。
这意味着，例如，对于原始代码片段，编译器不能只编写一个执行两个比较并执行and操作的循环，除非编译器还可以证明l[i + shift]在要求不执行的情况下永远不会导致segfault。
简而言之，与后者相比，原始代码提供的优化机会更少。(当然，编译器是否意识到机会是一个完全不同的问题)
你可以通过做来修复原始版本
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)，然后检查输出并跳到g(x)的求值(当它是true时)。否则，它将离开函数。
相反，使用"布尔"乘法每次都会强制计算两个操作数，因此不需要跳转。
根据数据的不同，跳跃可能会导致速度减慢，因为它会干扰CPU的管道和其他事情，如推测执行。通常情况下，分支预测会有所帮助，但如果你的数据是随机的，那么就没有多少可以预测的了。
这可能是因为当您使用逻辑运算符&&时，编译器必须检查两个条件才能使if语句成功。然而，在第二种情况下，由于您将int值隐式转换为bool，编译器会根据传入的类型和值以及(可能)单个跳转条件进行一些假设。编译器也有可能通过比特移位来完全优化jmps。