首页 文章

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

提问于
浏览
22299

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

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


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

  • 发生了什么事?

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

  • 代码总结了一些独立的术语,顺序无关紧要 .

22 回答

  • 3035

    这是肯定的!...

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

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

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

    因此,以编程方式, branch prediction 会导致进程变慢...

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

    1. Static

    2. Dynamic

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

  • 909

    在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
    
  • 609

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

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

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

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

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

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

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

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

    x86

    //  Branch - Random
    seconds = 8.885
    
    //  Branch - Sorted
    seconds = 1.528
    
    //  Branchless - Random
    seconds = 3.716
    
    //  Branchless - Sorted
    seconds = 3.71
    

    x64

    //  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
    

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

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

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

    在分支案例中,以下内容指令由前一个决定,所以我们不能做流水线操作 . 我们必须等待或预测 .

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

    Computer Systems: A Programmer's Perspective, second edition详细解释了这一点 . 您可以检查第3.6.6节有关条件移动指令,整个第4章用于处理器体系结构,第5.11.2节用于特殊处理分支预测和错误预测惩罚 .

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

  • 0

    Branch prediction.

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

  • 1201

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

    实际上,数组在 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];
    

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

  • 730

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

    要理解分支预测,首先必须了解 Instruction Pipeline

    任何指令都被分成一系列步骤,以便可以并行地同时执行不同的步骤 . 这种技术称为指令流水线,用于提高现代处理器的吞吐量 . 要更好地理解这一点,请参阅example on Wikipedia .

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

    • IF - 从内存中获取指令

    • ID - 解码指令

    • EX - 执行指令

    • WB - 写回CPU寄存器

    4-stage pipeline in general for 2 instructions.
    4-stage pipeline in general

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

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

    如果没有分支预测,将发生以下情况:

    为了执行指令B或指令C,处理器必须等到指令A没有到达流水线中的EX阶段,因为转到指令B或指令C的决定取决于指令A的结果 . 所以管道会是这样的 .

    when if condition returns true:
    enter image description here

    When if condition returns false:
    enter image description here

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

    So what is branch prediction?

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

    In case of a correct guess, the pipeline looks something like this:
    enter image description here

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

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

    • 所有元素都小于128

    • 所有元素都大于128

    • 一些起始新元素小于128,后来大于128

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

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

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

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

  • 148

    官方的答案是来自

    你也可以从这个可爱的diagram中看到为什么分支预测器会混淆 .

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

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

    因此预测变量将会因为 std::rand() 而受到影响 .

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


  • 641

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

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

    或者类似的:

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

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

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

  • 3769

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

    从原始循环开始:

    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倍

  • 2085

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

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

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

    Let's do some bench marking to understand it better

    if -statement的性能取决于其条件是否具有可预测的模式 . 如果条件始终为真或始终为假,则处理器中的分支预测逻辑将获取模式 . 另一方面,如果模式不可预测, 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
    

    bad ”真假模式可以使 if -statement比“ good ”模式慢6倍!当然,哪种模式好,哪种模式不好取决于编译器和特定处理器生成的确切指令 .

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

  • 578

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

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

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

    你的问题的答案很简单 .

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

    分类阵列:直道

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

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

    ______   ________
    |     |__|
    

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

    ___________________________________________ Straight road
     |_________________________________________|Longer road
    

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

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