Java调用Arrays.sort后无关业务逻辑性能骤降问题排查

复现环境 #

• JDK版本：Java 8、Java 17均可稳定复现
• 硬件环境：英特尔11代处理器
• 其他验证环境：在线编译器同样可复现问题

复现代码 #

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class DistanceYandex{
    static class Elem implements Comparable<Elem>{
        int value;
        int index;
        long dist;
        public Elem(int value, int index){
            this.value = value;
            this.index = index;
        }

        @Override
        public int compareTo(Elem o){
            return Integer.compare(value, o.value);
        }
    }
    public static void main(String[] args){
        int n = 300_000;
        int k = 3_000;
        Elem[] elems = new Elem[n];
        for(int i = 0; i < n; i++){
            elems[i] = new Elem(ThreadLocalRandom.current().nextInt(), i);
        }
        solve(n, k, elems);
    }
    private static void solve(int n, int k, Elem[] elems){
        Arrays.sort(elems); // 影响性能的关键行
        long time = System.nanoTime();

        for(int i = 0; i < n; i++){
            elems[i].dist = findDistForIth(elems, i, k);
        }
        // 此处省略输出逻辑，与问题无关
        // Arrays.sort(elems, Comparator.comparingInt(elem -> elem.index));
        // System.out.print(elems[0].dist);
        // for(int i = 1; i < n; i++){
        //     System.out.print(" " + elems[i].dist);
        // }
        System.out.println((System.nanoTime() - time)/1_000_000_000.0);
    }

    private static long findDistForIth(Elem[] elems, int i, int k){
        int midElem = elems[i].value;
        int left = i - 1;
        int right = i + 1;
        long dist = 0;
        for(int j = 0; j < k; j++){
            if(left < 0){
                dist += elems[right++].value - midElem;
            }else if(right >= elems.length){
                dist += midElem - elems[left--].value;
            }else{
                int leftAdd = midElem - elems[left].value;
                int rightAdd = elems[right].value - midElem;
                if(leftAdd < rightAdd){
                    dist+=leftAdd;
                    left--;
                }else{
                    dist+=rightAdd;
                    right++;
                }
            }
        }
        return dist;
    }
}

异常现象 #

solve方法逻辑如下：

1. 首先调用Arrays.sort(elems)对Elem数组按value字段自然排序
2. 排序完成后才通过System.nanoTime()启动计时，计时范围仅包含后续循环调用findDistForIth为每个元素计算dist值的逻辑，完全不包含Arrays.sort本身的执行耗时
3. findDistForIth方法的执行逻辑不依赖数组是否有序，绝大多数分支都会进入第三个else分支

实际测试出现反常结果：注释掉Arrays.sort(elems)这行代码后，计时区间的执行耗时从约7.3秒降低到约1.6秒，性能差距超过4倍。

已尝试的无效排查手段 #

• 配置JVM启动参数-Xmx2048M -Xms2048M将堆内存固定为2G，排除GC干扰，未生效
• 移除Elem类对Comparable接口的实现，为Arrays.sort传入显式比较器Comparator.comparingInt(e -> e.value)，未生效
• 使用IntelliJ Profiler进行性能采样，未获得有效定位信息
• 将代码打包为jar包通过命令行直接启动，排除IDEA运行环境干扰，未生效

根本原因 #

这个性能差异来自CPU缓存的空间局部性失效：

• 未执行排序时，数组中存储的Elem对象引用顺序和对象实际创建顺序一致。循环new Elem时，对象在堆内存中大概率是连续分配的，遍历访问相邻数组元素对应的Elem对象时，访问的内存地址也是连续的，CPU缓存预取命中率极高，访问速度快。
• 执行Arrays.sort时，排序操作仅重排了数组中存储的对象引用，不会移动堆中实际的Elem对象。排序后数组中的引用顺序被打乱，后续遍历访问相邻数组元素时，对应的Elem对象在堆内存中的地址是随机跳跃的，CPU缓存预取完全失效，大量缓存未命中导致访存延迟暴涨，最终性能下降4倍以上。

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