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

这是一个C ++代码,看起来很奇特。出于一些奇怪的原因,对数据进行排序后使得代码神奇地快了近6倍。

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

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

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

  • 到底是怎么回事?
  • 为什么处理排序后的数组比未排序的数组更快?
  • 代码正在总结一些独立的术语,顺序应该不重要。

问题评论

  • 只是为了记录。在Windows / VS2017 / i7-6700K 4GHz两个版本之间没有区别。这两种情况都需要0.6s。如果外部循环的迭代次数增加了10倍,执行时间也增加了10倍,至6s。
  • 任何使用一个cmov或其他无分支实现(如自动矢量化pcmpgtd)的编译器将具有不依赖于任何CPU的数据的性能。但是,如果它是分支的,它将依赖于任何具有无序推测执行的CPU的排序。(即使是高性能的有序CPU使用分支预测来避免在采取的分支上获取/解码泡泡;缺失惩罚更小)。
  • @KyleMit和它们有什么关系?我还没有读太多
  • @mohitmun,这两个安全漏洞都属于被分类为“分支目标注入”攻击的一大类漏洞

 

答案:

 

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

什么是分支预测?

考虑一个铁路交界处:

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

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

火车很重,有很多的惯性。所以他们永远都要开始放慢速度。

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

  • 如果你猜对了,它会继续。
  • 如果你猜错了,那么队长会停下来,然后向你大喊,打开开关。然后它可以重新启动其他路径。

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

 

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

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

现代处理器复杂,流水线长。所以他们永远要“热身”,“放慢速度”。

有没有更好的办法?你猜猜分支会走哪个方向!

  • 如果你猜对了,你继续执行。
  • 如果你猜错了,你需要刷新管道并回滚到分支。然后你可以重新开始下另一个路径。

如果你每次都猜对了,执行永远不会停止。
如果你经常猜错,你会花费很多时间拖延,回滚,然后重新开始。

这是分支预测。我承认这不是最好的比喻,因为火车可以用一面旗子标出方向。但在计算机中,处理器不知道分支将走向哪个方向,直到最后一刻。

那么你怎么会战略性地猜测,以尽量减少火车必须备份和走下另一条路的次数呢?你看过去的历史!如果火车剩下99%的时间,那么你猜就走了。如果它交替,那么你交替你的猜测。如果每三次都有一种方法,你猜也一样。

换句话说,你试图找出一个模式并遵循它。这或多或少是分支预测器的工作原理。

大多数应用程序都有良好的分支。所以现代分支预测器通常会达到> 90%的命中率。但是当面对不可预知的分支而没有可识别的模式时,分支预测器实际上是无用的。

进一步阅读:维基百科的“分支预测”文章

正如上文所暗示的,罪魁祸首是这个陈述:

 

if (data >= 128)
    sum += data;

 

请注意,数据在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 >= 128)
    sum += data;

有:

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

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

(请注意,这个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

观察:

  • 与分支:排序和未排序的数据之间有巨大的差异。
  • 与黑客:有序和未分类的数据没有区别。
  • 在C ++的情况下,在数据排序的时候,hack实际上比分支要慢。

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

 

更新:

  • 具有-O3-ftree-vectorize在x64上的GCC 4.6.1 能够产生条件移动。所以排序和未排序的数据没有区别 – 两者都很快。
  • VC ++ 2010无法为此分支生成条件移动/Ox
  • 英特尔编译器11做了一些奇迹。它交换两个循环,从而将不可预知的分支提升到外部循环。所以它不仅可以避免错误预测,而且还是VC ++和GCC可以产生的速度的两倍。换句话说,ICC利用测试循环来打败基准…
  • 如果你给英特尔编译器的无分支代码,它只是向外矢量化它…和分支一样快(与循环交换)。

这表明,即使是成熟的现代编译器,其优化代码的能力也可能有很大差异。

添加评论

友情链接:蝴蝶教程