与GCC 5.4.0昂贵的跳跃
我有一个这样的function（只显示重要部分）：
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++; } ... } ... } 这样写的，function在我的机器上花了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++; } ... } ... }
执行时间减less到~19ms。
使用的编译器是GCC 5.4.0和-O3，使用godbolt.org检查生成的asm代码后，我发现第一个例子产生了一个跳转，而第二个例子没有。 我决定尝试GCC 6.2.0，它在使用第一个例子的时候也会生成一个跳转指令，但是GCC 7似乎不再生成一个。
找出这种方式来加快代码是相当可怕的，花了相当一段时间。 为什么编译器这样做？ 它是有意的，是程序员应该注意的东西吗？ 还有更多类似的东西吗？
编辑：链接到godbolt https://godbolt.org/g/5lKPF3
逻辑AND运算符（ && ）使用短路评估，这意味着只有在第一个比较结果为真时才进行第二个testing。 这通常正是你所需要的语义。 例如，请考虑以下代码：
if ((p != nullptr) && (p->first > 0))
在取消引用之前，您必须确保指针非空。 如果这不是一个短路评估，你会有未定义的行为，因为你会解引用一个空指针。
在条件评估是昂贵的过程的情况下，短路评估也可能产生性能增益。 例如：
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（其缓慢的提取时间和极小的预取队列（与指令caching相当），加上完全缺less分支预测，意味着采用分支需要caching被转储）到现代实现（其长pipe道使预测错误的分支同样昂贵）。 注意我在那里滑过的小警告。 自Pentium Pro以来，现代处理器拥有先进的分支预测引擎，旨在最大限度地降低分支机构的成本。 如果分支的方向可以正确预测，成本是最小的。 大多数情况下，这种方法运行良好，但是如果您遇到分支预测器不在您身边的病例， 您的代码可能会变得非常缓慢 。 这大概是你在这里，因为你说你的arrays是未分类的。
你说基准证实，用*代替&&使得代码明显更快。 当我们比较目标代码的相关部分时，原因很明显：
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的倒数。 如果比较结果低于或等于（因为寄存器被预先置零，否则它将为0），所以它将目的地寄存器设置为1，而如果比较结果在上面则分支。 一旦在r15b和r14b寄存器中获得了这两个值，就用imul它们相乘。 乘法传统上是一个相对较慢的操作，但在现代处理器上运行速度非常快，而且速度特别快，因为它只乘以两个字节大小的值。
您可以轻易地用乘以位运算符（ & ）来replace乘法运算符（ & ），这不会进行短路评估。 这使代码更清晰，是编译器普遍认可的模式。 但是当你用你的代码做这个，用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将&&expression式翻译为如果我已经使用&会发出相同的代码。 以下是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指令为第二个条件生成无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的不太聪明的方式。 这是一个重要的教训，你为什么在试图超出你的编译器时应该小心！
但是如果你可以用基准testing来certificate分支代码实际上比较慢，那么可能会花费更多的时间来试图编译器。 您只需仔细检查反汇编就能做到这一点 – 并准备在升级到更高版本的编译器时重新评估您的决定。 例如，您拥有的代码可以被重写为：
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++
如果你一直跟着前面的例子，这应该看起来很熟悉。 这两个比较都是以无分支方式完成的，中间结果被编辑在一起，然后这个结果（它将是0或1）被add到nontopOverlap 。 如果你想分支代码，这实际上确保你得到它。
GCC 7变得更聪明了。 它现在生成几乎相同的代码（除了一些轻微的指令重新排列）为上述技巧作为原始代码。 所以，你的问题的答案是“编译器为什么这样做？” ，可能是因为他们不完美！ 他们尝试使用启发式方法来生成最优化的代码，但他们并不总是做出最好的决定。 但至less他们可以随着时间变得更聪明！
查看这种情况的一种方法是分支代码具有更好的最佳性能。 如果分支预测成功，跳过不必要的操作会导致运行时间稍微加快。 但是，无分支代码具有更好的最坏情况性能。 如果分支预测失败，则必要时执行一些额外的指令以避免分支，肯定会比错误预测的分支快。 即使是最聪明，最聪明的编译器也很难做出这样的select。
对于程序员是否需要注意的问题，答案几乎肯定是否定的，除非在某些热循环中，您正试图通过微观优化加速。 然后，你坐下来拆卸，并find方法来调整它。 而且，正如我之前所说的，当你更新到更新版本的编译器时，准备重新审视这些决定，因为它可能会对你的棘手的代码做些愚蠢的事情，或者可能已经改变了它的优化启发式，使用您的原始代码。 彻底评论！
重要的是要注意的是
(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()为真
那么expression式(curr[i] < 479) && (l[i + shift] < 479)保证是一个定义良好的布尔值。 例如，它不会导致分段错误。
然而，在这种情况下，expression式(curr[i] < 479) * (l[i + shift] < 479)是不确定的行为 。 允许导致分段错误。
这意味着对于原始的代码片段，例如，编译器不能只编写一个循环来执行比较并执行一个操作，除非编译器也能够certificatel[i + shift]永远不会导致段错误这是一个不需要的情况。
简而言之，原始代码比后者提供更less的优化机会。 （当然，编译器是否认识到这个机会是一个完全不同的问题）
你可以修改原来的版本，而不是做
bool t1 = (curr[i] < 479); bool t2 = (l[i + shift] < 479); if (t1 && t2) { // ...
&&运营商实施短路评估。 这意味着第二个操作数只有在第一个操作数为真时才被计算。 这肯定会导致这种情况的发生。
你可以创build一个小例子来显示这个：
#include <iostream> bool f(int); bool g(int); void test(int x, int y) { if ( f(x) && g(x) ) { std::cout << "ok"; } }
汇编输出可以在这里find 。
你可以看到生成的代码首先调用f(x) ，然后检查输出并跳转到g(x)结果。 否则它会离开该function。
每次使用“布尔”乘法强制评估两个操作数，因此不需要跳转。
根据数据的不同，跳转可能会导致缓慢，因为它干扰了CPU的pipe道以及诸如推测性执行等其他事情。 通常分支预测是有帮助的，但是如果你的数据是随机的，那么可以预测的分支就不多了。
这可能是因为在使用逻辑运算符&& ，编译器必须检查if语句是否成功的两个条件。 然而，在第二种情况下，因为您隐式地将int值转换为bool，所以编译器根据传入的types和值进行一些假设，以及（可能）一个跳转条件。 编译器还可以通过位移完全优化jmp。
