处理有序数据比无序的数组要快


系统和算法
作者: 双king
浏览量:2次

为什么处理有序数据比无序的数组要快呢？这个问题在stackoverflow上面有很高的投票数，虽然涉及的原理很基础，但是也有必要翻译一下，看看具体的解释，原文链接

1 问题

下面有一段C++的代码看起来很奇怪，因为一些未知的原因，排序之后的代码速度奇迹般的比没有排序的时候快6倍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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语言又试了一次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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);
    }
}

虽然差距没那么大，但是也是相似的结果（指排序之后变快了）。

我第一感觉是排序之后数据会被加载进缓存，但之后我就觉的这个想法太蠢了，因为数组是刚刚生成的。

发生了什么事情？
为什么排序的数组比没有排序的更快了？
这段代码和任何团队无关，并且顺序也不重要。

2投票数最多的回答

4什么是分支预测
考虑一个铁路的交叉口

tain.jpg

为了避免争吵，我们假设现在是1800年，没有无线电等远程通信技术。你是这个分岔口的管理员，听到有一辆火车要到了，你也不知道火车要去哪条路，你拦停了火车，问了下司机：“你要去哪条路？”，得到回答之后，把铁路扳倒正确的位置。

火车自重很大，惯性也很大，所以停下来和重新启动耗费了很长时间。还有更好的方法吗？比方说先猜一下火车的方向：

如果猜对了，挺好，火车继续走。
如果猜错了，司机会停下来，退回去，你把铁路扳正确了，火车重新启动再继续走。
如果你每次都猜对的话，火车就永远不会停。
如果你猜错的次数很多的话，火车就会频繁的停下、退回去、重新发动。

考虑一个if语句，在CPU这个级别，是这样执行的：

1
2
3
4
5
6
7
8
if(data[c] > 128) {
sum += data[c];
}
movsxd rdx,DWORD PTR [rcx]
cmp edx 128				 ; 00000080H
jl SHORT $LN3@main
add rbx,rdx
$LN3@main:

现在假设你就是CPU，你看到了一个分支，但是不知道该走哪个分支，你该怎么做？你挂起当前操作，等待分支判断的结果，然后再选择正确的分支。现在的CPU是很复杂的，有很长的执行命令管线（这块不知道怎么翻译了，Modern processors are complicated and have long pipelines），所以永远在热身和停止。

还有更好的方法吗？猜一下分支：

如果猜对了，挺好，继续执行。
如果猜错了，CPU刷新执行命令队列，回退到之前的分岔口，然后重新选择正确的分支。
这就是分支预测，我承认这不是最好的策略，因为火车可以发一个信号来指明它的方向，但是对于CPU来说，不到执行的时候，不知道会走哪个分支。所以采取什么样的策略才能使火车回退的可能性降低呢？可以观察下历史的分支选择数据，如果火车有99%的次数都在走左边，那么就猜左边，如果右边概率大，就猜右边，如果两边各3次，一样的道理。

换句话说，你尝试找到一个规律并且按这个规律来猜测，就差不多就是分支预测怎么做的。

现在大多数的应用程序的分支都很有规律，所以分支预测可以工作的很好，猜中的几率大于90%，但是当面对捉摸不透的没有规律的分支的时候，分支预测就没什么用了。

更多请阅读维基百科的分支预测

由此推断，上面的if语句是排序后程序运行更快的原因：

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

我们注意到数据分布在0到255之间，当数据是有序的，大概算一下前半部分都没有满足条件，后面的部分都满足了data[c] > 128的条件，就不判断这个条件了，在这之后，程序都是直接进入到sum+=data[c]。

有序的数据很适合拿来做分支预测因为大部分的情况下都能命中猜测。

1
2
3
4
5
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%会判断错误（根据历史规律猜中的概率差不多是瞎猜了）。

1
2
3
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)

3 我们该怎么办

如果编译器不能做分支预测的优化，我们该怎么办呢？如果我们可以为了性能而牺牲代码的可读性的话，可以尝试以下的优化方法，可以把下面的代码：

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

替换为：

1
2
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

这样就使用位移操作避免了分支判断。

以下是一些测试数据（Benchmarks: Core i7 920 @ 3.5 GHz）：
C++ - Visual Studio 2010 - x64 Release：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//  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++分支预测运行排序数据比第2种去分支优化方法稍微快一点。

有一个第一个要考虑的原则是避免在循环里面写和数据相关的分支判断，就像示例中的代码一样的那种，要避免。

全文完。