java - 为什么处理排序数组比处理未排序数组更快?




c++ performance (14)

这是一段看似非常特殊的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;
}
  • 没有std::sort(data, data + arraySize); ,代码运行时间为11.54秒。
  • 使用排序数据,代码运行1.93秒。

最初,我认为这可能只是一种语言或编译器异常。 所以我用Java试了一下。

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);
    }
}

有点相似但不太极端的结果。

我的第一个想法是排序将数据带入缓存,但后来我认为这是多么愚蠢,因为数组刚刚生成。

  • 到底是怎么回事?
  • 为什么处理排序数组比处理未排序数组更快?
  • 代码总结了一些独立的术语,顺序无关紧要。

分支预测。

对于排序数组,条件data[c] >= 128对于条纹值首先为false ,然后对于所有后续值变为true 。 这很容易预测。 使用未排序的数组,您需要支付分支成本。


分支预测增益!

重要的是要理解分支错误预测不会减慢程序的速度。错过预测的成本就像分支预测不存在一样,您等待表达式的评估以决定运行什么代码(在下一段中进一步说明)。

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

只要有if-else\ switch_语句,就必须计算表达式以确定应该执行哪个块。在编译器生成的汇编代码中,插入了条件branch指令。

分支指令可以使计算机开始执行不同的指令序列,从而偏离其按顺序执行指令的默认行为(即,如果表达式为假,则程序跳过if块的代码),这取决于某些条件,即在我们的案例中的表达评估。

话虽这么说,编译器会尝试在实际评估之前预测结果。它会从if块中获取指令,如果表达式是真的,那就太好了!我们获得了评估它并在代码中取得进展所花费的时间; 如果没有,那么我们运行错误的代码,刷新管道,并运行正确的块。

可视化:

假设您需要选择路线1或路线2.等待您的伴侣检查地图,您已停在##并等待,或者您可以选择路线1,如果您幸运(路线1是正确路线),然后很棒,你不必等待你的伴侣检查地图(你节省了检查地图所需的时间),否则你只需要回头。

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

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

在同一行(我认为没有任何答案突出显示),有时候(特别是在性能很重要的软件中,比如在Linux内核中)你可以找到一些if语句如下所示:

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

或者类似的:

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

双方likely()unlikely()在由使用像海湾合作委员会的定义其实宏__builtin_expect帮助编译器插入代码的预测偏向考虑到用户提供的信息的条件。 GCC支持其他可能改变正在运行的程序行为的内置函数或发出低级指令,如清除缓存等。请参阅此文档该文档通过可用的GCC内置函数。

通常,这种优化主要在硬实时应用程序或嵌入式系统中找到,其中执行时间很重要且非常重要。例如,如果您正在检查仅发生1/10000000次的错误情况,那么为什么不通知编译器呢?这样,默认情况下,分支预测会假设条件为假。


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

实际上,阵列被分隔在一个连续的区域data < 128和另一个区域data >= 128。因此,您应该使用二分法搜索(使用Lg(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];

一种更快的方法,即为排序或未排序提供近似解决方案:( sum= 3137536;假设真正均匀分布,16384个样本,期望值为191.5):-)


官方的答案是来自

  1. 英特尔 - 避免分支机构错误预测的成本
  2. 英特尔 - 分支和循环重组以防止错误预测
  3. 科学论文 - 分支预测计算机结构
  4. 书籍:JL Hennessy,DA Patterson:计算机体系结构:定量方法
  5. 科学出版物中的文章:TY Yeh,YN Patt在分支预测中做了很多这些。

您还可以从这个可爱的diagram看到为什么分支预测器会混淆。

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

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

因此,预测因素将会改变方向std::rand()

另一方面,一旦它被排序,预测器将首先进入强烈未被采用的状态,并且当值变为高值时,预测器将在三次运行中通过从强烈不采取到强烈采取的一直改变。


当数据被排序时,性能显着提高的原因是分支预测惩罚被消除,正如的答案中精美地解释的那样。

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

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

我们可以发现这个特殊的if... else...分支的含义是在条件满足时添加一些东西。 这种类型的分支可以很容易地转换为条件移动语句,它将被编译成x86系统中的条件移动指令: cmovl 。 分支以及因此潜在的分支预测惩罚被移除。

CC++ ,这个语句可以直接编译(没有任何优化)到x86的条件移动指令,是三元运算符... ? ... : ... ... ? ... : ... 所以我们将上面的语句重写为等价的语句:

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

在保持可读性的同时,我们可以检查加速因子。

在Intel Core i7 -2600K @ 3.4 GHz和Visual Studio 2010发布模式下,基准是(从Mysticial复制的格式):

86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

64位

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

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

现在让我们通过调查它们生成的x86程序集来更仔细地查看。 为简单起见,我们使用max1max2两个函数。

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

由于使用了指令cmovge max2使用的代码要少cmovge 。 但真正的好处是max2不涉及分支跳转, jmp ,如果预测结果不正确,则会产生显着的性能损失。

那么为什么有条件的移动表现更好呢?

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

在分支情况下,以下指令由前一个指令确定,因此我们不能进行流水线操作。 我们必须等待或预测。

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

计算机系统:程序员视角 ”一书第二版详细解释了这一点。 您可以检查第3.6.6节有关条件移动指令 ,整个第4章用于处理器体系结构 ,第5.11.2节用于特殊处理分支预测和错误预测惩罚

有时,一些现代编译器可以优化我们的代码以便以更好的性能进行汇编,有时一些编译器不能(有问题的代码使用Visual Studio的本机编译器)。 在不可预测的情况下了解分支和条件移动之间的性能差异可以帮助我们在场景变得如此复杂以至于编译器无法自动优化它们时编写具有更好性能的代码。


我刚刚读到了这个问题及其答案,我觉得答案遗失了。

消除我发现在托管语言中工作特别好的分支预测的常用方法是查找表而不是使用分支(尽管在这种情况下我还没有测试过它)。

如果符合以下情况,此方法通用

  1. 它是一个小桌子,可能会被缓存在处理器中
  2. 您正在以非常紧凑的循环运行和/或处理器可以预加载数据

背景和原因

Pfew,那到底是什么意思呢?

从处理器的角度来看,你的记忆很慢。 为了弥补速度上的差异,他们在处理器(L1 / L2缓存)中构建了几个缓存来补偿这一点。 所以想象一下,你正在做你很好的计算,并发现你需要一块记忆。 处理器将进行“加载”操作并将内存加载到缓存中 - 然后使用缓存执行其余计算。 因为内存相对较慢,这种“加载”会降低程序的速度。

与分支预测一样,这在Pentium处理器中进行了优化:处理器预测它需要加载一段数据并尝试在操作实际到达缓存之前将其加载到缓存中。 正如我们已经看到的那样,分支预测有时会出现可怕的错误 - 在最坏的情况下,您需要返回并实际等待内存负载,这将需要永远( 换句话说:失败的分支预测是坏的,一个内存在分支预测失败后加载是非常可怕的! )。

幸运的是,如果内存访问模式是可预测的,处理器将把它加载到快速缓存中,一切都很好。

我们需要知道的第一件事是什么? 虽然较小通常更好,但经验法则是坚持查找大小<= 4096字节的表。 作为上限:如果您的查找表大于64K,则可能值得重新考虑。

构建一个表

所以我们已经发现我们可以创建一个小表。 接下来要做的是获得一个查找功能。 查找函数通常是使用几个基本整数运算的小函数(和,或者,xor,shift,add,remove和multiply)。 您希望通过查找功能将您的输入转换为表格中的某种“唯一键”,然后简单地为您提供您希望它完成的所有工作的答案。

在这种情况下:> = 128意味着我们可以保留值,<128意味着我们摆脱它。 最简单的方法是使用'AND':如果我们保留它,我们和它一起使用7FFFFFFF; 如果我们想摆脱它,我们和它为0.注意,128也是2的幂 - 所以我们可以继续制作一个32768/128整数的表并填充一个零和很多7FFFFFFFF的。

托管语言

您可能想知道为什么这在托管语言中运行良好。 毕竟,托管语言使用分支检查数组的边界,以确保您不会陷入困境......

好吧,不完全...... :-)

为管理语言消除此分支已经做了相当多的工作。 例如:

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

在这种情况下,编译器显然不会遇到边界条件。 至少Microsoft JIT编译器(但我希望Java做类似的事情)会注意到这一点,并完全取消检查。 哇 - 这意味着没有分支。 同样,它将处理其他明显的案例。

如果您在托管语言上查找时遇到麻烦 - 关键是在查找函数中添加& 0x[something]FFF以使边界检查可预测 - 并且观察它更快。

这种情况的结果

// 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.Next(256);

//To keep the spirit of the code in-tact 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();

毫无疑问,我们中的一些人会对识别对CPU的分支预测器有问题的代码感兴趣。 Valgrind工具cachegrind有一个分支预测模拟器,使用--branch-sim=yes标志启用。 在这个问题的例子中运行它,外部循环的数量减少到10000并用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生成的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)行在cachegrind的branch-predictor模型下导致164,050,007个错误预测的条件分支( Bcm ),而它仅在排序版本中导致10,006 。

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

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


由于称为分支预测的现象,排序的阵列比未排序的阵列处理得更快。

分支预测器是一种数字电路(在计算机体系结构中),试图预测分支将采用哪种方式,从而改善指令流水线中的流量。电路/计算机预测下一步并执行它。

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

你的问题的答案很简单。

在未排序的数组中,计算机会进行多次预测,从而导致出错的可能性增加。然而,在排序中,计算机进行的预测更少,从而减少了出错的可能性。进行更多预测需要更多时间。

分类阵列:直道

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

未排序的阵列:弯曲的道路

______   ________
|     |__|

分支预测:猜测/预测哪条道路是直的并且在没有检查的情况下跟随它

___________________________________________ Straight road
 |_________________________________________|Longer road

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

更新:在@Simon_Weaver所说的之后,我想添加另一个事实......“它不会做出更少的预测 - 它会减少不正确的预测。它仍然需要预测每次循环。”


这是关于分支预测。 它是什么?

  • 分支预测器是古老的性能改进技术之一,它仍然与现代建筑相关。虽然简单的预测技术提供快速查找和功率效率,但是它们具有高的误预测率。

  • 另一方面,复杂的分支预测 - 无论是基于神经的还是两级分支预测的变体 - 提供更好的预测准确性,但它们消耗更多的功率和复杂性以指数方式增加。

  • 除此之外,在复杂的预测技术中,预测分支所花费的时间本身非常高,从2到5个周期 - 这与实际分支的执行时间相当。

  • 分支预测本质上是一种优化(最小化)问题,其中重点在于以最少的资源实现最低可能的未命中率,低功耗和低复杂度。

确实有三种不同的分支:

转发条件分支 - 基于运行时条件,PC(程序计数器)被改变为指向指令流中的前向地址。

向后条件分支 - PC在指令流中变为指向后向。分支基于某些条件,例如,当循环结束时的测试表明循环应该再次执行时,向后分支到程序循环的开头。

无条件分支 - 包括跳转,过程调用和没有特定条件的返回。例如,无条件跳转指令可能用汇编语言编码为简单的“jmp”,并且指令流必须立即定向到跳转指令指向的目标位置,而条件跳转可能被编码为“jmpne”仅当先前“比较”指令中两个值的比较结果显示值不相等时,才会重定向指令流。 (x86架构使用的分段寻址方案增加了额外的复杂性,因为跳转可以是“接近”(在一个段内)或“远”(在段外)。每种类型对分支预测算法都有不同的影响。)

静态/动态分支预测:微处理器在第一次遇到条件分支时使用静态分支预测,并且动态分支预测用于条件分支代码的后续执行。

参考文献:


除了分支预测可能会降低您的速度之外,排序数组还有另一个优势:

您可以设置停止条件而不是仅检查值,这样您只需循环访问相关数据,并忽略其余数据。
分支预测只会遗漏一次。

 // sort backwards (higher values first)
 std::sort(data, data + arraySize, std::greater<int>());

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

在ARM上,不需要分支,因为每条指令都有一个4位条件字段,以零成本进行测试。这消除了对短分支的需要,并且不会出现分支预测。因此,由于排序的额外开销,排序版本将比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

正如其他人已经提到的那样,神秘的背后是分支预测器。

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

在计算机体系结构中,分支预测器是一种数字电路,它试图猜测分支(例如if-then-else结构)在确定之前会走哪条路。分支预测器的目的是改善指令流水线中的流程。分支预测器在许多现代流水线微处理器架构(如x86)中实现高效性能方面发挥着关键作用。

双向分支通常使用条件跳转指令来实现。条件跳转可以是“未采用”并继续执行第一个代码分支,紧接在条件跳转之后,或者可以“采取”并跳转到程序存储器中的不同位置,其中第二个代码分支是存储。在计算条件并且条件跳转已经过指令流水线中的执行阶段之前,不确定是否采取条件跳转是未知的(见图1)。

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

  1. 没有分支预测器。

在没有分支预测的情况下,处理器必须等到条件跳转指令已经通过执行阶段,然后下一条指令才能进入流水线中的获取阶段。

该示例包含三条指令,第一条是条件跳转指令。后两条指令可以进入流水线,直到执行条件跳转指令。

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

  1. 使用分支预测器,不要进行条件跳转。让我们假设预测没有采取条件跳跃。

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

  1. 使用分支预测器并进行条件跳转。让我们假设预测没有采取条件跳跃。

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

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

如您所见,似乎我们没有理由不使用Branch Predictor。

这是一个非常简单的演示,阐明了Branch Predictor的基本部分。如果这些GIF很烦人,请随时将它们从答案中删除,访问者也可以从git获取演示git


这个问题已经多次得到了很好的回答。我仍然希望将该小组的注意力吸引到另一个有趣的分析上。

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

链接在这里:http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htmhttp://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm





branch-prediction