1 | public static void main(String[] args) { |
以上的示例初始化一个数组,以 256 的模数进行填充,后对其中大于等于 128 的元素求和。
见注释结果,排序后的数组执行求和,比不排序的要快的多。这是在执行 if 语句时,CPU 的分支预测导致的。
通过分支的历史选择记录进行分支预测,若预测命中,则指令能快速的执行;若未命中,则当前执行分支作废,转而执行另一分支 (未命中的预测会损耗性能):
T : 分支预测命中
F : 分支预测未命中
无序数组:
-248, 7, -14, 241, 15, 112, 88, 246, 152, -200, 31, 180 …
F F F T F F F T T F F T
有序数组:
127, 127, 127, 127, 127, 127, 128, 128, 128, 128, 128, 128 …
F F F F F F T T T T T T
无序数组难以保证预测命中率,而有序数组则极好判断。
也可通过位运算优化,消除分支判断。
1 | /** |
原始地址:
【Java深入学习系列】之CPU的分支预测(Branch Prediction)模型
why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array