Java-CPU-Branch-Prediction

发表于 更新于 分类于 本文字数： 448 阅读时长 ≈ 2 分钟 
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
public static void main(String[] args) {
    int arraySize = 1 << 15;
    int[] data = new int[arraySize];
    Random rnd = new Random(0);
    for (int c = 0; c < arraySize; ++c)
        data[c] = rnd.nextInt() % 256;
    
    sum(data, arraySize); // 2_506_570_100 ns
    // The next sum runs faster after sort
    Arrays.sort(data);
    sum(data, arraySize);// _768_923_900 ns
}

public static void sum(int[] array, int arraySize) {
    long start = System.nanoTime();
    long sum = 0;

    for (int i = 0; i < arraySize; ++i) {
        for (int j = 0; j < arraySize; ++j) {
            if (array[j] >= 128)
                sum += array[j];
        }
    }
    System.out.println(System.nanoTime() - start + " ns");
    System.out.println("sum : " + sum);
}

以上的示例初始化一个数组，以 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * no if statement in this method
 * use shift operators
 * if positive num : num >> 31 == 0
 * if negative num : num >> 31 == -1
 * ~0 = -1 (ffffffff)
 * ~-1 = 0 (0)
 */
public static void sumAvoidBranchPrediction(int[] array, int arraySize) {
    long start = System.nanoTime();
    long sum = 0;

    for (int i = 0; i < arraySize; ++i) {
        for (int j = 0; j < arraySize; ++j) {
            sum += ~((array[j] - 128) >> 31) & array[j];
        }
    }
    System.out.println(System.nanoTime() - start + " ns"); // _606_267_300 ns
    System.out.println("sum : " + sum);
}

原始地址：

【Java深入学习系列】之CPU的分支预测(Branch Prediction)模型

why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array