22 题: 为什么处理排序数组比处理未排序数组更快?

在...创建的问题 Tue, Jun 4, 2019 12:00 AM

这是一段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);
    }
}

具有类似但不太极端的结果。


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

  • 发生了什么事?
  • 为什么处理排序数组比处理未排序数组更快?代码总结了一些独立的术语,因此顺序无关紧要。
23151
  1. 仅供记录。在Windows /VS2017 /i7-6700K 4GHz上,两个版本之间没有区别。两种情况都需要0.6秒。如果外部循环中的迭代次数增加10倍,则两种情况下执行时间也会增加10次,达到6次。
    2017-11-15 20:45:37Z
  2. @ user194715:任何使用cmov或其他无分支实现的编译器(如pcmpgtd的自动向量化)都将具有不依赖于任何CPU的数据性能。但是,如果它是分支的,它将依赖于任何具有无序推测执行的CPU。 (即使是高性能的有序CPU也会使用分支预测来避免在所采用的分支上获取/解码气泡;未命中的惩罚会更小。)
    2017-12-26 07:14:57Z
  3. Woops ... re:Meltdown and Spectre
    2018-01-05 14:21:47Z
  4. @KyleMit它是否与两者有关?我没有读过很多关于
    的内容
    2018-01-10 06:26:02Z
  5. @ mohitmun,这两个安全漏洞都属于一类广泛的漏洞,分类为“分支目标注入”攻击
    2018-01-10 14:26:37Z
  6. 醇>
    22答案                              22 跨度>                         

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


    什么是分支预测?

    考虑一个铁路交界处:

    通过维基共享资源,通过Mecanismo的图片。在 CC-By-SA 3.0 许可下使用。

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

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

    火车很重,惯性很大。所以他们需要永远启动并放慢速度。

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

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

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


    考虑一个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, 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[]的所有输入值都有效。)

    基准:Core 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也无法为此分支生成条件移动。

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

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

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

        
    30295
    2019-05-27 12:42:11Z
    1. @ Mysticial为了避免转移黑客,你可以编写像int t=-((data[c]>=128))这样的东西来生成掩码。这应该更快。知道编译器是否足够聪明以插入条件移动会很有趣。
      2012-06-27 16:47:51Z
    2. @ phonetagger看看这个后续问题: stackoverflow.com/questions/11276291 /... 英特尔编译器非常接近完全摆脱外循环。
      2012-07-10 17:08:39Z
    3. @ Novelocrat只有一半是正确的。当它为零时将1移入符号位确实是UB。那是因为它是有符号整数溢出。但是,从符号位移出1是IB。右移有负有符号整数是IB。您可以进入这样的论点,即C /C ++不要求顶部位是符号指示符。但实施细节是IB。
      2013-08-18 21:04:38Z
    4. @ Mysticial非常感谢链接。看起来很有希望。我会去的。最后一个请求。对不起,但请不要介意,你能不能告诉我你怎么做int t = (data[c] - 128) >> 31; sum += ~t & data[c];来取代上面原来的条件?
      2014-03-08 20:05:22Z
    5. 我的语法要求我认为这应该是“...分支预测的受害者失败 ”而不仅仅是“..分支预测的受害者失败。“
      2015-06-27 11:35:58Z
    6. 醇>

    分支预测。

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

        
    3907
    2016-08-05 07:53:10Z
    1. 对于排序数组与具有不同模式的数组,分支预测是否更有效?例如,对于数组 - &gt; {10,5,20,10,40,20,...}来自模式的数组中的下一个元素是80.这种数组是否会被分支预测加速,其中下一个元素是80,如果模式是遵循?或者它通常只对排序数组有帮助吗?
      2014-09-23 18:58:12Z
    2. 所以基本上我通常学到的关于big-O的一切都是在窗外?分拣成本比分支成本更好?
      2014-10-30 07:51:58Z
    3. @ AgrimPathak这取决于。对于不太大的输入,当具有较高复杂度的算法的常数较小时,具有较高复杂度的算法比具有较低复杂度的算法更快。在哪里收支平衡点很难预测。另外,比较这个,地方很重要。 Big-O很重要,但它不是表现的唯一标准。
      2014-10-30 10:14:12Z
    4. 何时进行分支预测?什么时候语言会知道数组是排序的?我正在考虑数组的情况,如:[1,2,3,4,5,... 998,999,1000,3,10001,10002]?这个模糊的3会增加运行时间吗?它会和未排序的数组一样长吗?
      2014-11-09 13:37:18Z
    5. @ FilipBartuzi分支预测发生在处理器中,低于语言级别(但语言可能提供告诉编译器可能性的方法,因此编译器可以发出适合的代码那个)。在您的示例中,乱序3将导致分支错误预测(对于适当的条件,其中3给出的结果与1000不同),因此处理该数组可能比一个数组长几十或几百纳秒排序的数组几乎不会引人注意。花费时间的是错误预测率高,每1000次误预测不多。
      2014-11-09 13:49:37Z
    6. 醇>

    数据排序时性能大幅提升的原因是分支预测损失被删除,正如 Mysticial的回答

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

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

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

    C,即C++中,将直接编译(没有任何优化)到x86中的条件移动指令的语句是三元运算符... ? ... : ...。因此,我们将上述语句重写为等效语句:

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

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

    在英特尔 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
    
    由于使用了max2指令,cmovge使用的代码少得多。但真正的好处是,max2不涉及分支跳转,jmp,如果预测结果不正确,则会产生显着的性能损失。

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

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

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

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

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

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

        
    3144
    2019-05-27 12:50:22Z
    1. 除非您在GCC命令行中添加-O,否则没有默认的优化级别。 (你的英语不会超过我的;)
      2012-06-28 14:04:45Z
    2. 我发现很难相信编译器可以比等效的if语句更好地优化三元运算符。您已经证明GCC将三元运算符优化为条件运算;你没有表明它对if语句没有做同样的事情。事实上,根据上面的Mystical,GCC 将if语句优化为条件移动,这会使这个答案完全错误。
      2012-06-30 15:29:23Z
    3. @ WiSaGaN代码没有任何说明,因为你的两段代码编译成相同的机器代码。至关重要的是,人们不会认为你的例子中的if语句与你的例子中的terenary有所不同。你确实拥有你上一段中的相似之处,但这并不能抹掉这个例子其余部分有害的事实。
      2012-10-11 03:12:02Z
    4. @ WiSaGaN如果您修改了删除误导性-O0示例的答案并在优化中显示差异,我的downvote肯定会成为一个upvote asm在你的两个测试用例上。
      2012-10-11 04:13:03Z
    5. @ UpAndAdam在测试的那一刻,VS2010即使在指定高优化级别时也无法将原始分支优化为条件移动,而gcc可以。
      2013-09-14 15:18:02Z
    6. 醇>

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

    从原始循环开始:

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

    那个比之前快10万倍。

        
    2159
    2019-05-27 12:51:33Z
    1. 如果你想作弊,你可以在循环外进行乘法,并在循环后求和* = 100000。
      2012-10-11 01:48:01Z
    2. @ Michael - 我相信这个例子实际上是循环不变吊装(LIH)优化,而不是循环交换。在这种情况下,整个内部循环独立于外部循环,因此可以从外部循环中提升,因此结果只需乘以一个总和i的一个单位= 1e5。它对最终结果没有影响,但我只是想直接设置记录,因为这是一个经常光顾的页面。
      2013-03-04 12:59:11Z
    3. 虽然不是交换循环的简单精神,但此时内部if可以转换为:sum += (data[j] >= 128) ? data[j] * 100000 : 0;,编译器可以将其减少到cmovge或等效。
      2013-05-15 11:57:16Z
    4. 外部循环是使内循环所花费的时间足够大以进行分析。那你为什么要循环交换呢?最后,无论如何都会删除该循环。
      2016-06-22 15:45:19Z
    5. @saurabheights:错误的问题:编译器为什么不循环交换。 Microbenchmarks很难;)
      2016-12-29 13:58:53Z
    6. 醇>

    毫无疑问,我们中的一些人会对识别对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)行在cachegrind的分支预测模型下导致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)
    ...
    

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

        
    1800
    2012-10-18 19:20:21Z
    1. 这是可怕的,在未排序的列表中,应该有50%的机会点击添加。不知何故,分支预测只有25%的未命中率,它怎么能比50%的未命中率好?
      2013-12-09 04:00:09Z
    2. @ tall.b.lo:25%属于所有分支 - 循环中有两个分支,一个用于data[c] >= 128(其中如你所暗,有50%的未命中率,而有一个用于循环条件c < arraySize,其失误率约为0%。
      2013-12-09 04:29:25Z
    3. 醇>

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

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

    这种方法一般适用于:

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

      背景和原因强>

      从处理器的角度来看,你的记忆很慢。为了弥补速度的差异,处理器(L1 /L2缓存)中内置了几个缓存。所以想象一下,你正在进行漂亮的计算并弄清楚你需要一块内存。处理器将获得其“加载”操作并将内存加载到缓存中 - 然后使用缓存执行其余计算。由于内存相对较慢,因此“加载”会降低程序的速度。

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

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

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

      构建表格

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

      在这种情况下:&gt; = 128表示我们可以保留该值,&lt; 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();
      
          
    1259
    2019-01-16 04:47:21Z
    1. 你想绕过分支预测器,为什么?这是一个优化。
      2013-04-24 17:50:33Z
    2. 因为没有分支比分支更好:-)在很多情况下,这只是快得多......如果你正在优化,那绝对值得尝试。他们在f.ex中也使用了相当多的东西。 graphics.stanford.edu/~seander/bithacks.html
      2013-04-24 21:57:13Z
    3. 一般情况下,查找表可能很快,但是您是否针对此特定条件运行了测试?你的代码中仍然会有一个分支条件,现在它只被移动到查找表生成部分。你仍然不会得到你的性能提升
      2013-12-19 21:45:03Z
    4. @ Zain如果你真的想知道......是:分支15秒,我的版本10分。无论如何,知道这两种方式都是一种有用的技术。
      2013-12-20 18:57:29Z
    5. 为什么不sum += lookup[data[j]] lookup是一个包含256个条目的数组,第一个是零,最后一个是否等于索引?
      2014-03-12 12:17:49Z
    6. 醇>

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

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

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

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

    if声明的表现取决于其状况是否具有可预测的模式。如果条件始终为真或始终为假,则处理器中的分支预测逻辑将获取模式。另一方面,如果模式不可预测,那么if-statement将会更加昂贵。

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

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

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

        
    1129
    2019-02-27 10:58:32Z
    1. 您不显示“随机”TF模式的时间。
      2013-02-23 02:31:21Z
    2. @ MooingDuck'因为它不会产生任何影响 - 该值可以是任何值,但它仍将处于这些阈值的范围内。那么为什么在你已经知道限制时会显示随机值?虽然我同意你可以为了完整性而展示一个,而且“只是为了它的he”。
      2016-03-28 12:58:51Z
    3. @ cst1992:现在他最慢的时间是TTFFTTFFTTFF,在我的人眼看来,这似乎是可以预测的。随机本身就是不可预测的,所以完全有可能它会更慢,因此超出了这里所示的限制。 OTOH,可能是TTFFTTFF完全击中了病理情况。不能说,因为他没有显示随机的时间。
      2016-03-28 18:27:16Z
    4. @ MooingDuck对于人眼来说,“TTFFTTFFTTFF”是一个可预测的序列,但我们在这里讨论的是内置在CPU中的分支预测器的行为。分支预测器不是AI级模式识别;这很简单。当你只是交替分支时,它不能很好地预测。在大多数代码中,分支几乎始终以相同的方式运行;考虑一个执行一千次的循环。循环结束时的分支返回到循环的开始999次,然后第1000次执行不同的操作。一个非常简单的分支预测器通常很好用。
      2016-07-20 21:07:37Z
    5. @ steveha:我认为你正在假设CPU分支预测器是如何工作的,我不同意这种方法。我不知道该分支预测器有多先进,但我似乎认为它比你更先进。你可能是对的,但测量肯定会很好。
      2016-07-20 21:10:18Z
    6. 醇>

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

    但在这种情况下,我们知道值在[0,255]范围内,我们只关心值&gt; = 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语句的版本快得多。

    但在我的测试中,显式查找表略快于此,可能是因为索引到查找表的速度比位移略快。这显示了我的代码如何设置和使用查找表(在代码中对于“LookUp Table”无法想象地称为lut)。这是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语句的技术可用于决定使用哪个指针。我看到一个实现二叉树的库,而不是有两个命名指针(pLeftpRight或其他)有一个长度为2的指针数组,并使用“决策位”技术来决定遵循哪一个。例如,而不是:

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

    这个库会做类似的事情:

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

    以下是此代码的链接:红黑树永远被困惑

        
    1051
    2019-05-27 13:08:32Z
    1. 对,你也可以直接使用该位并乘以(data[c]>>7 - 这也在这里讨论过);我故意将此解决方案排除在外,但当然你是对的。只是一个小注释:查找表的经验法则是,如果它适合4KB(因为缓存),它将起作用 - 最好使表尽可能小。对于托管语言,我将其推到64KB,对于像C ++和C这样的低级语言,我可能会重新考虑(这只是我的经验)。从typeof(int) = 4开始,我会尝试坚持最多10位。
      2013-07-29 12:05:24Z
    2. 我认为使用0/1值进行索引可能会比整数乘法更快,但我想如果性能真的很重要,你应该对其进行分析。我同意小的查找表对于避免缓存压力是必不可少的,但很明显,如果你有更大的缓存,你可以使用更大的查找表,所以4KB更像是经验法则而不是硬规则。我觉得你的意思是sizeof(int) == 4?这对32位来说是正确的。我两年前的手机有一个32KB的L1缓存,所以即使4K查找表也可以工作,特别是如果查找值是一个字节而不是一个int。
      2013-07-29 22:02:13Z
    3. 可能我错过了一些东西,但在你的j中等于0或1的方法为什么不在你添加它之前将你的值乘以j而不是使用数组索引(可能应该乘以1-j而不是j
      2014-03-04 15:38:24Z
    4. @ steveha乘法应该更快,我试过在英特尔书籍中查找它,但找不到它......无论哪种方式,基准测试也给了我那个结果这里。
      2014-03-18 08:45:05Z
    5. @ steveha P.S。:另一个可能的答案是int c = data[j]; sum += c & -(c >> 7);,根本不需要乘法。
      2014-03-18 08:52:11Z
    6. 醇>

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

    实际上,阵列在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): - )强>

        
    950
    2019-05-11 11:31:12Z
    1. sum= 3137536 - 聪明。这显然不是问题的重点。问题显然是解释令人惊讶的性能特征。我倾向于说增加做std::partition而不是std::sort是有价值的。虽然实际问题不只是给出了合成基准。
      2013-07-24 16:31:30Z
    2. @ DeadMG:这确实不是给定密钥的标准二分法搜索,而是搜索分区索引;每次迭代需要一次比较。但是不要依赖这个代码,我还没有检查过它。如果您对保证正确的实施感兴趣,请告诉我。
      2013-07-24 20:37:31Z
    3. 醇>

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

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

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

    一般来说,现代处理器有很长的流水线,但为了方便起见,我们只考虑这4个步骤。

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

      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的结果。因此管道将如下所示。

      如果条件返回true,则

      if条件返回false时:

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

      那么什么是分支预测?

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

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

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

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

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

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

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

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

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

            
    774
    2018-04-10 20:13:26Z
    1. 两条指令如何一起执行?这是用单独的cpu内核完成的,还是管道指令集成在单个cpu内核中?
      2017-10-11 14:49:42Z
    2. @ M.kazemAkhgary这一切都在一个逻辑核心内。如果您有兴趣,可以参考英特尔软件开发人员手册
      2017-11-03 07:45:12Z
    3. 醇>

    官方答案来自

    1. 英特尔 - 避免分支机构错误预测的成本
    2. 英特尔 - 分行和循环重组防止错误预测
    3. 科学论文 - 分支预测计算机体系结构
    4. 书籍:J.L。Hennessy,D.A。帕特森:计算机架构:定量方法
    5. 科学出版物中的文章:T.Y。 Ye,Y.N。 Patt在分支预测上做了很多这些。
    6. 醇>

      你也可以从这个可爱的为什么分支预测器会混淆。

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

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

      所以预测因素会随着std::rand()的打击而改变方向。

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


    678
    2017-01-31 11:39:33Z

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

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

    或类似地:

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

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

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

        
    645
    2016-10-28 10:28:11Z

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

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

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

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

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

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

    ~不能用于NOT。相反,您可以通过对0进行异或来对已知为11的变量进行布尔值NOT:

     
    bool a, b;
    b = !a;
    

    可以优化为:

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

    如果a && b是一个不应该被评估的表达式,如果a & bba将不评估false,则&&)不能被b替换为&a || b将)。同样,如果a | b是一个表达式,如果ba,则不能用true代替

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

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

     &&

    在大多数情况下是最佳的(除非您希望data[c] >= 128表达式产生许多分支错误预测)。

        
    614
    2019-05-30 16:34:26Z

    这是肯定的!...

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

    如果数组已排序,则第一步的条件为false:When the input is unsorted, all the rest of the loop takes substantial time. But with sorted input, the processor is somehow able to spend not just less time in the body of the loop, meaning the buckets at offsets 0x18 and 0x1C, but vanishingly little time on the mechanism of looping.,然后成为到街道尽头的整个路径的真值。这就是你如何更快地完成逻辑的结束。另一方面,使用未排序的数组,需要进行大量的转换和处理,这使得代码运行得更慢......

    查看我在下面为您创建的图像。哪条街要快点完成?

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

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

    1。静态强>

    2。动态强>

      

    第一次微处理器使用静态分支预测   遇到条件分支,动态分支预测是   用于后续执行条件分支代码。

         

    为了有效地编写代码以利用这些代码   规则,在编写 if-else 切换语句时,请检查最多   首先是常见病例,逐步减少到最不常见的情况。   循环不一定需要任何特殊的代码排序   静态分支预测,仅作为循环迭代器的条件   通常使用。

        
    289
    2018-05-03 06:35:51Z

    这个问题已经多次得到了很好的回答。我还想提请小组注意另一个有趣的分析。

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

    链接在这里: http://www.geoffchappell.com/studies/windows/km/NTOSKRNL /API /EX /简档/demo.htm

        
    266
    2017-01-17 18:02:31Z
    1. 这是一篇非常有趣的文章(事实上,我刚刚阅读了所有文章),但它是如何回答这个问题的呢?
      2018-03-16 12:47:19Z
    2. @ PeterMortensen我对你的问题感到有点沮丧。例如,以下是该文章中的一个相关行:
      if (expression)
      {
          // Run 1
      } else {
          // Run 2
      }
      
      作者试图在此处发布的代码的上下文中讨论分析,并在此过程中尝试解释为什么分类的案例更快。
      2018-03-16 15:37:16Z
    3. 醇>

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

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

      

    在计算机体系结构中,分支预测器是a   试图猜测分支的方式的数字电路(例如   if-then-else结构)将在此之前确定。该   分支预测器的目的是改善流量   指令管道。分支预测因子在其中起着关键作用   在许多现代流水线中实现高效性能   微处理器体系结构,如x86。

         

    双向分支通常使用条件跳转来实现   指令。条件跳转可以“不采用”并继续   使用紧随其后的第一个代码分支执行   条件跳转后,或者可以“采取”并跳转到   程序存储器中不同的位置,代码的第二个分支是   存储。目前尚不清楚是否会有条件跳跃   在计算条件之前采取或不采取   条件跳转已经过了指令中的执行阶段   管道(见图1)。

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

    1. 没有分支预测器。
    2. 醇>
        

      如果没有分支预测,处理器将不得不等到   条件跳转指令已经过了执行阶段   下一条指令可以进入管道中的提取阶段。

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

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

      1. 使用分支预测器,不要进行条件跳转。我们假设预测是采取条件跳转。
      2. 醇>

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

        1. 使用分支预测器并进行条件跳转。我们假设预测是采取条件跳转。
        2. 醇>

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

            

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

          如您所见,我们似乎没有理由不使用分支预测器。

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

              
    183
    2019-06-04 16:20:33Z

    分支预测增益!

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

     if-else

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

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

    话虽如此,编译器会在实际评估之前尝试预测结果。它将从

     O      Route 1  /-------------------------------
    /|\             /
     |  ---------##/
    / \            \
                    \
            Route 2  \--------------------------------
    
    块中获取指令,如果表达式结果为真,则很棒!我们获得了评估它并在代码中取得进展所花费的时间;如果没有,那么我们运行错误的代码,刷新管道,并运行正确的块。

    可视化:

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

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

     
     // 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];               
     }
    
        
    172
    2018-03-16 12:30:45Z

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

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

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

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

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

    确实有三种不同的分支:

    转发条件分支 - 根据运行时条件,PC(程序计数器)更改为指向指令流中的转发地址。

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

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

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

    参考分配办法:

    116
    2018-03-16 10:57:23Z

    除了分支预测可能减慢你的速度之外,排序数组还有另一个优点:

    你可以有一个停止条件,而不仅仅是检查值,这样你只需要循环相关数据,然后忽略其余数据。
    分支预测只会错过一次。

     
    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
    
        
    110
    2019-03-05 09:58:40Z
    1. 是的,但是排序数组的设置成本是O(N log N),所以如果你对数组进行排序的唯一原因那么早点破解对你没有帮助是能够早点休息。但是,如果您有其他理由对数组进行预排序,那么是的,这很有价值。
      2018-11-06 12:28:29Z
    2. @LukeHutchison好观察;请参阅下面的答案以获取不同的内容。
      2019-02-27 11:47:22Z
    3. 取决于您对数据进行排序的次数与循环次数相比的次数。此示例中的排序只是一个示例,它不必位于循环
      之前
      2019-02-27 12:23:22Z
    4. 是的,这正是我在第一条评论中提出的观点:-)你说“分支预测只会错过一次”。但是你没有计算排序算法中的O(N log N)分支预测未命中,这实际上大于未分类情况下的O(N)分支预测未命中。所以你需要使用整个排序数据O(log N)次来收支平衡(可能实际上更接近O(10 log N),具体取决于排序算法,例如对于快速排序,由于缓存未命中 - mergesort更加缓存一致,因此您需要更接近O(2 log N)的用法来实现收支平衡。)
      2019-02-28 12:28:14Z
    5. 一个重要的优化虽然只做“半快速排序”,只排序小于目标枢轴值127的项目(假设一切都小于或等于枢轴在枢轴之后排序)。到达枢轴后,在枢轴之前对元素求和。这将在O(N)启动时间而不是O(N log N)中运行,尽管仍然会有很多分支预测未命中,可能是基于我之前给出的数字的O(5 N)的顺序,因为这是快速的一半。
      2019-02-28 12:34:48Z
    6. 醇>

    在ARM上,不需要分支,因为每条指令都有一个4位条件字段,以零成本进行测试。这消除了对短分支的需要,并且不会出现分支预测。因此,由于排序的额外开销,排序版本将比ARM上的未排序版本运行得慢。内部循环看起来如下所示:

     GE     
    106
    2018-05-14 14:01:18Z
    1. 你是说每条指令都是有条件的吗?所以,多指令带有R3后缀的s可以按顺序执行,而不会更改之间的值
      ______   ________
      |     |__|
      
      2018-05-14 14:04:03Z
    2. 是的,正确的,每条指令都可以以ARM为条件,至少在32位和64位指令集中。有一个专门的4位条件字段。您可以在具有相同条件的行中连续使用多条指令,但在某些时候,如果条件为false的可能性不可忽略,则添加分支会更有效。
      2018-05-15 17:06:42Z
    3. ARM中的另一项创新是添加了S指令后缀,在(几乎)所有指令上也是可选的,如果不存在,则会阻止指令更改状态位(使用CMP指令除外,其作用是设置状态位,因此不需要S后缀)。这允许您在许多情况下避免使用CMP指令,只要比较为零或类似(例如,当R0达到零时,SUBS R0,R0,#1将设置Z(零)位)。条件和S后缀会产生零开销。这是一个非常漂亮的ISA。
      2018-05-15 17:06:54Z
    4. 不添加S后缀允许您连续有几个条件指令,而不必担心其中一个可能会更改状态位,否则可能会产生副作用跳过其余的条件指令。
      2018-05-15 17:08:22Z
    5. 醇>

    由于称为分支预测的现象,分类数组的处理速度比未分类数组快。

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

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

    你的问题的答案非常简单。

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

    Sorted Array:直道     ____________________________________________________________________________________      - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -     TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

    未排序数组:弯曲道路

     
    ___________________________________________ Straight road
     |_________________________________________|Longer road
    

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

     n.log(n)

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


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

      

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

        
    96
    2019-05-27 12:47:18Z
    1. “用简单的话说” - 我觉得你的解释不像火车那么简单,而且远比其他任何答案都准确得多,尽管我不是初学者。我很好奇为什么会有这么多的赞成,或许未来的一位赞助人可以告诉我?
      2018-07-04 13:54:21Z
    2. @ Sinatr它可能真的是基于意见,我自己并且它足以支持它,它不像其他例子那么准确,这就是重点:放弃答案(因为我们都同意这里涉及分支预测)而没有读者像其他人那样进行技术解释(很好)。我认为他做得很好。
      2018-07-09 12:45:50Z
    3. 它不会做出更少的预测 - 它会减少不正确的预测。它仍然需要通过循环每次预测。
      2018-07-16 01:28:03Z
    4. 哦,你的正确,我的不好,谢谢你@Simon_Weaver,我会在一段时间内纠正它,或者请你可以编辑它然后我会批准它,在此先感谢...
      2018-07-16 05:52:47Z
    5. 醇>

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

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

    仅对k元素部分进行排序以线性时间而不是

    #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;
    }
    
    完成预处理。  

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

        
    17
    2019-02-28 15:24:59Z
    1. 我真的不明白这是怎么回事?你唯一展示的是“没有完成整个数组排序的所有工作所需的时间比排序整个数组要少”。您声称“运行速度最快”的说法非常依赖于架构。请参阅我的答案,了解它如何在ARM上运行。 PS你可以通过将总和放在200元素的块循环中,反向排序,然后使用Yochai Timmer的建议,一旦你得到一个超出范围的值,就可以使你的代码在非ARM架构上更快。这样,每个200元素的块总和可以提前终止。
      2019-02-28 12:18:29Z
    2. @ LukeHutchison证明是针对OP的,而不是像你这样知情的回答者。对于OP,这使得排序与更快处理有关的假设无效(参见问题标题措辞)。在通用架构的算法意义上“运行最快” - ARM是一种特殊情况。 Yochai Timmer的建议是一种可靠的优化,在大O意义上是非算法的。此外,一般来说,人们会在真实和虚假的情况下做一些事情,所以Yochai的黑客不适用&amp;
      。可能比总和更重要
      2019-02-28 15:21:15Z
    3. 醇>
来源放置 这里