ArrayList<Int>与IntArray并行快排性能差异：1e8元素时并行变慢原因

核心原因分析 #

这种性能反转的现象，本质是小数据量下被掩盖的ArrayList开销（装箱拆箱、内存冗余）在1e8规模时被指数级放大，加上并行场景的特有开销（缓存颠簸、GC压力、任务调度）共同作用的结果，具体拆解如下：

• 内存冗余引发的缓存命中率暴跌
  ArrayList存储的是Integer对象引用，而非直接的基本类型int。以64位JVM为例，单个Integer对象至少占用16字节（对象头）+4字节int值，再加上数组中8字节的引用，单元素总内存开销达28字节；而IntArray（等价于int[]）单元素仅占4字节。1e8个元素时，ArrayList的内存占用是IntArray的7倍左右，远超CPU L3缓存容量（通常几十到上百MB）。
  并行排序时，4个线程同时访问分散的内存区域，会导致严重的缓存颠簸：线程之间频繁抢占缓存行，缓存失效次数剧增，内存访问延迟飙升。而顺序排序的单线程内存访问模式更连续，缓存命中率相对更高，两者的性能差距因此反转。

• 装箱拆箱与GC压力的并行放大
  小数据量时，装箱拆箱的CPU开销占排序总开销的比例极低，并行带来的计算加速足以覆盖这部分成本。但1e8规模下，装箱拆箱的总操作量达到亿级，会产生大量临时Integer对象，触发频繁的Full GC。
  GC的Stop-The-World（STW）阶段会暂停所有线程，并行版本因4个线程同时运行，STW造成的总停顿时间是单线程的数倍；而顺序版本仅单个线程受影响，GC的相对开销更低。同时，多线程并发创建/回收对象还会加剧堆内存碎片化，进一步降低GC效率。

• ForkJoin任务调度的边际成本上升
  并行快排依赖ForkJoinPool拆分大量子任务，小数据量时任务调度的开销可以忽略。但1e8规模下，子任务数量指数级增长，每个任务处理ArrayList元素的操作成本（对象引用访问、拆箱）本身就高，调度开销的占比随之上升。当调度+内存访问的总开销超过并行带来的计算收益时，并行版本就会比顺序版本更慢。

补充验证方向 #

如果想进一步验证结论，可以：

• 监控1e8规模下ArrayList版本的GC日志，查看Full GC的频率和停顿时间
• 对比两种数据结构的内存占用（用Runtime.getRuntime()统计）
• 调整ForkJoinPool的线程数（比如2线程），观察是否能缓解性能反转情况

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