Java-CPU-Branch-Prediction

发表于 更新于 分类于 本文字数： 631 阅读时长 ≈ 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 的元素求和。[1]

见注释结果，排序后的数组执行求和，比不排序的要快的多。这是在执行 if 语句时，CPU 的分支预测导致的。[2]

通过分支的历史选择记录进行分支预测，若预测命中，则指令能快速的执行；若未命中，则当前执行分支作废，转而执行另一分支 (未命中的预测会损耗性能)：[3]

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

无序数组难以保证预测命中率，而有序数组则极好判断。[4]

也可通过位运算优化，消除分支判断。[5]

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

  1. JLS SE 21, §15.17.3 Remainder Operator, defines Java % as remainder rather than mathematical modulo; Oracle Java SE 21 Random.nextInt(int bound) is the API to generate a bounded [0, bound) integer when that is the intended data range. ↩︎

  2. The Stack Overflow example “Why is processing a sorted array faster than processing an unsorted array?” is the demonstration source; Intel’s Optimization Reference Manual is the primary vendor source for branch-prediction performance behavior. ↩︎

  3. Intel’s Optimization Reference Manual describes branch prediction as a processor optimization and treats mispredicted branches as a performance cost in hot code. ↩︎

  4. Intel’s Optimization Reference Manual supports the general claim that predictable branch behavior is easier for the processor than irregular branch behavior; exact results depend on CPU, JVM, data shape, and benchmark method. ↩︎

  5. JLS SE 21, §15.19 Shift Operators, defines signed right-shift behavior; branchless arithmetic or bit tricks should still be verified with JMH or equivalent benchmarking before being treated as an optimization. ↩︎