这是一段看似非常特殊的 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)
{
// 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 秒。起先我以为是语言或者编译器有什么特殊的,所以我用 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);
}
}
结果和 C++ 版本类似,只是快慢差距不那么悬殊。
一开始我以为是因为排序导致数据被缓存,但后来我意识到这是不对的,因为数组是刚刚生成的。
你是分支预测失败的受害者。
这是一个铁路岔口:
图片来自 Mecanismo,来自 Wikimedia Commons。在CC-By-SA 3.0许可下使用。
为了讨论背景,我们假设这是在 19 世纪 - 在无线通信发明之前。
你是个搬岔工,听到火车即将到来。你不知道这趟车应该走哪条路,所以你停下火车去询问司机他们想要的方向。然后正确地进行搬岔。
火车很重,惯性大。所以他们启动和停下需要较长时间。
有没有更好的办法?我想那就是由你来猜火车往哪个方向走并搬岔!
如果你每次都能猜对 ,火车就永远不会停下来。
如果您经常猜错
,火车将花费大量时间停止,后退和重启。
考虑一个 if 语句:在处理器级别,它是一条分支指令:
假设你是处理器,你看到了一个分支。你不知道它会走哪条路径。这是要怎么做呢?你会暂停执行并等待前面的指令完成。然后继续沿着正确的路径前进。
现代处理器很复杂,管道很长。所以他们 “热身” 和 “慢下来” 需要较长时间。
有没有更好的办法?那就是你来猜分支的方向!
如果你每次都能猜对,执行就可以永远不会停止。
如果你经常猜错 ,你会花很多时间停止,回滚和重启。
这就是分支预测。我承认这不是最好的类比,因为火车可以用旗帜向方向发出信号。但是在计算机中,处理器直到最后一刻才知道分支将朝哪个方向发展。
要怎样猜测才能尽量减少回滚重启次数呢?可以看看过去的历史!如果火车 99% 都往左开,那这次也一样猜左边。如果历史上是交替着开,那么这次也按交替来猜。如果它每 3 次走一条路,你就猜相同......
换句话说,你可以尝试识别模式并按照这个模式的规律来猜。这基本就是分支预测器的工作方式。
大多数应用程序具有表现良好的分支。因此,现代分支预测器通常会达到 >90% 的命中率。但是当面对不可预测的分支也没有可识别的模式时,分支预测器实际上是无用的。
进一步阅读: 维基百科上的 “分支预测” 一文 。
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, 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[c] >= 128)
sum += data[c];
为:
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
这个优化通过位操作来消除了分支。
(注意,这个优化并不完全等同于原始的 if 语句。但在这种情况下,它对data[]
所有输入值都有效。)
基准测试:酷睿 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
观察:
一般的经验法则是避免在关键循环中依赖数据进行分支。(例如本示例)
更新:
在 x64 上使用-O3
或-ftree-vectorize
GCC 4.6.1 能够生成条件移动。因此,排序和未排序数据之间没有区别 - 两者都很快。
即使在/Ox
下,VC ++ 2010 也无法为此分支生成条件移动。
英特尔编译器 11 (Intel Compiler 11)做了一些神奇的优化。它会进行循环交换 ,从而将不可预测的分支提升到外循环。因此,它不仅能够免受错误预测的影响,而且速度也是 VC++ 和 GCC 速度的两倍!换句话说,ICC 利用测试循环来击败基准......
如果你给英特尔编译器提供无分支代码,那么它将向右矢量化…… 并且与分支一样快(通过循环交换)。
这说明即使是成熟的现代编译器,在优化代码的能力方面也会有很大差异……