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

Question

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

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

---

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

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

Answer 1

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

什么是分支预测？

考虑一个铁路交界处:

_{图片来自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实际上比分支慢一点.

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

更新:

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

• VC++ 2010无法为此分支生成条件移动/Ox.

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

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

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

Answer 2

分支预测.

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

Answer 3

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

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

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

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

在C,因此C++,语句,这将在直接编译(无任何优化)到条件移动指令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他们生成的组件来更仔细地观察.为简单起见,我们使用两个函数max1和max2.

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

Answer 4

如果您对可以对此代码进行的更多优化感到好奇,请考虑以下事项:

从原始循环开始:

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倍

Answer 5

毫无疑问,我们中的一些人会对识别对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我们在相关循环中看到的逐行输出:

排序方式:

          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.

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

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

Answer 6

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

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

这种方法通常适用于:

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

背景和原因

从处理器的角度来看,你的记忆很慢.为了弥补速度的差异,处理器(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 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();

Answer 7

当数组排序时,数据分布在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声明的速度比" 好 "模式慢六倍!当然,哪种模式好,哪种模式不好取决于编译器和特定处理器生成的确切指令.

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

Answer 8

避免分支预测错误的一种方法是构建查找表,并使用数据对其进行索引.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语句的版本快得多.

但在我的测试中,显式查找表略快于此,可能是因为索引到查找表的速度比位移略快.这显示了我的代码如何设置和使用查找表(lut代码中缺乏想象力的"LookUp表").这是C++代码:

// 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个值的表,这可能是实用的.

索引到数组而不是使用if语句的技术可用于决定使用哪个指针.我看到一个实现二叉树的库,而不是有两个命名指针(pLeft和/ pRight或其他)有一个长度为2的指针数组,并使用"决策位"技术来决定遵循哪一个.例如,而不是:

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

这个库会做类似的事情:

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

这是这段代码的链接:红黑树,永恒的混淆

Answer 9

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

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

Answer 10

由于分支预测,上述行为正在发生.

要理解分支预测,首先必须了解指令管道:

任何指令都被分成一系列步骤,以便可以并行地同时执行不同的步骤.这种技术称为指令流水线,用于提高现代处理器的吞吐量.要更好地理解这一点,请在维基百科上查看此示例.

通常,现代处理器具有相当长的流水线,但为了方便起见,我们仅考虑这4个步骤.

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条件返回true时:

当if条件返回false时:

作为等待指令A的结果的结果,在上述情况下花费的总CPU周期(没有分支预测;对于真和假)都是7.

那么什么是分支预测？

分支预测器将尝试猜测分支(if-then-else结构)将以何种方式确定之前.它不会等待指令A到达流水线的EX阶段,但它会猜测决定并转到该指令(在我们的例子中是B或C).

如果猜测正确,管道看起来像这样:

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

在OP的代码中,第一次有条件时,分支预测器没有任何基于预测的信息,所以第一次它会随机选择下一条指令.稍后在for循环中,它可以基于历史记录进行预测.对于按升序排序的数组,有三种可能性:

1. 所有元素都小于128
2. 所有元素都大于128
3. 一些起始新元素小于128,后来大于128

让我们假设预测器将在第一次运行时始终采用真分支.

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

在所有这些情况下,故障的数量将会减少,因此,只需要几次就可以丢弃部分执行的指令并重新使用正确的分支,从而减少CPU周期.

但是在随机未排序的数组的情况下,预测将需要丢弃部分执行的指令并且在大多数时间重新开始使用正确的分支,并且与排序的数组相比产生更多的CPU周期.

Answer 11

官方的答案是来自

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

您还可以从这个可爱的图表中看到为什么分支预测器会混淆.

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

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

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

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

Answer 12

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

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

或类似的:

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

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

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

Answer 13

在C++中经常使用的布尔运算在编译的程序中产生许多分支.如果这些分支是在循环内部并且很难预测它们会显着减慢执行速度.布尔变量存储为8位整数,其值为0for false和1for 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.编译器没有做出这样的假设的原因是,如果变量未初始化或来自未知来源,则变量可能具有其他值.上面的代码可以被优化,如果a和b都被初始化为有效值,或者如果它们来自运营商产生布尔输出.优化的代码如下所示:

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

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

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

bool a, b;
b = !a;

可以优化为:

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

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

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

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

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

Answer 14

这是肯定的!...

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

如果对数组进行排序,则在第一步中您的条件为false:data[c] >= 128然后成为到街道尽头的整个路径的真值.这就是你如何更快地完成逻辑的结束.另一方面,使用未排序的数组,您需要进行大量的转换和处理,这会使您的代码运行得更慢...

看下面我为你创建的图片.哪条街要快点完成？

因此,以编程方式,分支预测会导致进程变慢...

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

1.静态

2.动态

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

为了有效地编写代码以利用这些规则,在编写if-else或switch语句时,首先检查最常见的情况,然后逐步处理最不常见的情况.循环不一定需要任何特殊的代码排序用于静态分支预测,因为通常只使用循环迭代器的条件.

Answer 15

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

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

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

Answer 16

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

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

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

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

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

1. 没有分支预测器.

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

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

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

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

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

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

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

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

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

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

Answer 17

分支预测增益!

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

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

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

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

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

可视化:

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

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

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

Answer 18

这是关于分支预测.它是什么？

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

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

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

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

确实有三种不同的分支:

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

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

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

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

参考文献:

• 分支预测器

• 自我描绘的证明

• 分支预测评论

• 分支预测

Answer 19

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

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

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

Answer 20

在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

Answer 21

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

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

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

你的问题的答案很简单.

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

分类阵列:直道

______   ________
|     |__|

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

___________________________________________ Straight road
 |_________________________________________|Longer road

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

______   ________
|     |__|

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

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

它不会减少预测 - 它会减少不正确的预测.它仍然必须通过循环每次预测..

Answer 22

我在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.

我得到的@GManNickG中的C代码结果是：

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

基于此，MATLAB看上去比不进行排序的C实现慢了175倍，而进行排序却慢了350倍。换句话说，（分支预测）的效果是1.46x为MATLAB实现和2.7倍的C实现。

Answer 23

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

通过多分支预测和分支地址缓存提高指令提取率

当您对元素进行排序后，IR就不会费心一次又一次地获取所有 CPU 指令。它从缓存中获取它们。

Answer 24

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

以下代码不对整个数组进行排序,而是仅对其中的200个元素进行排序,从而运行得最快.

仅对k元素部分进行排序以线性时间完成预处理而不是O(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;
}

这也"证明"它与任何算法问题无关,例如排序顺序,它确实是分支预测.

Answer 25

快速简单理解的答案（阅读其他内容以获取更多详细信息）

这个概念称为分支预测

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

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

当预测正确时，优化技术就奏效了。

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

正如常识表明的那样，对已排序事物的预测比对未排序事物的预测准确得多。

分支预测可视化：

已排序
未排序的

Answer 26

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]) …”等于或等效。对于排序的序列，测试始终为真，而对于随机序列，选择的分支随机变化。

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

快速排序（通常是排序）是一项复杂的研究，吸引了计算机科学的一些最伟大的头脑。好的排序功能是选择好的算法并在实现过程中注意硬件性能的结果。

如果要编写高效的代码，则需要了解一些有关计算机体系结构的知识。

Answer 27

分支预测

这称为分支预测。如果没有分支预测，处理器将不得不等到条件跳转指令通过执行阶段，然后下一条指令才能进入流水线中的提取阶段。分支预测器试图通过尝试猜测是否最有可能采用或不采用条件跳转来避免这种时间浪费。然后被猜测为最可能的分支被提取并推测性地执行。如果稍后检测到猜测是错误的，则推测性地执行，导致延迟。

data[c] >= 128

从这个链接获得更多帮助：Multiple Branch Prediction for Wide-Issue Superscalar