这是一段C ++代码，显示了一些非常特殊的行为。由于某些奇怪的原因，奇迹般地对数据进行排序使代码快了将近六倍：
#include <algorithm> #include <ctime> #include <iostream> int main() { // Generate data const unsigned arraySize = 32768; int data[arraySize]; for (unsigned c = 0; c < arraySize; ++c) data[c] = std::rand() % 256; // !!! With this, the next loop runs faster. std::sort(data, data + arraySize); // Test clock_t start = clock(); long long sum = 0; for (unsigned i = 0; i < 100000; ++i) { // Primary loop for (unsigned c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC; std::cout << elapsedTime << std::endl; std::cout << "sum = " << sum << std::endl; }
import java.util.Arrays; import java.util.Random; public class Main { public static void main(String[] args) { // Generate data int arraySize = 32768; int data[] = new int[arraySize]; Random rnd = new Random(0); for (int c = 0; c < arraySize; ++c) data[c] = rnd.nextInt() % 256; // !!! With this, the next loop runs faster Arrays.sort(data); // Test long start = System.nanoTime(); long sum = 0; for (int i = 0; i < 100000; ++i) { // Primary loop for (int c = 0; c < arraySize; ++c) { if (data[c] >= 128) sum += data[c]; } } System.out.println((System.nanoTime() - start) / 1000000000.0); System.out.println("sum = " + sum); } }
具有类似但不太极端的结果。
我首先想到的是排序将数据带入缓存，但是后来我想到这是多么愚蠢，因为刚刚生成了数组。
您是分支预测失败的受害者。
什么是分支预测？ 考虑一个铁路枢纽：
该图显示了铁路枢纽 Mecanismo的图片，通过Wikimedia Commons。在CC-By-SA 3.0许可下使用。
现在，为了争论起见，假设这是在1800年代-在进行长距离或无线电通信之前。
您是路口的操作员，并且听到火车驶入。您不知道应该走哪条路。您停下火车，询问驾驶员他们想要哪个方向。然后您适当地设置开关。
火车很重，惯性很大。因此，它们花了永远的时间来启动和减速。
有没有更好的办法？您猜火车将朝哪个方向行驶！
考虑一个if语句：在处理器级别，它是一条分支指令：
包含if语句的已编译代码的屏幕截图
您是处理器，并且看到一个分支。您不知道它将走哪条路。你是做什么？您停止执行并等待之前的指令完成。然后，您沿着正确的路径继续。
现代处理器很复杂，而且流程很长。因此，他们需要永远“热身”和“放慢脚步”。
有没有更好的办法？您猜分支将朝哪个方向前进！
这是分支预测。我承认这不是最好的类比，因为火车可以只用一个标志来指示方向。但是在计算机中，处理器直到最后一刻才知道分支的方向。
那么，您如何从战略上猜测如何将火车必须倒退和走另一条路的次数降至最低？您看看过去的历史！如果火车有99％的时间向左行驶，那么您就猜到了。如果它交替出现，那么您将交替猜测。如果它每三回去一次，您会猜到相同…
换句话说，您尝试识别模式并遵循它。这或多或少是分支预测变量的工作方式。
大多数应用程序具有行为良好的分支。因此，现代分支预测器通常将达到90％以上的命中率。但是，当面对没有可识别模式的不可预测分支时，分支预测变量实际上是无用的。
从上面暗示，罪魁祸首是这个if陈述：
if (data[c] >= 128) sum += data[c];
请注意，数据在0到255之间均匀分布。对数据进行排序时，大约前一半的迭代将不会进入if语句。之后，他们都会进入if语句。
这对分支预测器非常友好，因为分支连续多次朝同一方向前进。即使是简单的饱和计数器也可以正确预测分支，除了在切换方向后进行几次迭代外。
快速可视化：
T = branch taken N = branch not taken data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ... branch = N N N N N ... N N T T T ... T T T ... = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (easy to predict)
但是，当数据完全随机时，分支预测器将变得无用，因为它无法预测随机数据。因此，可能会有大约50％的错误预测（没有比随机猜测好）。
data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ... branch = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ... = TTNTTTTNTNNTTTN ... (completely random - hard to predict)
那该怎么办呢？
如果编译器无法将分支优化为有条件的移动，那么如果您愿意牺牲可读性来提高性能，则可以尝试一些破解。
更换：
与：
int t = (data[c] - 128) >> 31; sum += ~t & data[c];
这消除了分支，并用一些按位运算将其替换。
（请注意，这种破解并不完全等同于原始的if语句。但是在这种情况下，它对于的所有输入值均有效data[]。）
data[]
基准：Core i7 920 @ 3.5 GHz
C ++-Visual Studio 2010-x64版本
// Branch - Random seconds = 11.777 // Branch - Sorted seconds = 2.352 // Branchless - Random seconds = 2.564 // Branchless - Sorted seconds = 2.587
Java-NetBeans 7.1.1 JDK 7-x64
// Branch - Random seconds = 10.93293813 // Branch - Sorted seconds = 5.643797077 // Branchless - Random seconds = 3.113581453 // Branchless - Sorted seconds = 3.186068823
观察结果：
更新：
（或者有点快：对于已经排序的情况，cmov可能会变慢，特别是如果GCC将其放在关键路径上而不是仅仅在add，尤其是在Broadwell之前cmov有2个周期延迟的Intel上：gcc优化标志-O3会使代码比-O2慢）
VC ++ 2010即使在.NET下也无法为该分支生成条件移动/Ox。
英特尔C 编译器（ICC）11起到了神奇的作用。它互换两个循环，从而将不可预测的分支提升到外部循环。因此，它不仅可以避免错误预测，而且还比VC 和GCC生成的速度快两倍！换句话说，ICC利用测试循环击败了基准测试…
如果给Intel编译器提供无分支的代码，它就直接对其进行矢量化处理……并且与分支（通过循环交换）一样快。
分支预测。
对于排序数组，条件data[c] >= 128首先false是值的条纹，然后true是所有后续值的条件。这很容易预测。使用未排序的数组，您需要支付分支成本。
data[c] >= 128
false
true
当对数据进行排序时，性能大幅提高的原因是，消除了分支预测损失，如Mysticial的答案中所详细解释的那样。
现在，如果我们看一下代码
我们可以发现，该特定if...else...分支的含义是在满足条件时添加一些内容。这种类型的分支可以很容易地转化为有条件的举动语句，该语句将被编译成一个条件移动指令：cmovl在一个x86系统中。去除分支并因此去除潜在的分支预测损失。
if...else...
cmovl
x86
在C，因此C++，语句，这将直接编译（不使用任何优化）插入在条件移动指令x86，是三元运算符... ? ... : …。因此，我们将上面的语句重写为等效的语句：
C
C++
... ? ...
sum += data[c] >=128 ? data[c] : 0;
在保持可读性的同时，我们可以检查加速因子。
在Intel Core i7 -2600K @ 3.4 GHz和Visual Studio 2010 Release Mode上，基准是（从Mysticial复制的格式）：
// Branch - Random seconds = 8.885 // Branch - Sorted seconds = 1.528 // Branchless - Random seconds = 3.716 // Branchless - Sorted seconds = 3.71
x64
// Branch - Random seconds = 11.302 // Branch - Sorted seconds = 1.830 // Branchless - Random seconds = 2.736 // Branchless - Sorted seconds = 2.737
在多次测试中，结果是可靠的。当分支结果不可预测时，我们可以大大提高速度，但是当分支结果不可预测时，我们会受到一点损失。实际上，使用条件移动时，无论数据模式如何，性能都是相同的。
现在，让我们通过研究x86它们生成的程序集来更仔细地研究。为简单起见，我们使用两个函数max1和max2。
max1使用条件分支if... else ...：
max1
if... else ...
int max1(int a, int b) { if (a > b) return a; else return b; }
max2使用三元运算符… ? … : …：
int max2(int a, int b) { return a > b ? a : b; }
在x86-64机器上，GCC -S生成以下程序集。
:max1 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl -8(%rbp), %eax jle .L2 movl -4(%rbp), %eax movl %eax, -12(%rbp) jmp .L4 .L2: movl -8(%rbp), %eax movl %eax, -12(%rbp) .L4: movl -12(%rbp), %eax leave ret :max2 movl %edi, -4(%rbp) movl %esi, -8(%rbp) movl -4(%rbp), %eax cmpl %eax, -8(%rbp) cmovge -8(%rbp), %eax leave ret
max2由于使用指令，使用的代码少得多cmovge。但是真正的收益是max2不涉及分支跳转，jmp如果预测结果不正确，则分支跳转将受到重大性能损失。
那么，为什么有条件举动的表现更好呢？
在典型的x86处理器中，一条指令的执行分为几个阶段。大致来说，我们有不同的硬件来处理不同的阶段。因此，我们不必等待一条指令完成就可以开始一条新指令。这称为流水线。
在分支情况下，以下指令由前一条指令确定，因此我们无法进行流水线操作。我们必须等待或预测。
在条件移动的情况下，执行条件移动指令分为几个阶段，但是较早的阶段类似于Fetch并且Decode不依赖于前一条指令的结果。只有后期才需要结果。因此，我们等待一条指令执行时间的一小部分。这就是为什么在容易预测时条件移动版本比分支慢的原因。
《计算机系统：程序员的观点》（第二版）一书对此进行了详细说明。您可以检查第3.6.6节中的“条件移动指令”，整个第4章中的“处理器体系结构”和第5.11.2节中的“分支预测和错误预测惩罚”的特殊处理。
有时，某些现代的编译器可以优化我们的代码以使其具有更好的性能，而某些编译器则不能（以使用Visual Studio的本机编译器为目的）。当情况变得如此复杂以至于编译器无法自动优化它们时，了解分支与条件移动之间的性能差异（这是不可预测的）可以帮助我们编写性能更高的代码。
如果您对可以对此代码进行更多优化感到好奇，请考虑以下事项：
从原始循环开始：
for (unsigned i = 0; i < 100000; ++i) { for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) sum += data[j]; } }
使用循环交换，我们可以安全地将此循环更改为：
for (unsigned j = 0; j < arraySize; ++j) { for (unsigned i = 0; i < 100000; ++i) { if (data[j] >= 128) sum += data[j]; } }
然后，您可以看到if条件在整个i循环执行期间是恒定的，因此您可以if取消：
for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { for (unsigned i = 0; i < 100000; ++i) { sum += data[j]; } } }
然后，您可以看到内部循环可以折叠为一个表达式，假设浮点模型允许（/fp:fast例如，抛出该异常）
for (unsigned j = 0; j < arraySize; ++j) { if (data[j] >= 128) { sum += data[j] * 100000; } }
那是比以前快100,000倍。
毫无疑问，我们中的某些人会对识别对CPU的分支预测器有问题的代码的方式感兴趣。Valgrind工具cachegrind具有一个分支预测器模拟器，可以通过使用该--branch-sim=yes标志来启用它。在此问题的示例上运行它，将外部循环数减少到10000并使用编译g++，得到以下结果：
Valgrind
cachegrind
--branch-sim=yes
g++
排序：
==32551== Branches: 656,645,130 ( 656,609,208 cond + 35,922 ind) ==32551== Mispredicts: 169,556 ( 169,095 cond + 461 ind) ==32551== Mispred rate: 0.0% ( 0.0% + 1.2% ) 未分类： ==32555== Branches: 655,996,082 ( 655,960,160 cond + 35,922 ind) ==32555== Mispredicts: 164,073,152 ( 164,072,692 cond + 460 ind) ==32555== Mispred rate: 25.0% ( 25.0% + 1.2% )
深入研究cg_annotate我们所讨论的循环所产生的逐行输出：
Bc Bcm Bi Bim 10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i) . . . . { . . . . // primary loop 327,690,000 10,016 0 0 for (unsigned c = 0; c < arraySize; ++c) . . . . { 327,680,000 10,006 0 0 if (data[c] >= 128) 0 0 0 0 sum += data[c]; . . . . } . . . . }
未分类：
Bc Bcm Bi Bim 10,001 4 0 0 for (unsigned i = 0; i < 10000; ++i) . . . . { . . . . // primary loop 327,690,000 10,038 0 0 for (unsigned c = 0; c < arraySize; ++c) . . . . { 327,680,000 164,050,007 0 0 if (data[c] >= 128) 0 0 0 0 sum += data[c]; . . . . } . . . . }
这样一来，您可以轻松识别出问题行-在未排序版本中，该if (data[c] >= 128)行在Bcmcachegrind的分支预测器模型下导致164,050,007错误预测的条件分支（），而在排序版本中仅导致10,006。
if (data[c] >= 128)
Bcmcachegrind
另外，在Linux上，您可以使用性能计数器子系统来完成相同的任务，但是使用CPU计数器可以实现本机性能。
perf stat ./sumtest_sorted
Performance counter stats for './sumtest_sorted': 11808.095776 task-clock # 0.998 CPUs utilized 1,062 context-switches # 0.090 K/sec 14 CPU-migrations # 0.001 K/sec 337 page-faults # 0.029 K/sec 26,487,882,764 cycles # 2.243 GHz 41,025,654,322 instructions # 1.55 insns per cycle 6,558,871,379 branches # 555.455 M/sec 567,204 branch-misses # 0.01% of all branches 11.827228330 seconds time elapsed
Performance counter stats for './sumtest_unsorted': 28877.954344 task-clock # 0.998 CPUs utilized 2,584 context-switches # 0.089 K/sec 18 CPU-migrations # 0.001 K/sec 335 page-faults # 0.012 K/sec 65,076,127,595 cycles # 2.253 GHz 41,032,528,741 instructions # 0.63 insns per cycle 6,560,579,013 branches # 227.183 M/sec 1,646,394,749 branch-misses # 25.10% of all branches 28.935500947 seconds time elapsed
它还可以使用反汇编进行源代码注释。
perf record -e branch-misses ./sumtest_unsorted perf annotate -d sumtest_unsorted
Percent | Source code & Disassembly of sumtest_unsorted ------------------------------------------------ ... : sum += data[c]; 0.00 : 400a1a: mov -0x14(%rbp),%eax 39.97 : 400a1d: mov %eax,%eax 5.31 : 400a1f: mov -0x20040(%rbp,%rax,4),%eax 4.60 : 400a26: cltq 0.00 : 400a28: add %rax,-0x30(%rbp) ...
