为什么排序数组处理更快？Java 解释

引言：引爆 Stack Overflow 的悖论

想象一下：你编写一个简单的 Java 循环，根据条件（例如，如果数字大于 128）对数组元素求和。你在排序数组上运行代码——它比在未排序数组上运行快 2-3 倍。听起来像魔法？实际上这不是魔法，而是 branch prediction（分支预测）——现代处理器的关键特性之一。

“为什么对排序数组的条件处理比未排序数组更快？” 这个问题在 Stack Overflow 上获得了超过 3 万票，并成为学习底层优化的经典案例。在本文中，我们不仅会分析理论，还会编写真实的 Java 代码，亲眼目睹这一效果。更重要的是，你将学会如何在实践中运用这一知识。

如果你想更深入地理解 Java 代码优化 的工作原理，以及为什么 分支预测 既能加速也能拖慢你的程序——你来对地方了。

1. 实验：揭示一切的代码

我们从简单的 Java 应用程序开始。我们将创建两个数组：一个已排序，另一个随机。然后遍历每个数组，计算大于阈值（例如 128）的元素之和。测量执行时间。

import java.util.Arrays;\nimport java.util.Random;\n\npublic class BranchPredictionDemo {\n    private static final int SIZE = 100_000;\n    private static final int THRESHOLD = 128;\n\n    public static void main(String[] args) {\n        // 创建未排序数组\n        int[] unsorted = new int[SIZE];\n        Random rand = new Random();\n        for (int i = 0; i < SIZE; i++) {\n            unsorted[i] = rand.nextInt(256); // 0..255\n        }\n\n        // 创建排序数组（复制并排序）\n        int[] sorted = unsorted.clone();\n        Arrays.sort(sorted);\n\n        // 测量未排序数组的时间\n        long start = System.nanoTime();\n        long sumUnsorted = processArray(unsorted);\n        long end = System.nanoTime();\n        System.out.println("未排序: " + (end - start) / 1_000_000 + " ms, 总和 = " + sumUnsorted);\n\n        // 测量排序数组的时间\n        start = System.nanoTime();\n        long sumSorted = processArray(sorted);\n        end = System.nanoTime();\n        System.out.println("排序: " + (end - start) / 1_000_000 + " ms, 总和 = " + sumSorted);\n    }\n\n    private static long processArray(int[] arr) {\n        long sum = 0;\n        for (int i = 0; i < arr.length; i++) {\n            if (arr[i] >= THRESHOLD) {\n                sum += arr[i];\n            }\n        }\n        return sum;\n    }\n}\n

在我的笔记本电脑（Intel i7, Java 17）上的结果：

\n
• 未排序数组： ~22 ms
\n
• 排序数组： ~8 ms
\n

差距几乎达到 3 倍！为什么？因为操作数量相同。答案在于处理器如何处理条件 if (arr[i] >= THRESHOLD)。

2. 分支预测：处理器的大脑

现代处理器使用流水线架构——它们预测将选择哪条执行路径（分支），并提前开始执行指令。如果预测正确——一切顺利。如果预测错误——流水线被清空，处理器花费时钟周期进行清理。

在排序数组中，值首先长时间小于 128，然后全部大于 128。处理器很快“学会”：如果前 1000 次都是 false，那么下一次很可能也是 false。分支预测几乎完美工作。

在未排序数组中，值随机地高于或低于阈值。处理器在约 50% 的情况下会预测错误，读