为什么处理排序数组比处理未排序数组快？

您是分支预测失败的受害者。
什么是分支预测？
考虑一个铁路枢纽：
Mecanismo的图片，通过Wikimedia Commons。在CC-By-SA 3.0许可下使用。
现在，为了争论起见，假设这是在1800年代-在进行长距离或无线电通信之前。
您是路口的操作员，并且听到火车驶入。您不知道应该走哪条路。您停下火车，问司机他们想要哪个方向。然后您适当地设置开关。
火车很重，惯性很大。因此，它们花了永远的时间来启动和减速。
有没有更好的办法？您猜火车将朝哪个方向行驶！
如果您猜对了，它将继续进行。
如果您猜错了，机长会停下来，后退并大喊大叫，以拨动开关。然后，它可以沿着其他路径重新启动。
如果您每次都猜对了，火车将永远不会停止。如果您经常猜错，火车将花费大量时间停止，备份和重新启动。
考虑一个if语句：在处理器级别，它是一条分支指令：
您是处理器，并且看到一个分支。您不知道它将走哪条路。你是做什么？您停止执行并等待直到前面的指令完成。然后，您沿着正确的路径继续。
现代处理器很复杂，而且流程很长。因此，他们需要永远“热身”和“放慢脚步”。
有没有更好的办法？您猜分支将朝哪个方向前进！
如果猜对了，则继续执行。
如果您猜错了，则需要刷新管道并回滚到分支。然后，您可以沿着其他路径重新启动。
如果您每次都猜对了，执行将永远不会停止。如果您经常猜错，那么您将花费大量时间来拖延，回滚和重新启动。
这是分支预测。我承认这不是最好的类比，因为火车可以只用一个标志来指示方向。但是在计算机中，处理器直到最后一刻才知道分支的方向。
那么，您如何从战略上猜测如何将火车必须倒退和走另一条路的次数降至最低？您看看过去的历史！如果火车有99％的时间向左行驶，那么您就猜到了。如果它交替出现，那么您将交替猜测。如果它每三回​​去一次，您会猜到相同...
换句话说，您尝试识别一个模式并遵循它。这或多或少是分支预测变量的工作方式。
大多数应用程序具有行为良好的分支。因此，现代分支预测器通常将达到90％以上的命中率。但是，当面对没有可识别模式的不可预测分支时，分支预测变量实际上是无用的。
进一步阅读：Wikipedia上的“分支预测器”文章。
从上面暗示，罪魁祸首是这个if陈述：
如果（data [c]> = 128）
sum + = data [c];
请注意，数据在0到255之间均匀分布。对数据进行排序时，大约前一半的迭代将不会进入if语句。之后，他们都会进入if语句。
这对分支预测器非常友好，因为分支连续多次朝同一方向前进。即使是简单的饱和计数器也可以正确预测分支，除了在切换方向后进行几次迭代外。
快速可视化：
T =采取分支
N =未采取分支
data [] = 0，1，2，3，4，... 126，127，128，129，130，... 250，251，252，...
分支= N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT（易于预测）
但是，当数据完全随机时，分支预测器将变得无用，因为它无法预测随机数据。因此，可能会有大约50％的错误预测（没有比随机猜测好）。
data [] = 226、185、125、158、198、144、217、79、202、118、14、150、177、182、133，...
分支= T，T，N，T，T，T，T，N，T，N，N，T，T，T，N ...
= TTNTTTTNTNNTTTN ...（完全随机-难以预测）
那该怎么办呢？
如果编译器无法将分支优化为有条件的移动，那么如果您愿意牺牲可读性来提高性能，则可以尝试一些破解。
更换：
如果（data [c]> = 128）
sum + = data [c];
与：
int =（data [c]-128）>> 31;
sum + =〜t＆data [c];
这消除了分支，并用一些按位运算将其替换。
（请注意，这种破解并不严格等同于原始的if语句。但是在这种情况下，它对data []的所有输入值均有效。）
基准：Core i7 920 @ 3.5 GHz
C ++-Visual Studio 2010-x64版本
//分支-随机
秒= 11.777
//分支-排序
秒= 2.352
//无分支-随机
秒= 2.564
//无分支-排序
秒= 2.587
Java-NetBeans 7.1.1 JDK 7-x64
//分支-随机
秒= 10.93293813
//分支-排序
秒= 5.643797077
//无分支-随机
秒= 3.113581453
//无分支-排序
秒= 3.186068823
观察结果：
使用分支：排序和未排序的数据之间存在巨大差异。
使用Hack：排序和未排序的数据之间没有区别。
在C ++情况下，对数据进行排序时，hack实际上比分支慢一点。
一般的经验法则是避免在关键循环中避免依赖数据的分支（例如在此示例中）。
更新：
在x64上带有-O3或-ftree-vectorize的GCC 4.6.1能够生成条件移动。因此，已排序和未排序的数据之间没有区别-两者都很快速。
（或者有点快：对于已经排序的情况，cmov可能会变慢，尤其是如果GCC将其放在关键路径上而不是仅仅添加，尤其是在Broadmov之前的Intel上，cmov有2个周期延迟：gcc优化标志-O3使代码变慢比-O2）
即使在/ Ox下，VC ++ 2010也无法为此分支生成条件移动。
英特尔C ++编译器（ICC）11起到了神奇的作用。它互换两个循环，从而将不可预测的分支提升到外部循环。因此，它不仅可以避免错误预测，而且还比VC ++和GCC生成的速度快两倍！换句话说，ICC利用测试循环击败了基准测试...
如果给Intel编译器提供无分支的代码，它将直接对其进行矢量化处理……并且速度与分支一样快（通过循环交换）。
这表明即使是成熟的现代编译器，其优化代码的能力也可能存在巨大差异。
|
分支预测。
对于排序数组，条件data [c]> = 128对于值的条带首先为false，然后对于所有后续值都为true。这很容易预测。使用未排序的数组，您需要支付分支成本。
|
如对Mysticial的回答所解释的那样，当对数据进行排序时，性能大幅提高的原因是删除了分支预测损失。
现在，如果我们看一下代码
如果（data [c]> = 128）
sum + = data [c];
我们可以发现，如果... else ...分支的特定含义是在满足条件时添加一些内容。这种类型的分支可以轻松地转换为条件移动语句，该条件语句将被编译为条件移动指令：cmovl，在x86系统中。去除分支并因此去除潜在的分支预测损失。
在C中，因此在C ++中，将直接（无需任何优化）编译为x86中的条件移动指令的语句就是三元运算符...？ ...：....因此，我们将以上语句重写为等效的语句：
sum + = data [c]> = 128吗？数据[c]：0；
在保持可读性的同时，我们可以检查加速因子。
在Intel Core i7-2600K @ 3.4 GHz和Visual Studio 2010 Release Mode上，基准是（从Mysticial复制的格式）：
x86
//分支-随机
秒= 8.885
//分支-排序
秒= 1.528
//无分支-随机
秒= 3.716
//无分支-排序
秒= 3.71
x64
//分支-随机
秒= 11.302
//分支-排序
秒= 1.830
//无分支-随机
秒= 2.736
//无分支-排序
秒= 2.737
在多次测试中，结果是可靠的。当分支结果不可预测时，我们可以大大提高速度，但是当分支结果不可预测时，我们会受到一些影响。实际上，使用条件移动时，无论数据模式如何，性能都是相同的。
现在，通过研究它们生成的x86程序集，让我们更加仔细地研究。为简单起见，我们使用两个函数max1和max2。
如果... else ...，max1将使用条件分支：
int max1（int a，int b）{
如果（a> b）
返回
其他
返回b;
}
max2使用三元运算符...？ ...：...：
int max2（int a，int b）{
返回a> b？ a：b;
}
在x86-64机器上，GCC -S生成以下程序集。
：最大1
movl％edi，-4（％rbp）
movl％esi，-8（％rbp）
movl -4（％rbp），％eax
cmpl -8（％rbp），％eax
jle .L2
movl -4（％rbp），％eax
move％eax，-12（％rbp）
JMP .L4
.L2：
movl -8（％rbp），％eax
move％eax，-12（％rbp）
.L4：
movl -12（％rbp），％eax
离开
退回
：最大2
movl％edi，-4（％rbp）
movl％esi，-8（％rbp）
movl -4（％rbp），％eax
cmpl％eax，-8（％rbp）
cmovge -8（％rbp），％eax
离开
退回
由于使用指令cmovge，max2使用的代码少得多。但是真正的好处是max2不涉及分支跳转jmp，如果预测的结果不正确，则会对性能造成重大影响。
那么，为什么有条件举动的表现更好呢？
在典型的x86处理器中，一条指令的执行分为几个阶段。大致来说，我们有不同的硬件来处理不同的阶段。因此，我们不必等待一条指令完成就可以开始一条新指令。这称为流水线。
在分支情况下，以下指令由前一条指令确定，因此我们无法进行流水线操作。我们必须等待或预测。
在有条件的情况下执行条件移动指令分为几个阶段，但较早的阶段（如Fetch和Decode）并不取决于前一条指令的结果。只有后期才需要结果。因此，我们等待一条指令执行时间的一小部分。这就是为什么在容易预测时条件移动版本比分支慢的原因。
第二版《计算机系统：程序员的观点》一书对此进行了详细解释。您可以查看第3.6.6节中的“条件移动指令”，整个第4章中的“处理器体系结构”和第5.11.2节中的“分支预测和错误预测惩罚”的特殊处理。
有时，某些现代的编译器可以优化我们的代码以提高汇编性能，而有时某些编译器则不能（问题代码使用Visual Studio的本机编译器）。当情况变得如此复杂以至于编译器无法自动优化它们时，了解分支与条件移动之间的性能差异（这是不可预测的）可以帮助我们编写性能更高的代码。
|
如果您对可以对此代码进行更多优化感到好奇，请考虑以下事项：
从原始循环开始：
对于（无符号i = 0; i <100000; ++ i）
{
for（无符号j = 0; j  = 128）
总和=数据[j];
}
}
使用循环交换，我们可以安全地将此循环更改为：
for（无符号j = 0; j  = 128）
总和=数据[j];
}
}
然后，您可以看到if条件在整个i循环执行期间是恒定的，因此可以将if提升：
for（无符号j = 0; j  = 128）
{
对于（无符号i = 0; i <100000; ++ i）
{
总和==数据[j];
}
}
}
然后，您可以看到内部循环可以折叠为一个表达式，假设浮点模型允许它（例如，抛出/ fp：fast）
for（无符号j = 0; j  = 128）
{
和+ = data [j] * 100000;
}
}
那是比以前快100,000倍。
|
毫无疑问，我们中的某些人会对识别对CPU的分支预测器有问题的代码的方式感兴趣。 Valgrind工具cachegrind具有分支预测器模拟器，可使用--branch-sim = yes标志启用。在此问题的示例上运行它，将外部循环数减少到10000并使用g ++进行编译，得出以下结果：
排序：
== 32551 ==分支机构：656,645,130（656,609,208 cond + 35,922 ind）
== 32551 ==错误预测：169,556（169,095 cond + 461 ind）
== 32551 ==错误率：0.0％（0.0％+ 1.2％）
未分类：
== 32555 ==分支机构：655,996,082（655,960,160 cond + 35,922 ind）
== 32555 ==错误预测：164,073,152（164,072,692 cond + 460 ind）
== 32555 ==错误率：25.0％（25.0％+ 1.2％）
深入研究cg_annotate产生的逐行输出，我们看到了所讨论的循环：
排序：
Bc Bcm Bi Bim
10,001 4 0 0 for（无符号i = 0; i <10000; ++ i）
。 。 。 。 {
。 。 。 。 //主循环
327,690,000 10,016 0 0 for（无符号c = 0; c  = 128）
0 0 0 0 sum + =数据[c];
。 。 。 。 }
。 。 。 。 }
未分类：
Bc Bcm Bi Bim
10,001 4 0 0 for（无符号i = 0; i <10000; ++ i）
。 。 。 。 {
。 。 。 。 //主循环
327,690,000 10,038 0 0 for（无符号c = 0; c  = 128）
0 0 0 0 sum + =数据[c];
。 。 。 。 }
。 。 。 。 }
这使您可以轻松地确定问题行-在未排序版本中，if（data [c]> = 128）行在cachegrind的branch-predictor模型下导致164,050,007错误预测的条件分支（Bcm），而在排序版本中仅导致10,006 。
另外，在Linux上，您可以使用性能计数器子系统来完成相同的任务，但是使用CPU计数器可以实现本机性能。
性能统计./sumtest_sorted
排序：
“ ./sumtest_sorted”的性能计数器统计信息：
11808.095776任务时钟＃0.998使用的CPU
1,062个上下文开关＃0.090 K /秒
14个CPU迁移＃0.001 K /秒
337页错误＃0.029 K /秒
26,487,882,764周期＃2.243 GHz
每个周期41,025,654,322条指令＃1.55 insns
6,558,871,379个分支＃555.455 M / sec
567,204个分支缺失-所有分支的0.01％
经过了11.827228330秒的时间
未分类：
性能“ ./sumtest_unsorted”的计数器统计信息：
28877.954344任务时钟＃0.998使用的CPU
2,584个上下文开关＃0.089 K /秒
18个CPU迁移＃0.001 K /秒
335页错误＃0.012 K /秒
65,076,127,595周期＃2.253 GHz
每个周期41,032,528,741条指令＃0.63 insns
6,560,579,013个分支＃227.183 M / sec
1,646,394,749分行缺失＃占所有分行的25.10％
经过28.935500947秒的时间
它还可以使用反汇编进行源代码注释。
性能记录-e branch-misses ./sumtest_unsorted
性能注释-d sumtest_unsorted
百分比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：添加％rax，-0x30（％rbp）
...
有关更多详细信息，请参见性能教程。
|
我只是阅读了这个问题及其答案，所以我觉得答案丢失了。
我发现在托管语言中消除分支预测特别有效的一种常见方法是使用表查找而不是使用分支（尽管在这种情况下我没有对其进行测试）。
这种方法通常在以下情况下有效：
它是一个小表，可能会缓存在处理器中，并且
您正在以非常紧密的循环运行事物和/或处理器可以预加载数据。
背景以及原因
从处理器的角度来看，您的内存很慢。为了弥补速度上的差异，处理器内置了两个缓存（L1 / L2缓存）。因此，假设您正在执行出色的计算，并发现您需要一块内存。处理器将执行其“加载”操作，并将内存块加载到缓存中-然后使用缓存来执行其余的计算。由于内存相对较慢，因此此“加载”将减慢您的程序的速度。
像分支预测一样，它在奔腾处理器中进行了优化：处理器预测它需要加载一条数据，并在操作实际到达缓存之前尝试将其加载到缓存中。正如我们已经看到的那样，分支预测有时会出现严重的错误-在最坏的情况下，您需要返回并实际上等待内存加载，这将永远耗费时间（换句话说：失败的分支预测很糟糕，内存不足）分支预测失败后的加载太可怕了！）。
对我们来说幸运的是，如果内存访问模式是可预测的，则处理器会将其加载到其快速缓存中，一切都很好。
我们需要知道的第一件事是小的？虽然通常较小是更好的选择，但经验法则是坚持使用<= 4096字节大小的查找表。作为上限：如果您的查找表大于64K，则可能值得重新考虑。
构造表
因此，我们发现可以创建一个小表。接下来要做的就是准备好查找功能。查找功能通常是使用几个基本整数运算（和，或，异或，移位，加法，删除和乘以乘法）的小型函数。您希望通过查找功能将输入转换为表中的某种“唯一键”，然后简单地为您提供所需的所有工作的答案。
在这种情况下：> = 128表示我们可以保留该值，<128表示我们可以摆脱它。最简单的方法是使用“ AND”：如果我们将其保留，则将其与7FFFFFFF进行AND；如果要删除它，则将其与0进行“与”运算。还要注意128是2的幂-因此我们可以继续制作一张32768/128整数的表，并用一个零和很多零填充7FFFFFFFF。
托管语言
您可能想知道为什么这在托管语言中能很好地工作。毕竟，托管语言使用分支检查数组的边界，以确保您不会弄乱……
好吧，不完全是... :-)
关于消除托管语言的此分支，已经进行了很多工作。例如：
对于（int i = 0; i  = 128）吗？ c：0；
}
//测试
DateTime startTime = System.DateTime.Now;
长和= 0;
对于（int i = 0; i <100000; ++ i）
{
//主循环
对于（int j = 0; j  = 128）
sum + = data [c];
问题是：是什么使上述语句在某些情况下（如已排序的数据）无法执行？这是“分支预测器”。分支预测器是一种数字电路，它试图猜测在确定之前知道分支（例如，if-then-else结构）的方向。分支预测器的目的是改善指令管道中的流程。分支预测变量在实现高效能方面起着至关重要的作用！
让我们做一些基准测试以更好地了解它
if语句的性能取决于其条件是否具有可预测的模式。如果条件始终为真或始终为假，则处理器中的分支预测逻辑将选择模式。另一方面，如果模式是不可预测的，则if语句将更加昂贵。
让我们在不同条件下测量此循环的性能：
对于（int i = 0; i  =128。这意味着我们可以轻松地提取单个位来告诉我们是否需要一个值：数据右边的7位，剩下的是0位或1位，我们只想在有1位的情况下将值相加。我们将此位称为“决策位”。
通过将决策位的0/1值用作数组的索引，无论数据是否排序，我们都可以使代码变得同样快。我们的代码将始终添加一个值，但是当决策位为0时，我们会将值添加到我们不在乎的位置。这是代码：
//测试
clock_t start = clock（）;
long long a [] = {0，0};
长久的总和
对于（无符号i = 0; i <100000; ++ i）
{
//主循环
for（无符号c = 0; c > 7）;
a [j] + = data [c];
}
}
double elapsedTime = static_cast （clock（）-start）/ CLOCKS_PER_SEC;
sum = a [1];
该代码浪费了添加的一半，但从未发生分支预测失败。对于随机数据，它比带有实际if语句的版本要快得多。
但是在我的测试中，显式查找表的速度比此表稍快，这可能是因为索引到查找表的速度比移位略快。这显示了我的代码如何设置和使用查找表（在代码中，“ LookUp Table”意为“ lut”）。这是C ++代码：
//声明然后填写查询表
int lut [256];
for（无符号c = 0; c <256; ++ c）
lut [c] =（c> = 128）？ c：0；
//构建后使用查找表
对于（无符号i = 0; i <100000; ++ i）
{
//主循环
for（无符号c = 0; c 值）
node = node-> pLeft;
其他
node = node-> pRight;
该库将执行以下操作：
i =（x <节点->值）;
node = node-> link [i];
这是此代码的链接：永远困惑的红黑树
|
在排序的情况下，您可以比依靠成功的分支预测或任何无分支比较技巧来做的更好：完全删除分支。
确实，该数组在数据<128和数据> = 128的连续区域中进行分区。因此，您应该使用二分搜索（使用Lg（arraySize）= 15比较）找到分区点，然后从中进行直接累加那一点。
类似于（未选中）的内容
int i = 0，j，k = arraySize;
而（i > 1;
如果（数据[j]> = 128）
k = j;
其他
i = j;
}
总和= 0;
为（;我> 1;
对于（i = 0，k = arraySize; i  = 128？k：i）= j）
j =（i + k）>> 1;
对于（sum = 0; i  = 128）
/ \
/ \
/ \
真假
/ \
/ \
/ \
/ \
B）和+ = data [c]; C）用于循环或print（）。
如果没有分支预测，则会发生以下情况：
要执行指令B或指令C，处理器将必须等到指令A到达流水线中的EX阶段为止，因为转到指令B或指令C的决定取决于指令A的结果。因此，管线看起来像这样
如果条件返回true：
如果条件返回false：
等待指令A的结果的结果是，在上述情况下（无分支预测；对于true和false而言）花费的总CPU周期为7。
那么什么是分支预测？
分支预测器将尝试猜测在确定之前知道分支（if-then-else结构）的方向。它不会等待指令A到达流水线的EX阶段，但会猜测该决定并转到该指令（在本例中为B或C）。
在正确猜测的情况下，管道如下所示：
如果以后检测到猜测是错误的，则将部分执行的指令丢弃，流水线将从正确的分支重新开始，从而导致延迟。
在分支预测错误的情况下所浪费的时间等于从获取阶段到执行阶段的流水线中的阶段数。现代微处理器往往具有很长的流水线，因此误预测延迟在10到20个时钟周期之间。流水线越长，对好的分支预测器的需求就越大。
在OP的代码中，有条件的第一次，分支预测变量没有任何信息可作为预测的基础，因此，第一次它将随机选择下一条指令。稍后在for循环中，它可以根据历史记录进行预测。
对于按升序排序的数组，存在三种可能性：
所有元素均小于128
所有元素都大于128
一些开始的新元素小于128，后来又大于128
让我们假设预测变量在首次运行时将始终假设为真实分支。
因此，在第一种情况下，它将始终是真实的因为历史上所有预测都是正确的
在第二种情况下，最初它会预测错误，但是经过几次迭代后，它将正确预测。
在第3种情况下，它将最初正确地进行预测，直到元素少于128个。此后，它将失败一段时间并在历史中看到分支预测失败时进行校正。
在所有这些情况下，失败的次数将太少，因此，仅需几次就可以丢弃部分执行的指令并从正确的分支重新开始，从而减少了CPU周期。
但是，如果是随机未排序的数组，则预测将需要丢弃部分执行的指令，并在大部分时间中从正确的分支重新开始，与排序后的数组相比，将导致更多的CPU周期。
|
官方答案将来自
英特尔-避免分支错误的成本
英特尔-分支和循环重组可防止错误预测
科学论文-分支预测计算机体系结构
书籍：J.L。Hennessy，D.A. Patterson：计算机体系结构：定量方法
科学出版物中的文章：是的Patt在分支预测中做了很多。
您还可以从这张可爱的图表中看到分支预测变量为何会感到困惑。
原始代码中的每个元素都是一个随机值
data [c] = std :: rand（）％256;
因此，随着std :: rand（）的打击，预测变量将改变方向。
另一方面，一旦将其排序，预测变量将首先进入强烈不采用的状态，并且当值更改为高值时，预测变量将在三个过程中从强烈不采用变为强烈采取。
|
在同一行中（我认为这没有得到任何答案的强调），值得一提的是，有时（尤其是在性能至关重要的软件中，例如在Linux内核中），您会找到一些if语句，如下所示：
如果（可能是（everything_is_ok））
{
/* 做一点事 */
}
或类似的：
如果（不太可能（very_improbable_condition））
{
/* 做一点事 */
}
实际上，approximate（）和appliant（）都是通过使用类似GCC的__builtin_expect的定义的宏，以帮助编译器插入预测代码以考虑到用户提供的信息来满足条件。 GCC支持其他可能会更改正在运行的程序的行为或发出底层指令（例如清除缓存等）的内置插件。请参阅此文档，其中提供了可用的GCC内置插件。
通常，这种优化主要在执行时间很重要的硬实时应用程序或嵌入式系统中找到。例如，如果您要检查仅发生1/10000000次的某些错误情况，那么为什么不通知编译器呢？这样，默认情况下，分支预测将假定条件为假。
|
C ++中经常使用的布尔运算会在编译程序中产生许多分支。如果这些分支位于循环内并且难以预测，则它们可能会大大降低执行速度。布尔变量存储为8位整数，false值为0，true值为1。
在所有意义上都将布尔变量用作输入的运算符会检查输入是否具有除0或1以外的任何其他值，但将布尔值作为输出的运算符不能产生除0或1之外的其他值，因此布尔变量被过分确定。布尔变量作为输入的效率低于必要的效率。
考虑示例：
布尔a，b，c，d;
c = a && b;
d = a || b;
这通常由编译器通过以下方式实现：
布尔a，b，c，d;
如果（a！= 0）{
如果（b！= 0）{
c = 1；
}
其他{
转到CFALSE;
}
}
其他{
CFALSE：
c = 0;
}
如果（a == 0）{
如果（b == 0）{
d = 0;
}
其他{
转到DTRUE;
}
}
其他{
DTRUE：
d = 1；
}
此代码远非最佳。万一发生预测错误，分支机构可能会花费很长时间。如果可以肯定地知道操作数除了0和1之外没有其他值，则可以使布尔运算的效率更高。编译器没有做出这种假设的原因是，如果变量未初始化，则它们可能具有其他值。或来自未知来源。如果a和b已初始化为有效值，或者它们来自产生布尔输出的运算符，则可以优化上述代码。优化的代码如下所示：
char a = 0，b = 1，c，d；
c = a＆b;
d = a | b;
使用char代替bool可以使用按位运算符（＆和|）代替布尔运算符（&&和||）。按位运算符是仅占用一个时钟周期的单个指令。即使a和b的值不为0或1，OR运算符（|）也可以工作。如果操作数的值不为0和1，则AND运算符（＆）和EXCLUSIVE OR运算符（^）的结果可能不一致。
〜不能用于NOT。代替，您可以通过将XOR与1进行异或运算，对已知为0或1的变量进行布尔NOT运算：
布尔a，b;
b =！a;
可以优化为：
字符a = 0，b;
b = a ^ 1;
如果b是在a为假时不应该求值的表达式（&&将不求b，＆will），则a && b不能用a＆b替换。同样，|| b不能替换为|如果b是一个表达式，则如果a为true，则不应该对其求值。
如果操作数是变量，则使用按位运算符要比比较操作数更有利：
布尔x，y，z的两倍；
a = x> y && z <5.0;
在大多数情况下是最佳选择（除非您期望&&表达式会产生许多分支错误预测）。
|
这是肯定的！...
由于代码中发生的切换，分支预测使逻辑运行速度变慢！就像您要走在一条直街或拐弯很多的街道上一样，请确保直路会更快！
如果对数组进行了排序，则第一步的条件为false：data [c]> = 128，然后在到达街道尽头的整个过程中为真值。这样便可以更快地到达逻辑结尾。另一方面，使用未排序的数组，您需要进行大量的翻转和处理，这肯定会使您的代码运行缓慢。
在下面查看我为您创建的图像。哪条街的建成速度会更快？
因此，以编程方式，分支预测会使流程变慢。
同样在最后，很高兴知道我们有两种分支预测，每种预测都会以不同的方式影响您的代码：
1.静态的
2.动态
微处理器首次使用静态分支预测
遇到条件分支，而动态分支预测是
用于条件分支代码的成功执行。
为了有效地编写您的代码以利用这些优势
规则，在编写if-else或switch语句时，请检查最多
常见的情况首先出现，然后逐步减少到最不常见的情况。
循环不一定需要任何特殊的代码顺序
静态分支预测，仅作为循环迭代器的条件
通常使用。
|
这个问题已经被回答了好多次了。我仍然想提请小组注意另一种有趣的分析。
最近，该示例（进行了很小的修改）还用作演示如何在Windows上的程序本身中分析一段代码的方式。在此过程中，作者还展示了如何使用结果来确定代码在排序和未排序情况下大部分时间都花在了哪里。最后，这篇文章还展示了如何使用HAL（硬件抽象层）的一个鲜为人知的功能来确定在未排序的情况下发生了多少分支错误预测。
链接在这里：
自我分析演示
|
正如其他人已经提到的那样，神秘的背后是分支预测器。
我不是要添加任何内容，而是以另一种方式解释该概念。
Wiki上有一个简短的介绍，其中包含文本和图表。
我喜欢下面的解释，该解释使用图表直观地阐述Branch Predictor。
在计算机体系结构中，分支预测变量是
试图猜测分支方式的数字电路（例如
if-then-else结构）将在确定之前就消失了。的
分支预测变量的目的是改善
指令流水线。分支预测变量在
在许多现代管道中实现高效的性能
微处理器体系结构，例如x86。
双向分支通常通过条件跳转来实现
指令。有条件的跳转可以“不采取”并继续
用紧随其后的代码的第一分支执行
有条件的跳转之后，或者可以“获取”并跳转到
程序存储器中代码第二个分支所在的不同位置
存储。不确定是否会发生条件跳转
直到计算出条件并且
条件跳转已通过指令的执行阶段
管道（见图1）。
基于所描述的场景，我编写了一个动画演示来展示如何在不同情况下在管道中执行指令。
没有分支预测器。
如果没有分支预测，则处理器将不得不等到
条件跳转指令在执行之前已经通过了执行阶段
下一条指令可以进入流水线中的获取阶段。
该示例包含三个指令，第一个是条件跳转指令。后两条指令可以进入管道，直到执行条件跳转指令为止。
3条指令需要9个时钟周期才能完成。
使用Branch Predictor，不要进行条件跳转。假设预测没有采用有条件的跳跃。
3条指令需要7个时钟周期才能完成。
使用Branch Predictor并进行条件跳转。让我们假设预测没有采取条件转移。
3条指令需要9个时钟周期才能完成。
在分支预测错误的情况下浪费的时间等于
从获取阶段到执行阶段的管道中的阶段数
执行阶段。现代微处理器往往具有相当长的时间
流水线，以使错误预测延迟在10到20个时钟之间
周期。结果，延长管道的长度增加了对管道的需求。
更高级的分支预测器。
如您所见，似乎我们没有理由不使用Branch Predictor。
这是一个非常简单的演示，阐明了Branch Predictor的最基本部分。如果这些gif令人讨厌，请随时将其从答案中删除，访问者还可以从BranchPredictorDemo获取实时演示源代码。
|
分支预测收益！
重要的是要了解分支预测错误不会降低程序速度。错过预测的代价就像不存在分支预测一样，您等待表达式的评估来决定要运行的代码（下一段中的进一步说明）。
如果（表达式）
{
//运行1
}其他{
//运行2
}
只要有if-else \ switch语句，就必须对表达式求值以确定应该执行哪个块。在编译器生成的汇编代码中，插入了条件分支指令。
分支指令会导致计算机开始执行不同的指令序列，从而偏离计算机根据顺序执行指令的默认行为（即，如果表达式为假，则程序将跳过if块的代码），具体取决于某些条件。是本例中的表达评估。
就是说，编译器会在实际评估结果之前尝试预测结果。它将从if块中获取指令，如果该表达式为真，那就太好了！我们获得了评估它所花费的时间，并在代码中取得了进步。如果不是，那么我们运行的是错误的代码，将刷新管道，并运行正确的块。
可视化：
假设您需要选择路线1或路线2，等待您的伴侣检查地图，您已经停在##并等待，或者您可以选择路线1，如果幸运的话（路线1是正确的路线），那就太好了，您不必等待伙伴检查地图（您节省了他检查地图所需的时间），否则您只需回头即可。
尽管冲洗管道非常快，但如今采取这种赌博是值得的。预测排序的数据或变化缓慢的数据总是比预测快速变化更容易和更好。
O路线1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
路线2 \ --------------------------------
|
在ARM上，不需要分支，因为每个指令都有一个4位的条件字段，该字段将以零成本测试（可能为零）处理器状态寄存器中可能出现的16种不同条件中的任何一种，以及指令中的条件是否为否，指令将被跳过。这消除了对短分支的需求，并且该算法不会对分支预测产生任何影响。因此，由于排序的额外开销，此算法的排序版本在ARM上的运行速度将比未排序版本慢。
该算法的内部循环在ARM汇编语言中看起来类似于以下内容：
MOV R0，＃0 // R0 =总和= 0
MOV R1，＃0 // R1 = c = 0
ADR R2，数据// R2 =数据数组的地址（将此指令置于外循环之外）
.inner_loop //内部循环分支标签
LDRB R3，[R2，R1] // R3 =数据[c]
CMP R3，＃128 //比较R3与128
添加R0，R0，R3 //如果R3> = 128，则求和+ = data [c]-无需分支！
添加R1，R1，＃1 // c ++
CMP R1，#arraySize //将c与arraySize比较
BLT inner_loop //如果c （））;
for（无符号c = 0; c  = 128
sum = sum + data1（j）;
结束
结束
结束
托克
ExeTimeWithSorting = toc-tic;
上面的MATLAB代码的结果如下：
a：经过时间（无排序）= 3479.880861秒。
b：经过的时间（带有排序）= 2377.873098秒。
我得到的@GManNickG中的C代码的结果是：
a：经过时间（无排序）= 19.8761秒。
b：经过时间（排序）= 7.37778秒。
基于此，MATLAB看上去比不进行排序的C实现慢了175倍，而进行排序却慢了350倍。换句话说，对于MATLAB实现，效果（分支预测）为1.46x，对于C实现，效果为2.7x。
|
其他答案认为需要对数据进行排序的假设是不正确的。
以下代码不会对整个数组进行排序，而是仅对数组的200个元素进行排序，因此运行速度最快。
仅对k个元素部分进行排序即可完成线性时间O（n）的预处理，而不是对整个数组进行排序所需的O（n.log（n））时间。
#include <算法>
#include 
#include 
int main（）{
int数据[32768]; const int l =数据大小/数据大小[0];
for（无符号c = 0; c  = 128）
sum + = data [c];
}
}
std :: cout << static_cast （clock（）-start）/ CLOCKS_PER_SEC << std :: endl;
std :: cout <<“ sum =” <<总和<< std :: endl;
}
这也“证明”它与诸如排序顺序之类的任何算法问题均无关，并且确实是分支预测。
|
Bjarne Stroustrup对这个问题的回答：
这听起来像一个面试问题。是真的吗你怎么知道的？不先进行一些测量就回答有关效率的问题是一个坏主意，因此了解如何进行测量很重要。
因此，我尝试使用一百万个整数的向量，得到：
已排序32995毫秒
随机播放125944毫秒
已排序18610毫秒
随机播放133304毫秒
已排序17942毫秒
随机播放107858毫秒
我跑了几次，以确保。是的，这种现象是真实的。我的关键代码是：
无效运行（vector ＆v，const string＆label）
{
自动t0 = system_clock :: now（）;
sort（v.begin（），v.end（））;
自动t1 = system_clock :: now（）;
cout <<标签
<< duration_cast <微秒>（t1 — t0）.count（）
<<“毫秒\ n”;
}
无效的tst（）
{
vector  v（1'000'000）;
iota（v.begin（），v.end（），0）;
运行（v，“已排序”）；
std :: shuffle（v.begin（），v.end（），std :: mt19937 {std :: random_device {}（）}）;
运行（v，“洗牌”）;
}
对于这种编译器，标准库和优化器设置，至少这种现象是真实的。不同的实现可以而且确实给出不同的答案。实际上，有人确实做了更系统的研究（可以通过快速的网络搜索找到它），并且大多数实现都显示出这种效果。
原因之一是分支预测：排序算法中的关键操作是“ if（v [i] <枢轴]）…”或等效操作。对于排序的序列，测试始终为真，而对于随机序列，选择的分支随机变化。
另一个原因是，当向量已经排序时，我们不需要将元素移到正确的位置。这些小细节的影响是我们看到的五或六倍。
快速排序（通常是排序）是一项复杂的研究，吸引了计算机科学的一些最伟大的头脑。良好的排序功能是选择良好算法并在实现过程中注意硬件性能的结果。
如果要编写高效的代码，则需要了解一些有关计算机体系结构的知识。
|
此问题源于CPU上的分支预测模型。我建议阅读这篇文章：
通过多个分支预测和分支地址缓存提高指令提取速率
对元素进行排序后，IR不会一次又一次地获取所有CPU指令，而是从缓存中获取它们。
|
避免分支预测错误的一种方法是建立查找表，并使用数据对其进行索引。 Stefan de Bruijn在回答中对此进行了讨论。
但是在这种情况下，我们知道值在[0，255]范围内，我们只关心值> =128。这意味着我们可以轻松地提取单个位来告诉我们是否需要一个值：数据右边的7位，剩下的是0位或1位，我们只想在有1位的情况下将值相加。我们将此位称为“决策位”。
通过将决策位的0/1值用作数组的索引，无论数据是否排序，我们都可以使代码变得同样快。我们的代码将始终添加一个值，但是当决策位为0时，我们会将值添加到我们不在乎的位置。这是代码：
//测试
clock_t start = clock（）;
long long a [] = {0，0};
长久的总和
对于（无符号i = 0; i <100000; ++ i）
{
//主循环
for（无符号c = 0; c > 7）;
a [j] + = data [c];
}
}
double elapsedTime = static_cast （clock（）-start）/ CLOCKS_PER_SEC;
sum = a [1];
该代码浪费了添加的一半，但从未发生分支预测失败。对于随机数据，它比带有实际if语句的版本要快得多。
但是在我的测试中，显式查找表的速度比此表稍快，这可能是因为索引到查找表的速度比移位略快。这显示了我的代码如何设置和使用查找表（在代码中，“ LookUp Table”意为“ lut”）。这是C ++代码：
//声明然后填写查询表
int lut [256];
for（无符号c = 0; c <256; ++ c）
lut [c] =（c> = 128）？ c：0；
//构建后使用查找表
对于（无符号i = 0; i <100000; ++ i）
{
//主循环
for（无符号c = 0; c 值）
node = node-> pLeft;
其他
node = node-> pRight;
该库将执行以下操作：
i =（x <节点->值）;
node = node-> link [i];
这是一个不错的解决方案，也许会奏效。
|
高度活跃的问题。赢得10个声誉才能回答这个问题。信誉要求有助于保护该问题免受垃圾邮件和非答复活动的侵害。
不是您要找的答案？浏览标记为Java c ++性能优化分支预测的其他问题，或者提出您自己的问题。