为何对已排序ArrayList执行sum()方法比未排序时更快？

初始化代码 #

List<Long> l = new ArrayList<>();
for (long i = 10_000_000; i < 20_000_000; i++) {
    l.add(i);
}

测试代码 #

public class Main {

    public static void main(String[] args) {
        List<Long> l = new ArrayList<>();
        for (long i = 10_000_000; i < 20_000_000; i++) {
            l.add(i);
        }

        System.out.println(sum(l));

        Collections.shuffle(l);
        System.out.println(sum(l));

        Collections.sort(l);
        System.out.println(sum(l));
    }

    static long sum(List<Long> l) {
        long started = System.nanoTime();
        long result = 0;
        for (long v : l) {
            result += v;
        }
        System.out.println(" duration: " + (System.nanoTime() - started) / 1_000_000 + "ms");
        return result;
    }

}

测试步骤与结果 #

• 首次在已排序数组上执行sum()：耗时85ms
• 第二次在未排序数组上执行sum()：耗时250ms
• 第三次再次在已排序数组上执行sum()：耗时97ms

原因分析 #

核心差异来自CPU缓存命中率的不同：

1. 首次创建的有序列表中，Long对象是连续创建的，JVM会在堆上为这些对象分配连续的内存空间。遍历列表时，CPU的缓存预取机制会把连续内存中的对象数据提前加载到高速缓存里，后续访问直接从缓存读取，速度极快。
2. 调用Collections.shuffle()打乱列表后，引用指向的Long对象在堆上的内存地址变得分散无序。遍历过程中CPU无法有效预取数据，每次访问都要从速度远慢于缓存的主存读取，导致耗时飙升。
3. 再次排序后，列表中的引用回到了最初的连续顺序，CPU缓存的预取机制重新生效，缓存命中率回升，遍历速度随之变快。

额外补充：如果使用long[]基本类型数组而非List<Long>，排序与未排序的sum速度差异会大幅缩小——因为基本类型数组本身的内存就是连续的，无论是否排序，内存访问模式都更利于缓存命中。

内容的提问来源于stack exchange，提问作者Ignatyo