为什么处理一个排序的数组比处理一个未排序的数组快？ ｜ Java-Debug实录

提问：为什么处理一个排序的数组比处理一个未排序的数组快？

这里有一段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)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {   // Primary loop
            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)
        {
            for (int c = 0; c < arraySize; ++c)
            {   // Primary loop
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}
复制代码

有一个类似但差强人意的结果

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

到底是怎么回事呢？
为什么处理一个排序的数组比处理一个未排序的数组要快？
代码是对一些独立的项进行求和，所以顺序应该不重要。

最热门回答：

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

什么是分支预测？
考虑一个铁路枢纽。

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

你是一个路口的操作员，你听到火车来了，不知道它应该往哪边走；你停下火车，问司机他们想要哪个方向，然后你适当地设置开关。

火车很重，有很大的惯性。因此，他们需要花很长时间来启动和放慢。

有更好的方法吗？你猜一猜火车会去哪个方向!

如果你猜对了，它就继续前进。
如果你猜错了，车长就会停下来，往后退，并喊你去翻开开关。然后它就可以重新开始走另一条路了。
如果你每次都猜对了，火车就永远不用停下来。
如果你经常猜错，火车就会花很多时间停下来，倒车，再重新启动。

考虑一个if语句。在处理器层面，它是一个分支指令。

包含if语句的编译代码的截图

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

现代处理器很复杂，有很长的流水线。所以它们需要永远 “热身 “和 “减速”。

有更好的方法吗？你猜猜看分支会往哪个方向走!

如果你猜对了，你就继续执行。
如果你猜错了，你需要冲刷管道并回滚到分支上。然后你就可以沿着另一条路径重新开始。
如果你每次都猜对了，那么执行就永远不必停止。
如果你经常猜错，你就会花很多时间来停顿、回滚和重启。

这就是分支预测。我承认这不是最好的比喻，因为火车可以直接用旗子示意方向。但在计算机中，处理器直到最后一刻才知道一个分支会去哪个方向。

那么，你如何从战略上猜测，以尽量减少火车必须倒车和走另一条路的次数？你看一下过去的历史! 如果火车99%的时间都是向左行驶，那么你就猜测向左。如果它交替出现，那么你就交替猜测。如果它每三次都走一条路，你就猜一样的……

换句话说，你试图找出一种模式并持续去遵循它。这或多或少是分支预测器的工作方式。

大多数应用程序都有行为良好的分支。因此，现代分支预测器通常会达到90%以上的命中率。但是，当面对没有可识别模式的不可预测的分支时，分支预测器几乎毫无用处。

进一步阅读。维基百科上的 “分支预测器 “文章。

正如上文所暗示的，罪魁祸首是这个if-statement。

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, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T  ...

       = TTNTTTTNTNNTTT ...   (completely random - impossible to predict)
复制代码

那么，我们可以做什么呢？

如果编译器不能将分支优化为条件移动，如果你愿意为性能牺牲可读性，你可以尝试一些小技巧。

替换

if (data[c] >= 128)
    sum += data[c];
复制代码

和

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

这就取消了分支，而用一些位操作来代替它。

(注意，这个黑客并不严格等同于原始的if语句。但在这种情况下，它对data[]的所有输入值都有效）。)

基准测试 Core i7 920 @ 3.5 GHz

C++ – Visual Studio 2010 – x64 版本

Java – NetBeans 7.1.1 JDK 7 – x64

可以观察到

随着分支的出现，排序后的数据和未排序的数据之间存在巨大差异
使用Hack：排序后的数据和未排序的数据之间没有区别
在C++情况下，当数据被排序时，Hack实际上比使用分支的速度要慢一点
一般的经验法则是避免在关键循环中进行数据依赖性的分支（比如在这个例子中）。

更新

在x64上使用-O3或-ftree-vectorize的GCC 4.6.1能够生成一个条件移动；因此，排序后的数据和未排序的数据之间没有区别–两者都很快。

(或者说有点快：对于已经排序的情况，cmov可能更慢，特别是如果GCC把它放在关键路径上，而不是仅仅添加，特别是在Broadwell之前的Intel上，cmov有2个周期的延迟：GCC优化标志-O3使代码比-O2更慢)

即使在/Ox下，VC++ 2010也无法为这个分支生成条件性动作。

英特尔C++编译器（ICC）11做了一些神奇的事情。它将两个循环互换，从而将不可预测的分支吊在外循环上。因此，它不仅对错误预测有免疫力，而且比VC++和GCC所能产生的速度快了一倍！也就是说，ICC利用了错误预测。换句话说，ICC利用了测试循环的优势来打败了基准…

如果你把无分支的代码交给英特尔编译器，它就直接把它矢量化了……而且和有分支的时候一样快（有循环互换）。

这表明，即使是成熟的现代编译器在优化代码的能力上也会有很大的不同……

文章翻译自Stack Overflow :stackoverflow.com/questions/1…