关于局部性原理
因为之前一直在关注『码农翻身』公众号,作者以很基础的文字构建关于计算机关于编程的小故事,由浅入深,,其中的知识点可以自己延伸阅读,还是非常不错的,很适合入门~后来,作者出书了,支持了一波,,毕竟纸质书翻起来比较方便。
OK,进入正题,,在『CPU阿甘』中有提到『局部性原理』,,有必要延伸阅读下。网上找到了Stack Overflow中一篇文章-Why is it faster to process a sorted array than an unsorted array?-本文是对这篇文章的简单翻译,四级水平,还请多包涵 哈哈。
为什么排序后的数组比乱序的数组执行起来要快?
这是一段看起来非常奇怪的C++代码,因为某些原因,将数组排序之后奇迹般的将运行速度提高了将近六倍。
1 | #include <algorithm> |
- 如果没有
std::sort(data, data + arraySize);
(即数组数据大小乱序), 代码运行11.54秒。 - 数组元素排序之后,运行只用了1.93秒。
起初,我以为这种现象与编程语言或者编译器什么的有关系,,所以,我把代码移植到Java中试了一下👇
1 | import java.util.Arrays; |
运行结果有点类似,但没有像在C++中差很多。
我刚开始想到的是把数组排序之后,将数组载入到内存中了,,转念一想,这忒蠢了,数组明明是刚生成的(一直在内存中)。
- 到底发生了神马?
- 为什么排序后的数组比乱序时处理速度快很多?
- 代码中求和项是相对独立的,应该跟数组数据没什么关系。。(存疑)
高票回答
你可能是分支预测失败的受害者。。
那么什么是分支预测呢??
想象铁路的岔口,,👇
@(Image by Mecanismo, via Wikimedia Commons. Used under the CC-By-SA 3.0 license.)
现在为了方便讨论,假想我们回到了19世纪,那时候还无法进行远距离无线通讯。
你作为这个岔路口的操作员,听到一辆货车正在驶来,但又完全不知道它想去哪条分支路线。这时,你示意货车停下来,问他你想去哪个方向,然后将开关设置为正确的位置。
火车很笨重,因为惯性的原因,它们在启动和停下来的时候通常要花很长时间。
有没有更好的办法嗫?(办法是)猜测它会去往哪个方向!
- 如果你猜对了,它继续行驶~
- 如果你猜错了,火车司机会向你大喊大叫,让你重置开关,,然后TA重新启动,驶向另一方向。
如果你每次都猜对,火车就永远不需要停下来~
如果你总是都猜错,火车会花费很长时间停下来,后退,重新启动。。
把它看做一个 if 代码块:在芯片级别,这是一个分支指令👇
作为一个处理器,你看到一个分支结构,,完全不知道它将要怎么运行?你怎么做?等判断条件先运行结束,然后根据正确的结果选择合适的分支运行。
现代处理器(通常)很复杂,有很长的流水线级数。所以,会像火车一样话很长的时间『启动』和『刹车』。
有没有更好的办法嗫?(答案是)猜测程序会运行哪个分支的代码。
- 如果猜对了,程序继续执行~
- 如果猜错了,需要清空流水线(的所有任务),回滚到分支结构开始的位置。然后重新启动执行另一个分支。
如果每次都猜对,你永远不需要被迫停下~
如果总是猜错,你会花费很长时间减速,回滚,重启。。
这就是分支预测,,我承认这不是最好的比喻,因为火车可以用旗子作为指示方向的信号。但是在计算机中,处理器直到最后一刻才知道最终会运行哪个分支(的代码)。
那么,你如何策略性地猜测,以尽量减少火车必须后退才能才能驶向正确的方向的次数?观察过去的执行历史!如果99%的情况,火车都向驶向左侧,那么你(肯定)猜测(下一次)火车(同样)驶向左侧。如果它(驶向左侧或者右侧的情况)交替出现,那么你(根据情况)交替改变你的猜测。如果每三次就会驶向某一特定的方向,那么你也会据此作出合理的猜测..
换句话说,你试图抽象出一个模型并据此作出猜测。这或多或少是分支预测器的工作原理。
大多数应用程序具有良好表现(well-behaved 具体指什么??)的分支。所以现代分支预测器通常会达到大于90%的命中率。但是当面对不可识别的模型时,我们无法预测将要执行的分支,这时分支预测器实际上是毫无用处的。
正如上边我们猜测的那样,罪魁祸首是这个if代码块👇
1 | if (data[c] >= 128) |
我们可以注意到,数据均匀分布在0和255之间。数组中的所有元素排序之后,大致前半部分元素迭代时不会进入if语句。剩下后半部分的元素,它们将全部进入if语句。
分支连续多次走向相同的方向时,这对于分支预测器非常友好。即使是简单的饱和计数器也能正确预测分支,除了饱和后改变方向后的少数迭代。
快速预览:
1 | T = branch taken |
但是,当数据是完全随机的时,分支预测器将无法发挥作用,因为它无法预测随机数据。因此,可能会有大约50%的预测失误。(比随机乱猜好不到哪而去..)。
1 | data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ... |
那么,我们能做些什么呢?
如果编译器无法将分支优化为条件转移(conditional move???),那么如果您愿意为了提高性能而牺牲可读性,则可以尝试一些风骚的操作。
👇
1 | if (data[c] >= 128) |
这样,用一些位操作代替分支(判断)。
(PS:需要注意的是,这种风骚的操作并不完全等同于原始的if语句。但在这个例子中,它对数据的所有输入值都有效[])。
基于: Core i7 920 @ 3.5 GHz
C++ - Visual Studio 2010 - x64 Release 👇
1 | // Branch - Random |
Java - Netbeans 7.1.1 JDK 7 - x64
1 | // Branch - Random |
- 分支:排序后的数组与乱序的数组之间(执行速度)有巨大的差异。
- 风骚の操作:排序后的数组与乱序的数组之间(执行速度)无明显差异。
- 在C++中,排序后的数组用风骚的位操作甚至比分支预测有些慢。。
一般情况下应该避免 data-dependent branching in critical loops. (such as in this example)