CPU分支预测对程序性能的影响
CPU分支预测对程序性能的影响
执行下面这段代码,你会发现排序的数组总是比未排序的数组计算快。
1 | public class BranchPrediction |
原因
出现这种现象的原因是CPU分支预测(可以参考CPU流水线简介一文中分支预测部分)。
注意下面的分支语句:
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, ... |
更多的例子
1 | int Sum(int max) { |
对于不同的条件,我们有下面的统计结果展示了分支预测对执行结果的影响。
Condition | Pattern | Time (ms) |
---|---|---|
(i & 0x80000000) == 0 | TTT… | 322 |
(i & 0xffffffff) == 0 | FFF… | 276 |
(i & 1) == 0 | T/F T/F … | 760 |
(i & 3) == 0 | TFFFTFFF… | 513 |
(i & 2) == 0 | TTFFTTFF… | 1675 |
(i & 4) == 0 | TTTTFFFFTTTTFFFF… | 1275 |
(i & 8) == 0 | 8T 8F 8T 8F … | 752 |
(i & 16) == 0 | 16T 16F 16T 16F … | 490 |
How
- 避免关键循环中依赖于数据的分支。
- 关键循环尽量减少分支判断(过多的分支会影响预测命中率)。
- (如果可以)使用位运算来优化性能,例如:
1 | if (data[c] >= 128) |