LOCATINO'S NOTE
0%

Stack Overflow经典问题选讲(1)

發表於 更新於 分類於

##Question##
下面是一段非常神奇的**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
33
34
35
#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
31
32
33
34
35
36
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);
}
}

结果也类似，只不过速度差异没有那么夸张。
我最初以为是因为排序把数据带入了高速缓存里，但马上就发现这个想法多么愚蠢，因为数组是运行时生成的。

  • 发生了什么事？
  • 为什么排序后的数组比没有排序的数组处理起来快？
  • 代码仅仅把数据元素单独的相加，数据元的顺序应该没有影响才对。

##Answer## 你是[分支预测](https://en.wikipedia.org/wiki/Branch_predictor)(branch prediction)失败的受害者。

##什么是分支预测？##
请参考下图铁轨分岔路：
train_pic
为了方便说明这个程序问题，假设我们回到了1800年代——在无线电或者其他长距离通信方式发明之前。
你是一名操作员，你听到了一辆火车正在驶来。你不知道它要走哪个方向。你停下了火车去问列车长他要走哪个方向。然后你正确地设置了分岔口的开关。


火车重，并且惯性大。所以它们启动和停下需要花费大量的时间。


那有没有更好的方式？你来猜火车会走哪条路！

  • 如果你猜对了，火车就继续走。
  • 如果你猜错了，那列车长会停车，退回，训斥你重新操作分岔开关。然后火车重新驶向另一条路。

如果你每次都猜对，火车将永远不用停下来。

如果你老是猜错，火车将会花费大量的时间停下来，退回，重启。

观察下列if语句：在处理器层面上，它是一条分支指令：
branch_instruction
假设你是一个处理器并且你发现了一个分支指令。你不知道接下来会执行哪条指令。你怎么办？你挂起了程序，等待之前的指令执行完毕。然后你顺着正确的分支继续执行。


现代处理器结构复杂并且拥有长流水线。所以它们启动和停止需要花费大量的时间。


那有没有更好的方式？你来猜接下来会执行哪条分支！

  • 如果你猜对了，你就继续执行。
  • 如果你猜错了，你需要刷新指令流水线并回退到分支语句。然后你重新执行正确地分支。

如果你每次都猜对，执行将永远不用停止。
如果你老是猜错，你将花费大量的时间停止，回退，重启。

这就是分支预测。我承认上面的比喻不是最合适的，因为火车只需要打一面标识行进方向的旗子就可以了。但是计算机里，处理器不到最后一刻是不会知道该进入哪条分支的。
所以你该如何选择猜测方案来最小化火车回退重启的次数呢？你观察之前的历史！如果火车99%的情况下走左边，那么你就猜左。反之，你就猜右。如果它每三次就走其中某个特定的方向，你就猜它接下来也是这样……
换句话说，你试图找出一个模式并遵循它。这差不多就是分支预测器的工作方式。
大部分应用都有可良好预测的分支。所以现代分支预测器差不多可以达到>90%的命中率。但是当面临无可预测的分支并且毫无规律可循的情况下，分支预测器基本上形同虚设。

深入阅读：“Branch predictor” article on Wikipedia。

##根据以上所说，罪魁祸首就是这条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)

###所以应该如何是好？###
如果编译器没法把分支优化成可良好预测，你可以用一些技巧优化，如果你愿意为性能牺牲可读性的话。
将：

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

替换为：

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

这样就用一些位操作消除了分支。（上述方法并不等价于原来的if语句。仅仅是在这个例子中跟原来的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++时，消除分支语句的执行速度是比使用分支处理排序后的数据的速度慢一点的。

所以一般的最佳做法是避免在重要的循环中使用依赖数据特性的分支。