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

分支预测。

对于排序数组，条件首先是一连串的值，然后成为所有后续值的条件。这很容易预测。对于未排序的数组，您需要支付分支成本。data[c] >= 128falsetrue

您是分支预测失败的受害者。

---

什么是分支预测？

考虑一个铁路枢纽：

_{图片由 Mecanismo 提供，来自 Wikimedia Commons。在 CC-By-SA 3.0 许可下使用。}

现在为了论证，假设这是在 1800 年代——在长途或无线电通信之前。

你是一个路口的盲人操作员，你听到火车来了。你不知道它应该走哪条路。你停下火车，问司机他们想要哪个方向。然后适当地设置开关。

火车很重，惯性很大，所以它们需要很长时间才能启动和减速。

有没有更好的方法？你猜火车会往哪个方向开！

• 如果你猜对了，它就会继续。
• 如果你猜错了，司机会停下来，倒车，对你大喊大叫，让你拨动开关。然后，它可以沿着另一条路径重新启动。

如果你每次都猜对了，火车就永远不必停下来了。
如果你经常猜错，火车会花费大量时间停止、倒车和重新启动。

---

考虑一个 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, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T  ...

       = TTNTTTTNTNNTTT ...   (completely random - impossible to predict)

---

可以做些什么？

如果编译器无法将分支优化为有条件的移动，如果您愿意牺牲可读性来换取性能，则可以尝试一些技巧。

取代：

if (data[c] >= 128)
    sum += data[c];

跟：

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

这将消除分支，并将其替换为一些按位操作。

_{（请注意，这个 hack 并不完全等同于原始的 if 语句。但在这种情况下，它对 data[] 的所有输入值都有效。}

基准测试： Core i7 920 @ 3.5 GHz

C++ - Visual Studio 2010 - x64 版本

Java - NetBeans 7.1.1 JDK 7 - x64

观察：

• 与分支：排序和未排序的数据之间存在巨大差异。
• 使用 Hack：排序数据和未排序数据之间没有区别。
• 在 C++ 的情况下，hack 实际上比对数据进行排序时的分支慢一点。

一般的经验法则是避免在关键循环中出现依赖于数据的分支（如本例中所示）。

---

更新：

• 带有或在 x64 上的 GCC 4.6.1 能够生成条件移动，因此排序和未排序的数据之间没有区别 - 两者都很快。-O3-ftree-vectorize

  （或者有点快：对于已经排序的情况，可能会更慢，特别是如果 GCC 将其放在关键路径上而不仅仅是，尤其是在 Broadwell 之前的 Intel 上，其中有 2 个周期的延迟：gcc 优化标志 -O3 使代码比 -O2 慢cmovaddcmov)

• VC++ 2010 即使在 下也无法为此分支生成条件移动。/Ox

• 英特尔 C++ 编译器 （ICC） 11 创造了奇迹。它交换两个环路，从而将不可预测的分支提升到外环路。它不仅不受错误预测的影响，而且速度是 VC++ 和 GCC 可以生成的任何产品的两倍！换句话说，ICC利用测试循环击败了基准测试......

• 如果您为英特尔编译器提供无分支代码，它就会直接将其矢量化......并且与分支（使用环形交换）一样快。

这表明，即使是成熟的现代编译器，在优化代码的能力方面也会有很大差异......

当数据排序时，性能会大幅提高的原因是消除了分支预测惩罚，正如 Mysticial 的回答中所解释的那样。

现在，如果我们看一下代码

if (data[c] >= 128)
    sum += data[c];

我们可以发现，这个特定分支的含义是在满足条件时添加一些东西。这种类型的分支可以很容易地转换为条件移动语句，该语句将被编译为系统中的条件移动指令： 。删除了分支，从而删除了潜在的分支预测惩罚。if... else...cmovlx86

因此，将直接编译（不进行任何优化）到 中的条件移动指令的语句是三元运算符。因此，我们将上述语句重写为等效语句：CC++x86... ? ... : ...

sum += data[c] >=128 ? data[c] : 0;

在保持可读性的同时，我们可以检查加速系数。

在 Intel Core i7-2600K @ 3.4 GHz 和 Visual Studio 2010 发布模式下，基准测试为：

x86的

64 倍

结果在多项测试中是稳健的。当分支结果不可预测时，我们会得到很大的加速，但当它是可预测的时，我们会受到一些影响。事实上，当使用条件移动时，无论数据模式如何，性能都是相同的。

现在，让我们通过调查它们生成的程序集来更仔细地了解一下。为简单起见，我们使用两个函数和 .x86max1max2

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由于使用了指令，使用的代码要少得多。但真正的收益是不涉及分支跳跃，如果预测结果不正确，这将对性能造成重大影响。cmovgemax2jmp

那么，为什么有条件移动效果更好呢？

在典型的处理器中，指令的执行分为几个阶段。粗略地说，我们有不同的硬件来处理不同的阶段。因此，我们不必等待一条指令完成即可开始一条新指令。这称为流水线。x86

在分支情况下，下面的指令是由前面的指令决定的，因此我们不能进行流水线。我们要么等待，要么预测。

在条件移动的情况下，条件移动指令的执行分为几个阶段，但早期阶段类似和不依赖于前一个指令的结果;只有后期阶段需要结果。因此，我们等待一条指令执行时间的一小部分。这就是为什么当预测容易时，条件移动版本比分支慢的原因。FetchDecode

《Computer Systems： A Programmer's Perspective》一书第二版对此进行了详细解释。您可以查看第 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];
    }
}

然后，你可以看到条件在整个循环执行过程中是恒定的，所以你可以提升 out：ifiif

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 工具具有分支预测变量模拟器，通过使用标志启用。在本问题中的示例上运行它，将外部循环的数量减少到 10000 个，并使用 编译，得到以下结果：cachegrind--branch-sim=yesg++

排序：

==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];
           .           .  .   .          }
           .           .  .   .      }

这使您可以轻松识别有问题的行 - 在未排序的版本中，在 cachegrind 的分支预测器模型下，该行导致了 164,050,007 个错误预测的条件分支 （），而在排序版本中它只导致了 10,006 个。if (data[c] >= 128)Bcm

---

或者，在 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)
...

有关详细信息，请参阅性能教程。

我在 MacBook Pro（Intel i7,64 位，2.4 GHz）上使用 MATLAB 2011b 尝试了相同的代码，用于以下 MATLAB 代码：

% Processing time with Sorted data vs unsorted data
%==========================================================================
% Generate data
arraySize = 32768
sum = 0;
% Generate random integer data from range 0 to 255
data = randi(256, arraySize, 1);


%Sort the data
data1= sort(data); % data1= data  when no sorting done


%Start a stopwatch timer to measure the execution time
tic;

for i=1:100000

    for j=1:arraySize

        if data1(j)>=128
            sum=sum + data1(j);
        end
    end
end

toc;

ExeTimeWithSorting = toc - tic;

上述MATLAB代码的结果如下：

  a: Elapsed time (without sorting) = 3479.880861 seconds.
  b: Elapsed time (with sorting ) = 2377.873098 seconds.

C 代码的结果，如@GManNickG所示，我得到：

  a: Elapsed time (without sorting) = 19.8761 sec.
  b: Elapsed time (with sorting ) = 7.37778 sec.

基于此，看起来 MATLAB 比不进行排序的 C 实现慢了近 175 倍，在进行排序时慢了 350 倍。换言之，MATLAB实现的效果（分支预测）为1.46倍，C实现为2.7倍。

由于数组排序时数据分布在 0 到 255 之间，因此大约前半部分的迭代不会输入 -语句（该语句在下面共享）。ifif

if (data[c] >= 128)
    sum += data[c];

问题是：是什么让上述语句在某些情况下不执行，例如在排序数据的情况下？“分支预测器”来了。分支预测器是一种数字电路，它试图猜测分支（例如结构）在确定之前将走向哪个方向。分支预测器的目的是改善指令管道中的流程。分支预测器在实现高效性能方面发挥着关键作用！if-then-else

让我们做一些基准标记来更好地理解它

-语句的性能取决于其条件是否具有可预测的模式。如果条件始终为 true 或始终为 false，则处理器中的分支预测逻辑将拾取该模式。另一方面，如果模式是不可预测的，则 -statement 的成本会高得多。ifif

让我们在不同条件下测量此循环的性能：

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

以下是具有不同真假模式的循环时序：

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

一个“坏”的真假模式可以使一个-语句比一个“好”的模式慢六倍！当然，哪种模式是好的，哪种模式是坏的，取决于编译器生成的确切指令和特定的处理器。if

因此，分支预测对性能的影响是毋庸置疑的！

我刚刚阅读了这个问题及其答案，我觉得缺少一个答案。

我发现在托管语言中效果特别好的消除分支预测的一种常见方法是表查找，而不是使用分支（尽管在本例中我没有测试过它）。

在以下情况下，此方法通常有效：

1. 它是一个小表，很可能缓存在处理器中，并且
2. 您正在一个非常紧密的循环中运行事物和/或处理器可以预加载数据。

背景和原因

从处理器的角度来看，您的内存很慢。为了补偿速度上的差异，处理器中内置了几个缓存（L1/L2 缓存）。所以想象一下，你正在做你的很好的计算，并弄清楚你需要一块内存。处理器将获得其“加载”操作，并将内存加载到缓存中，然后使用缓存进行其余的计算。由于内存相对较慢，因此此“负载”会减慢程序速度。

与分支预测一样，这在奔腾处理器中得到了优化：处理器预测它需要加载一段数据，并尝试在操作实际到达缓存之前将其加载到缓存中。正如我们已经看到的，分支预测有时会出错——在最坏的情况下，你需要回去等待内存加载，这将花费很长时间（换句话说：分支预测失败是不好的，分支预测失败后的内存负载是可怕的！

对我们来说幸运的是，如果内存访问模式是可预测的，处理器会将其加载到其快速缓存中，一切正常。

我们首先需要知道的是什么是小的？虽然通常越小越好，但经验法则是坚持使用大小为 <= 4096 字节的查找表。作为上限：如果您的查找表大于 64K，则可能值得重新考虑。

构造表

因此，我们发现可以创建一个小表。接下来要做的是获取查找功能。查找函数通常是使用几个基本整数运算（and、or、xor、shift、add、remove 和 multiply）的小函数。您希望通过查找函数将输入转换为表中的某种“唯一键”，然后简单地为您提供您希望它执行的所有工作的答案。

在这种情况下：>= 128 表示我们可以保留该值，< 128 表示我们删除它。最简单的方法是使用“AND”：如果我们保留它，我们用 7FFFFFFF 和它;如果我们想摆脱它，我们用 0 和它。还要注意的是，128 是 2 的幂——所以我们可以继续制作一个 32768/128 整数的表，并用一个 0 和大量 7FFFFFFFF 填充它。

托管语言

您可能想知道为什么这在托管语言中效果很好。毕竟，托管语言会用分支检查数组的边界，以确保你不会搞砸......

嗯，不完全是...... ：-）

在消除托管语言的这个分支方面，已经做了相当多的工作。例如：

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

在这种情况下，编译器显然永远不会命中边界条件。至少Microsoft JIT编译器（但我希望Java会做类似的事情）会注意到这一点并完全删除检查。哇，这意味着没有分支。同样，它将处理其他明显的情况。

如果您在使用托管语言进行查找时遇到麻烦（关键是将 a 添加到查找函数以使边界检查可预测）并观察它的速度。& 0x[something]FFF

本案结果

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();

避免分支预测错误的一种方法是构建查找表，并使用数据对其进行索引。Stefan de Bruijn在他的回答中讨论了这一点。

但在这种情况下，我们知道值在 [0， 255] 范围内，我们只关心值 >= 128。这意味着我们可以很容易地提取一个位，告诉我们是否想要一个值：通过将数据移动到右边的 7 位，我们只剩下 0 位或 1 位，我们只想在有 1 位时添加值。我们称此位为“决策位”。

通过使用决策位的 0/1 值作为数组的索引，我们可以制作出无论数据排序与否排序都同样快的代码。我们的代码总是会添加一个值，但是当决策位为 0 时，我们会将值添加到我们不关心的地方。代码如下：

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

此代码浪费了一半的添加，但从未出现分支预测失败。在随机数据上，它比使用实际 if 语句的版本要快得多。

但在我的测试中，显式查找表的速度比这略快，可能是因为索引到查找表中比位移略快。这显示了我的代码如何设置和使用查找表（在代码中毫无想象力地称为“查找表”）。下面是 C++ 代码：lut

// Declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// Use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

在本例中，查找表只有 256 个字节，因此它非常适合缓存，而且速度很快。如果数据是 24 位值，而我们只想要其中的一半，那么这种技术将无法很好地工作......查找表太大而不实用。另一方面，我们可以结合上面显示的两种技术：首先移动位，然后索引查找表。对于我们只想要上半部分值的 24 位值，我们可能会将数据向右移动 12 位，并为表索引留下 12 位值。12 位表索引意味着一个包含 4096 个值的表，这可能很实用。

索引到数组中的技术（而不是使用语句）可用于决定使用哪个指针。我看到一个实现了二叉树的库，它没有两个命名指针（和/或其他），而是有一个长度为 2 的指针数组，并使用“决策位”技术来决定遵循哪一个。例如，而不是：ifpLeftpRight

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

这个库会做类似的事情：

i = (x < node->value);
node = node->link[i];

这是此代码的链接：红黑树，永远混淆

在排序的情况下，你可以比依赖成功的分支预测或任何无分支的比较技巧做得更好：完全删除分支。

实际上，该数组被划分在一个连续的区域中，另一个区域与 .因此，您应该通过二分法搜索（使用比较）找到分区点，然后从该点进行直接累积。data < 128data >= 128Lg(arraySize) = 15

类似（未选中）

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

或者，稍微模糊一点

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

一种更快的方法，为有序或未有序的都给出近似解：（假设真正均匀分布，16384 个样本，期望值为 191.5） ：-）sum= 3137536;

上述行为的发生是由于 Branch 预测。

要理解分支预测，必须首先了解指令流水线。

运行指令的步骤可以与运行上一条和下一条指令的步骤顺序重叠，以便可以并行执行不同的步骤。这种技术被称为指令流水线，用于提高现代处理器的吞吐量。为了更好地理解这一点，请参阅维基百科上的这个例子。

通常，现代处理器具有相当长（和宽）的管道，因此可以进行许多指令。了解现代微处理器 90分钟指南！它从介绍基本的有序流水线开始，然后从那里开始。

但为了方便起见，让我们考虑一个简单的有序管道，仅包含这 4 个步骤。
（类似于经典的 5 级 RISC，但省略了单独的 MEM 级。

1. IF -- 从内存中获取指令
2. ID -- 解码指令
3. EX -- 执行指令
4. WB -- 写回 CPU 寄存器

4 级流水线一般为 2 条指令。

回到上面的问题，让我们考虑以下说明：

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

如果没有分支预测，将发生以下情况：

为了执行指令 B 或指令 C，处理器必须等待（停止）直到指令 A 离开管道中的 EX 阶段，因为转到指令 B 或指令 C 的决定取决于指令 A 的结果（即从下一个获取的位置）。因此，管道将如下所示：

无预测：当条件为真时：

无预测：当 if 条件为 false 时：

由于等待指令 A 的结果，在上述情况下（无分支预测;对于 true 和 false）所花费的总 CPU 周期数为 7。

那么什么是分支预测呢？

分支预测器将尝试猜测分支（if-then-else 结构）将走向哪个方向，然后才能确定这一点。它不会等待指令 A 到达管道的 EX 阶段，但它会猜测决策并转到该指令（在我们的示例中为 B 或 C）。

如果猜测正确，管道如下所示：

如果后来检测到猜测错误，则部分执行的指令将被丢弃，管道将从正确的分支重新开始，从而导致延迟。 在分支错误预测的情况下浪费的时间等于管道中从提取阶段到执行阶段的阶段数。现代微处理器往往具有相当长的流水线，因此误预测延迟在 10 到 20 个时钟周期之间。管道越长，对良好分支预测器的需求就越大。

在 OP 的代码中，第一次有条件时，分支预测器没有任何信息可以作为预测的基础，所以第一次它会随机选择下一条指令。（或者回退到静态预测，通常是向前不采取，向后采取）。稍后在 for 循环中，它可以基于历史记录进行预测。 对于按升序排序的数组，有三种可能性：

1. 所有元素均小于 128 个
2. 所有元素都大于 128
3. 一些起始新元素小于 128，后来变得大于 128

让我们假设预测器在第一次运行时将始终假设真正的分支。

因此，在第一种情况下，它将始终采用真正的分支，因为从历史上看，它的所有预测都是正确的。 在第二种情况下，最初它会预测错误，但经过几次迭代后，它会正确预测。 在第 3 种情况下，它最初会正确预测，直到元素小于 128。之后，它将失败一段时间，并在历史上看到分支预测失败时自行纠正。

在所有这些情况下，故障的数量都会太少，因此，只有几次需要丢弃部分执行的指令并使用正确的分支重新开始，从而减少 CPU 周期。

但是，对于随机未排序的数组，预测将需要丢弃部分执行的指令，并在大多数时间从正确的分支重新开始，与排序数组相比，会导致更多的 CPU 周期。

---

延伸阅读：

• 现代微处理器 90分钟指南！
• Dan Luu 关于分支预测的文章（涵盖较旧的分支预测器，而不是现代的 IT-TAGE 或 Perceptron）
• https://en.wikipedia.org/wiki/Branch_predictor
• 分支预测和解释器的性能 - Don't Trust Folklore - 2015 年的论文展示了英特尔的 Haswell 在预测 Python 解释器主循环的间接分支方面做得有多好（由于非简单模式，历史上存在问题），与早期不使用 IT-TAGE 的 CPU 相比.（不过，它们对这种完全随机的情况没有帮助。当源代码编译为分支 asm 时，Skylake CPU 上循环内的 if 仍有 50% 的误报率。
• 较新的 Intel 处理器上的静态分支预测 - CPU 在运行没有可用动态预测的分支指令时实际执行的操作。从历史上看，前向未取（如或）、后取（如循环）已被使用，因为它总比没有好。对代码进行布局，使快速路径/常见情况最小化占用的分支，有利于 I 缓存密度和静态预测，因此编译器已经这样做了。（这是 C 源代码中 / 提示的真正效果，实际上并没有暗示大多数 CPU 中的硬件分支预测，除非可能通过静态预测。ifbreaklikelyunlikely

在同一行中（我认为这没有被任何答案突出显示），值得一提的是，有时（特别是在性能很重要的软件中，例如在 Linux 内核中），您可以找到一些如下所示的 if 语句：

if (likely( everything_is_ok ))
{
    /* Do something */
}

或类似情况：

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

实际上，两者都是通过使用类似 GCC 的东西来定义的宏，以帮助编译器插入预测代码以支持条件，同时考虑用户提供的信息。GCC 支持其他内置函数，这些内置函数可以更改正在运行的程序的行为或发出低级指令，例如清除缓存等。请参阅此文档，了解可用的 GCC 的内置函数。likely()unlikely()__builtin_expect

通常，这种优化主要存在于执行时间很重要且至关重要的硬实时应用程序或嵌入式系统中。例如，如果您正在检查某些仅发生 1/10000000 次的错误情况，那么为什么不通知编译器呢？这样，默认情况下，分支预测将假定条件为 false。

C++ 中常用的布尔运算在编译的程序中生成许多分支。如果这些分支位于循环内部并且难以预测，它们可能会显著减慢执行速度。布尔变量存储为 8 位整数，值为 for 和 for。0false1true

从某种意义上说，布尔变量是过度确定的，因为所有将布尔变量作为输入的运算符都会检查输入是否具有除 或 之外的任何其他值，但将布尔值作为输出的运算符只能产生 或 以外的其他值。这使得使用布尔变量作为输入的操作效率低于必要的效率。 请看例子：0101

bool a, b, c, d;
c = a && b;
d = a || b;

这通常由编译器通过以下方式实现：

bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}

此代码远非最佳代码。如果出现错误预测，分支可能需要很长时间。如果可以肯定地知道操作数除了 和 之外没有其他值，则可以使布尔运算更加高效。编译器不做出这种假设的原因是，如果变量未初始化或来自未知源，则变量可能具有其他值。如果 并且已初始化为有效值，或者它们来自生成布尔输出的运算符，则可以优化上述代码。优化后的代码如下所示：01ab

char a = 0, b = 1, c, d;
c = a & b;
d = a | b;

char用于使用按位运算符 （ 和 ） 而不是布尔运算符 （ 和 ）。按位运算符是仅使用一个时钟周期的单条指令。OR 运算符 （） 有效，即使 和 具有除 或 以外的其他值。如果操作数具有除 和 以外的其他值，则 AND 运算符 （） 和 EXCLUSIVE OR 运算符 （） 可能会给出不一致的结果。bool&|&&|||ab01&^01

~不能用于 NOT。取而代之的是，您可以在已知的变量上创建一个布尔值 NOT，或者通过对它进行异运算：011

bool a, b;
b = !a;

可以优化为：

char a = 0, b;
b = a ^ 1;

a && b不能替换为 if 是不应计算的表达式 if is （ will not expect ， will）。同样，不能替换为 if is 是不应计算的表达式 if is 。a & bbafalse&&b&a || ba | bbatrue

如果操作数是变量，则使用按位运算符比使用操作数是比较更有利：

bool a; double x, y, z;
a = x > y && z < 5.0;

在大多数情况下是最佳的（除非您预计表达式会生成许多分支错误预测）。&&

官方答案来自

1. 英特尔 - 避免分支机构错误预测的成本
2. 英特尔 - 分支和环路重组以防止错误预测
3. 科学论文 - 分支预测计算机体系结构
4. 书籍： J.L. Hennessy， D.A. Patterson： Computer architecture： a quantitative approach
5. 科学出版物上的文章：T.Y. Yeh、Y.N. Patt 在分支预测上做了很多这样的文章。

您还可以从这张可爱的图表中看出为什么分支预测器会感到困惑。

原始代码中的每个元素都是一个随机值

data[c] = std::rand() % 256;

因此，预测器将随着打击而改变立场。std::rand()

另一方面，一旦排序，预测变量将首先进入“强烈未采取”状态，当值变为高值时，预测变量将在三次运行中从“强烈未采取”一直变化为“强烈采取”。

---

这个问题已经多次得到了很好的回答。不过，我还是想提请大家注意另一个有趣的分析。

最近，此示例（稍作修改）也被用作演示如何在 Windows 上的程序本身中分析一段代码的一种方式。在此过程中，作者还展示了如何使用结果来确定代码在排序和未排序情况下花费大部分时间的位置。最后，本文还展示了如何使用 HAL（硬件抽象层）的一个鲜为人知的功能来确定在未排序的情况下发生了多少分支错误预测。

链接在这里： 自我剖析的演示

这是肯定的...

分支预测使逻辑运行速度变慢，因为代码中发生了切换！这就像你要走一条笔直的街道或一条有很多转弯的街道，当然笔直的街道会做得更快...

如果数组已排序，则您的条件在第一步为 false：，然后成为一直到街道尽头的真值。这样你就可以更快地到达逻辑的末尾。另一方面，使用未排序的数组，您需要大量的转换和处理，这肯定会使您的代码运行速度变慢......data[c] >= 128

看看下面我为你创建的图像。哪条街会更快完工？

因此，以编程方式，分支预测会导致该过程变慢......

最后，很高兴知道我们有两种分支预测，每种预测都会以不同的方式影响您的代码：

1.静态

2.动态

另请参阅英特尔的这份文档，其中说：

微处理器首次使用静态分支预测 遇到条件分支，动态分支预测 用于条件分支代码的后续执行。

为了有效地编写代码以利用这些 规则，在编写 if-else 或 switch 语句时，检查最多 首先是常见情况，然后逐步下降到最不常见的情况。 循环不一定需要对 静态分支预测，仅作为循环迭代器的条件 是正常使用的。

分支预测收益！

重要的是要了解分支错误预测不会减慢程序速度。错过预测的代价就像分支预测不存在一样，您等待表达式的计算来决定要运行的代码（下一段将进一步解释）。

if (expression)
{
    // Run 1
} else {
    // Run 2
}

每当有 \ 语句时，都必须计算表达式以确定应该执行哪个块。在编译器生成的汇编代码中，插入了条件分支指令。if-elseswitch

分支指令可能导致计算机开始执行不同的指令序列，从而偏离其按顺序执行指令的默认行为（即，如果表达式为 false，程序将跳过块的代码），具体取决于某些条件，即我们示例中的表达式计算。if

话虽如此，编译器试图在实际评估结果之前预测结果。它将从块中获取指令，如果表达式被证明是真的，那就太好了！我们获得了评估它所花费的时间，并在代码中取得了进展;如果不是，那么我们运行了错误的代码，管道被刷新，并运行了正确的块。if

可视化：

假设您需要选择路线 1 或路线 2。等待你的伴侣检查地图，你已经停在##并等待，或者你可以选择路线1，如果你幸运的话（路线1是正确的路线），那么你不必等待你的伴侣检查地图（你节省了他检查地图的时间）， 否则你只会回头。

虽然冲洗管道的速度非常快，但现在进行这种赌博是值得的。预测排序数据或缓慢变化的数据总是比预测快速变化更容易、更好。

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------

正如其他人已经提到的，谜团的背后是分支预测器。

我不是想添加什么，而是以另一种方式解释这个概念。 wiki 上有一个简明的介绍，其中包含文本和图表。 我确实喜欢下面的解释，它使用图表直观地阐述了分支预测器。

在计算机体系结构中，分支预测器是 试图猜测分支方式的数字电路（例如 if-then-else 结构）将在确定这一点之前进行。这 分支预测器的目的是改善 指令流水线。分支预测变量在以下方面发挥着关键作用 在许多现代流水线中实现高效性能 微处理器架构，例如 x86。

双向分支通常通过条件跳转实现 指令。有条件的跳转可以“不采取”并继续 使用紧随其后的第一个代码分支执行 在条件跳转之后，或者可以“拿走”并跳转到 程序内存中代码的第二个分支所在的位置不同 数据处理。目前尚不清楚是否有条件跳跃 在计算条件和 条件跳转已通过指令中的执行阶段 管道（见图 1）。

基于所描述的场景，我编写了一个动画演示，以展示在不同情况下如何在管道中执行指令。

1. 没有分支预测器。

如果没有分支预测，处理器将不得不等到 条件跳转指令在 下一条指令可以进入管道中的 fetch 阶段。

该示例包含三条指令，第一条是条件跳转指令。后两条指令可以进入管道，直到执行条件跳转指令。

完成 3 条指令需要 9 个时钟周期。

2. 使用 Branch Predictor，不要进行条件跳转。让我们假设预测没有采取条件跳跃。

完成 7 条指令需要 3 个时钟周期。

3. 使用 Branch Predictor 并进行条件跳转。让我们假设预测没有采取条件跳跃。

完成 3 条指令需要 9 个时钟周期。

在分支错误预测的情况下浪费的时间等于 管道中从 fetch 阶段到 执行阶段。现代微处理器往往有相当长的时间 流水线，使误预测延迟在 10 到 20 时钟之间 周期。因此，使管道更长会增加对 更高级的分支预测器。

正如你所看到的，我们似乎没有理由不使用 Branch Predictor。

这是一个非常简单的演示，阐明了 Branch Predictor 的基本部分。如果这些 gif 很烦人，请随时将它们从答案中删除，访问者还可以从 BranchPredictorDemo 获取实时演示源代码

除了分支预测可能会减慢您的速度之外，排序数组还有另一个优点：

您可以有一个停止条件，而不仅仅是检查值，这样您只遍历相关数据，而忽略其余数据。 分支预测只会错过一次。

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }

排序数组的处理速度比未排序数组快，这是由于一种称为分支预测的现象。

分支预测器是一个数字电路（在计算机体系结构中），试图预测分支将走向何方，从而改善指令管道中的流程。电路/计算机预测下一步并执行它。

做出错误的预测会导致返回上一步，并使用另一个预测执行。假设预测正确，代码将继续执行下一步。错误的预测会导致重复相同的步骤，直到发生正确的预测。

你的问题的答案很简单。

在未排序的数组中，计算机会进行多次预测，从而增加出错的机会。 然而，在排序数组中，计算机做出的预测较少，从而减少了出错的机会。 做出更多预测需要更多的时间。

排序阵列：直路

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

未排序数组：弯曲的道路

______   ________
|     |__|

分支预测：猜测/预测哪条路是直的，不检查就跟着走

___________________________________________ Straight road
 |_________________________________________|Longer road

虽然两条路都到达同一个目的地，但笔直的路更短，另一条更长。如果你错误地选择了另一条路，就没有回头路了，所以如果你选择了更长的路，你会浪费一些额外的时间。这类似于计算机中发生的情况，我希望这能帮助您更好地理解。

---

另外，我想从评论中引用@Simon_Weaver：

它不会做出更少的预测 - 它做出的错误预测更少。它仍然必须通过循环预测每次......

在 ARM 上，不需要分支，因为每条指令都有一个 4 位条件字段，该字段测试处理器状态寄存器中可能出现的 16 种不同条件中的任何一种（零成本），如果指令的条件为 false，则跳过该指令。这消除了对短分支的需求，并且此算法不会有分支预测命中。因此，此算法的排序版本将比 ARM 上的未排序版本运行得慢，因为排序会产生额外的开销。

此算法的内部循环在 ARM 汇编语言中如下所示：

MOV R0, #0   // R0 = sum = 0
MOV R1, #0   // R1 = c = 0
ADR R2, data // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop  // Inner loop branch label
    LDRB R3, [R2, R1]   // R3 = data[c]
    CMP R3, #128        // compare R3 to 128
    ADDGE R0, R0, R3    // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1      // c++
    CMP R1, #arraySize  // compare c to arraySize
    BLT inner_loop      // Branch to inner_loop if c < arraySize

但这实际上是更大图景的一部分：

CMP操作码始终更新处理器状态寄存器 （PSR） 中的状态位，因为这是它们的用途，但大多数其他指令不会触及 PSR，除非您向指令添加可选后缀，指定应根据指令结果更新 PSR。就像 4 位条件后缀一样，能够在不影响 PSR 的情况下执行指令是一种机制，可以减少对 ARM 上分支的需求，并且还有助于在硬件级别进行无序调度，因为在执行一些更新状态位的操作 X 之后，随后（或并行）您可以执行一堆其他工作，这些工作明确不应影响（或受其影响）状态位， 然后，您可以测试 X 之前设置的状态位的状态。S

条件测试字段和可选的“设置状态位”字段可以组合在一起，例如：

• ADD R1, R2, R3在不更新任何状态位的情况下执行。R1 = R2 + R3
• ADDGE R1, R2, R3仅当影响状态位的先前指令导致“大于”或“等于”条件时，才执行相同的操作。
• ADDS R1, R2, R3执行加法，然后根据结果是负数、零、携带（对于无符号加法）还是 oVerflowed（对于有符号加法）更新处理器状态寄存器中的 、 和标志。NZCV
• ADDSGE R1, R2, R3仅当测试为 true 时才执行加法，然后根据加法结果更新状态位。GE

大多数处理器架构没有这种能力来指定是否应为给定操作更新状态位，这可能需要编写额外的代码来保存和以后恢复状态位，或者可能需要额外的分支，或者可能限制处理器的无序执行效率：大多数 CPU 指令集架构在大多数指令之后强行更新状态位的副作用之一是它要困难得多梳理哪些指令可以并行运行而不会相互干扰。更新状态位有副作用，因此对代码有线性化影响。对于汇编语言程序员和编译器来说，ARM 能够对任何指令进行无分支状态测试，并在任何指令后更新或不更新状态位的选项进行混合和匹配，这非常强大，并且可以生成非常高效的代码。

当不必分支时，可以避免为原本很短的分支刷新管道的时间成本，并且可以避免多种形式的推测评估的设计复杂性。许多最近发现的处理器漏洞（Spectre 等）的缓解措施的最初幼稚影响对性能的影响表明，现代处理器的性能在多大程度上取决于复杂的推测评估逻辑。由于流水线较短，分支需求大大减少，ARM 不需要像 CISC 处理器那样依赖推测性评估。（当然，高端 ARM 实现确实包括推测性评估，但这只是性能故事的一小部分。

如果你曾经想过为什么ARM会取得如此惊人的成功，那么这两种机制的出色有效性和相互作用（结合另一种机制，让你以零额外成本“桶移”任何算术运算符或偏移内存访问运算符的两个参数之一）是故事的重要组成部分。 因为它们是 ARM 架构效率的最大来源之一。早在 1983 年，ARM ISA 的原始设计师 Steve Furber 和 Roger（现在的 Sophie）Wilson 的才华怎么强调都不为过。

其他答案认为需要对数据进行排序的假设是不正确的。

下面的代码不会对整个数组进行排序，而只会对数组的 200 个元素段进行排序，因此运行速度最快。

仅对 k 元素部分进行排序会以线性时间完成预处理，而不是对整个数组进行排序所需的时间。O(n)O(n.log(n))

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

这也“证明”它与排序顺序等任何算法问题无关，确实是分支预测。

Bjarne Stroustrup 对这个问题的回答：

这听起来像是一个面试问题。是真的吗？你怎么知道？在不先进行一些测量的情况下回答有关效率的问题是一个坏主意，因此知道如何测量很重要。

因此，我尝试使用一百万个整数的向量并得到：

Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds

为了确定，我跑了几次。是的，这种现象是真实的。我的关键代码是：

void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label
         << duration_cast<microseconds>(t1 — t0).count()
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}

至少在这个编译器、标准库和优化器设置中，这种现象是真实的。不同的实现可以而且确实会给出不同的答案。事实上，有人确实做了一个更系统的研究（快速的网络搜索就会发现它），大多数实现都显示了这种效果。

一个原因是分支预测：排序算法中的关键操作是或等效的。对于排序序列，该测试始终为真，而对于随机序列，选择的分支随机变化。“if(v[i] < pivot]) …”

另一个原因是，当向量已经排序时，我们永远不需要将元素移动到正确的位置。这些小细节的影响是我们看到的五六倍。

快速排序（以及一般的排序）是一项复杂的研究，吸引了计算机科学界一些最伟大的思想家。一个好的排序函数是选择一个好的算法并在其实现中注意硬件性能的结果。

如果你想写出高效的代码，你需要对机器架构有一点了解。

这个问题植根于 CPU 上的分支预测模型。我建议阅读这篇论文：

通过多分支预测和分支地址缓存提高指令获取率（但现在真正的 CPU 仍然不会在每个时钟周期进行多个分支预测，除了 Haswell 和后来在其循环缓冲区中有效地展开微小的循环。现代 CPU 可以预测多个分支，这些分支未被用于在大型连续块中利用其获取。

当您对元素进行排序时，分支预测可以轻松正确预测，除非就在边界处，让指令有效地流过 CPU 管道，而不必倒带并采用正确的错误预测路径。

快速简单理解的答案（阅读其他内容了解更多详情）

这个概念称为分支预测

分支预测是一种优化技术，用于预测代码在确定之前将采用的路径。这很重要，因为在代码执行期间，计算机会预取多个代码语句并将它们存储在管道中。

问题出现在条件分支中，其中有两个可能的路径或代码部分可以执行。

当预测为真时，优化技术就奏效了。

当预测是错误的时，用简单的方式解释它，存储在管道中的代码语句被证明是错误的，并且必须完全重新加载实际代码，这占用了大量时间。

正如常识所表明的那样，对有序事物的预测比对未分类事物的预测要准确得多。

分支预测可视化：

已排序 未排序