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




11 Answers

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

什么是分支预测?

考虑一个铁路交界处:

来自Mecanismo,来自Wikimedia Commons。 在CC-By-SA 3.0许可下使用。

现在为了争论,假设这是在19世纪 - 在长途或无线电通信之前。

您是交叉路口的运营商,您会听到火车即将到来。 你不知道应该走哪条路。 你停下火车去询问司机他们想要的方向。 然后适当地设置开关。

火车很重,有很多惯性。 所以他们需要永远的启动和放慢速度。

有没有更好的办法? 你猜猜火车往哪个方向走!

  • 如果你猜对了,那就继续吧。
  • 如果你猜对了,机长会停下来,然后向你大喊大叫,然后翻转开关。 然后它可以重新启动另一条路径。

如果你每次都猜对了 ,火车就永远不会停下来。
如果您经常猜错 ,列车将花费大量时间停止,备份和重新启动。

考虑一个if语句:在处理器级别,它是一个分支指令:

你是一个处理器,你看到一个分支。 你不知道它会走哪条路。 你是做什么? 您暂停执行并等待前面的指令完成。 然后继续沿着正确的路径前进。

现代处理器很复杂,管道很长。 所以他们永远地“热身”和“慢下来”。

有没有更好的办法? 你猜猜分支的方向!

  • 如果你猜对了,你继续执行。
  • 如果您猜错了,则需要刷新管道并回滚到分支。 然后你可以重新启动另一条路径。

如果你每次都猜对了 ,执行将永远不会停止。
如果你经常猜错 ,你会花很多时间停滞,回滚和重新启动。

这是分支预测。 我承认这不是最好的类比,因为火车可以用旗帜向方向发出信号。 但是在计算机中,处理器直到最后一刻才知道分支将朝哪个方向发展。

那么你如何战略性地猜测火车必须备份并沿着另一条路走下去的次数呢? 你看看过去的历史! 如果火车99%的时间都离开了,那么你猜对了。 如果它交替,那么你交替猜测。 如果它每3次走一条路,你就猜相同......

换句话说,您尝试识别模式并遵循它。 这或多或少是分支预测器的工作方式。

大多数应用程序具有良好的分支。 因此,现代分支预测器通常会达到> 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)

那可以做些什么呢?

如果编译器无法将分支优化为条件移动,那么如果您愿意牺牲性能的可读性,则可以尝试一些黑客攻击。

更换:

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

有:

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

这消除了分支并用一些按位操作替换它。

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

基准测试:酷睿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

观察:

  • 使用分支:已排序和未排序的数据之间存在巨大差异。
  • 使用Hack:排序和未排序数据之间没有区别。
  • 在C ++的情况下,当数据被排序时,hack实际上比分支慢一点。

一般的经验法则是避免在关键循环中依赖数据进行分支。 (例如在这个例子中)

更新:

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

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

  • 英特尔编译器11做了一些奇迹。 它交换两个循环 ,从而将不可预测的分支提升到外循环。 因此,它不仅能够免受错误预测的影响,而且速度也是VC ++和GCC能够产生的速度的两倍! 换句话说,ICC利用测试循环来击败基准......

  • 如果你给英特尔编译器提供无分支代码,那么它就是向右矢量化它......并且与分支一样快(使用循环交换)。

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

这是一段看似非常特殊的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);
    }
}

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

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

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



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

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

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的本机编译器)。 在不可预测的情况下了解分支和条件移动之间的性能差异可以帮助我们在场景变得如此复杂以至于编译器无法自动优化它们时编写具有更好性能的代码。




毫无疑问,我们中的一些人会对识别对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)
...

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




当数组排序时,数据在0到255之间分配,迭代的前半部分将不会进入if -statement( if语句在下面共享)。

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

问题是:在某些情况下,如果排序数据的情况,上述语句不执行的原因是什么? 这是“分支预测器”。 分支预测器是一种数字电路,它试图猜测分支(例如if-then-else结构)在确定之前会走哪条路。 分支预测器的目的是改善指令流水线中的流程。 分支预测器在实现高效性能方面发挥着关键作用!

让我们做一些基准测试来更好地理解它

if -statement的性能取决于其条件是否具有可预测的模式。 如果条件始终为真或始终为假,则处理器中的分支预测逻辑将获取模式。 另一方面,如果模式不可预测, if语句将更加昂贵。

让我们用不同的条件来衡量这个循环的性能:

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语句比“ ”模式慢六倍!当然,哪种模式好,哪种模式不好取决于编译器和特定处理器生成的确切指令。

因此,分支预测对性能的影响毫无疑问!




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

实际上,阵列被分隔在一个连续的区域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()

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




在C ++中经常使用的布尔运算在编译的程序中产生许多分支。如果这些分支在内部循环中并且很难预测它们会显着减慢执行速度。布尔变量存储为8位整数,其值为0for false1for true

布尔变量是超定的,因为所有具有布尔变量作为输入的运算符检查输入是否具有除0or 之外的任何其他值1,但是具有布尔值作为输出的运算符不能产生除0or 之外的其他值1。这使得使用布尔变量作为输入的操作效率低于必要的效率。考虑示例:

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

这段代码远非最佳。如果误预测,分支机构可能需要很长时间。如果已经确定操作数没有除了0和之外的其他值,则可以使布尔运算更有效1。编译器没有做出这样的假设的原因是,如果变量未初始化或来自未知来源,则变量可能具有其他值。上面的代码可以被优化,如果ab都被初始化为有效值,或者如果它们来自运营商产生布尔输出。优化的代码如下所示:

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

char而不是bool为了使得可以使用按位运算符(&|)而不是布尔运算符(&&||)。按位运算符是单指令,只需一个时钟周期。OR运算符(|)即使a并且b具有除0或之外的其他值也可以工作1。如果操作数具有除和之外的其他值,则AND运算符(&)和EXCLUSIVE OR运算符(^)可能会产生不一致的结果。01

~不能用于NOT。相反,你可以对已知的变量01通过XOR对其进行布尔值1

bool a, b;
b = !a;

可以优化为:

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

a && b不能替换为a & bif b是一个不应该被评估的表达式,如果afalse&&将不会评估b&将)。同样地,a || b不能被替换a | b,如果b是,如果不应该被计算的表达式atrue

如果操作数是变量而不是操作数是比较,则使用按位运算符更有利:

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

在大多数情况下是最佳的(除非您希望&&表达式生成许多分支错误预测)。




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

最近这个例子(稍微修改过)也被用来演示如何在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




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

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

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

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

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

  1. 没有分支预测器。

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

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

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

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

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

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

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

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

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

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




在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



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

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

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

你的问题的答案很简单。

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

分类阵列:直道

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

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

______   ________
|     |__|

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

___________________________________________ Straight road
 |_________________________________________|Longer road

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

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




Related