关于局部性原理

发表于 更新于 分类于

因为之前一直在关注『码农翻身』公众号，作者以很基础的文字构建关于计算机关于编程的小故事，由浅入深，，其中的知识点可以自己延伸阅读，还是非常不错的，很适合入门~后来，作者出书了，支持了一波，，毕竟纸质书翻起来比较方便。
OK，进入正题，，在『CPU阿甘』中有提到『局部性原理』，，有必要延伸阅读下。网上找到了Stack Overflow中一篇文章-Why is it faster to process a sorted array than an unsorted array?-本文是对这篇文章的简单翻译，四级水平，还请多包涵 哈哈。

为什么排序后的数组比乱序的数组执行起来要快？

这是一段看起来非常奇怪的C++代码，因为某些原因，将数组排序之后奇迹般的将运行速度提高了将近六倍。

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
31
32
#include <algorithm>
#include <ctime>
#include <iostream>

int main(){
    // 生成数据(数组)
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! 因为这一行代码，下边的循环运行的更快了
    std::sort(data, data + arraySize);

    // 测试
    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
31
32
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);
    }
}

运行结果有点类似，但没有像在C++中差很多。

我刚开始想到的是把数组排序之后，将数组载入到内存中了，，转念一想，这忒蠢了，数组明明是刚生成的(一直在内存中)。

  • 到底发生了神马？
  • 为什么排序后的数组比乱序时处理速度快很多？
  • 代码中求和项是相对独立的，应该跟数组数据没什么关系。。(存疑)

高票回答

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

那么什么是分支预测呢？？

想象铁路的岔口，，👇
railroad junction
@(Image by Mecanismo, via Wikimedia Commons. Used under the CC-By-SA 3.0 license.)

现在为了方便讨论，假想我们回到了19世纪，那时候还无法进行远距离无线通讯。

你作为这个岔路口的操作员，听到一辆货车正在驶来，但又完全不知道它想去哪条分支路线。这时，你示意货车停下来，问他你想去哪个方向，然后将开关设置为正确的位置。

火车很笨重，因为惯性的原因，它们在启动和停下来的时候通常要花很长时间。

有没有更好的办法嗫？(办法是)猜测它会去往哪个方向！

  • 如果你猜对了，它继续行驶~
  • 如果你猜错了，火车司机会向你大喊大叫，让你重置开关，，然后TA重新启动，驶向另一方向。

如果你每次都猜对，火车就永远不需要停下来~
如果你总是都猜错，火车会花费很长时间停下来，后退，重新启动。。

把它看做一个 if 代码块：在芯片级别，这是一个分支指令👇
if-statement
作为一个处理器，你看到一个分支结构，，完全不知道它将要怎么运行？你怎么做？等判断条件先运行结束，然后根据正确的结果选择合适的分支运行。

现代处理器(通常)很复杂，有很长的流水线级数。所以，会像火车一样话很长的时间『启动』和『刹车』。

有没有更好的办法嗫？(答案是)猜测程序会运行哪个分支的代码。

  • 如果猜对了，程序继续执行~
  • 如果猜错了，需要清空流水线(的所有任务)，回滚到分支结构开始的位置。然后重新启动执行另一个分支。

如果每次都猜对，你永远不需要被迫停下~
如果总是猜错，你会花费很长时间减速，回滚，重启。。

这就是分支预测，，我承认这不是最好的比喻，因为火车可以用旗子作为指示方向的信号。但是在计算机中，处理器直到最后一刻才知道最终会运行哪个分支(的代码)。

那么，你如何策略性地猜测，以尽量减少火车必须后退才能才能驶向正确的方向的次数？观察过去的执行历史！如果99%的情况，火车都向驶向左侧，那么你(肯定)猜测(下一次)火车(同样)驶向左侧。如果它(驶向左侧或者右侧的情况)交替出现，那么你(根据情况)交替改变你的猜测。如果每三次就会驶向某一特定的方向，那么你也会据此作出合理的猜测..

换句话说，你试图抽象出一个模型并据此作出猜测。这或多或少是分支预测器的工作原理。

大多数应用程序具有良好表现(well-behaved 具体指什么??)的分支。所以现代分支预测器通常会达到大于90％的命中率。但是当面对不可识别的模型时，我们无法预测将要执行的分支，这时分支预测器实际上是毫无用处的。

正如上边我们猜测的那样，罪魁祸首是这个if代码块👇

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

我们可以注意到，数据均匀分布在0和255之间。数组中的所有元素排序之后，大致前半部分元素迭代时不会进入if语句。剩下后半部分的元素，它们将全部进入if语句。

分支连续多次走向相同的方向时，这对于分支预测器非常友好。即使是简单的饱和计数器也能正确预测分支，除了饱和后改变方向后的少数迭代。

快速预览：

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

那么，我们能做些什么呢？

如果编译器无法将分支优化为条件转移(conditional move???)，那么如果您愿意为了提高性能而牺牲可读性，则可以尝试一些风骚的操作。
👇

1
2
3
4
5
6
7
if (data[c] >= 128)
    sum += data[c];
    
// 将上面👆的代码修改为下面👇的，，

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

这样，用一些位操作代替分支(判断)。
(PS:需要注意的是，这种风骚的操作并不完全等同于原始的if语句。但在这个例子中，它对数据的所有输入值都有效[])。

基于: Core i7 920 @ 3.5 GHz

C++ - Visual Studio 2010 - x64 Release 👇

1
2
3
4
5
6
7
8
9
10
11
//  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

1
2
3
4
5
6
7
8
9
10
11
//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823
  • 分支：排序后的数组与乱序的数组之间(执行速度)有巨大的差异。
  • 风骚の操作：排序后的数组与乱序的数组之间(执行速度)无明显差异。
  • 在C++中，排序后的数组用风骚的位操作甚至比分支预测有些慢。。

一般情况下应该避免 data-dependent branching in critical loops. (such as in this example)