为何二叉堆插入及PriorityQueue的offer()随容量增大执行更快？

我用Java实现了最小堆，测试插入操作时间复杂度时发现反常现象：堆越大，插入操作反而越快，哪怕此时上浮交换的次数更多。一开始怀疑是自己实现有bug，换成JCF的PriorityQueue测试，结果完全一致——PriorityQueue.offer()方法居然也随队列容量增大执行更快。

我的测试代码如下：

public static void main(String[] args) {
    PriorityQueue<Double> p = new PriorityQueue<>(200000000); //capacity: 200 Million
    
    int n = 100000000;
    for(int i = 0; i < n; i++){
        p.offer(100 + Math.random() * 10000);
    }
        
    int numOfInsertions = 5;
    long start = System.nanoTime();
    
    p.offer(Math.random() * 100); //inserted elements are less than all elements
    p.offer(Math.random() * 100);//in the heap, to ensure a full swim all the way up
    p.offer(Math.random() * 100);//to the root
    p.offer(Math.random() * 100);
    p.offer(Math.random() * 100);
    
    long end = System.nanoTime();
    
    System.out.println((end - start)/numOfInsertions);
    
    System.out.println(p.peek()); //ensure that the elements less than 100
                                  //were inserted
}

问题根源：CPU缓存命中率的影响 #

这种和理论时间复杂度相悖的现象，核心原因是CPU缓存机制：

• 当堆规模较小时，堆数组的内存还未被加载到CPU的L1/L2高速缓存中，上浮过程中每次访问父节点都要从主存读取，速度极慢。
• 当堆增大到一定程度后，堆数组的大部分数据已经被缓存到CPU高速缓存里，此时访问数组元素的速度是主存的几十到上百倍。哪怕上浮交换的次数更多，缓存带来的性能提升完全覆盖了交换的开销，最终整体执行速度更快。

测试代码的优化建议 #

• 测试样本量太小：仅5次插入的计时结果随机性极强，建议增加到十万甚至百万次插入，取多次测试的平均值。
• 测试场景单一：插入的元素都是远小于堆中所有元素，只会触发最坏情况的上浮操作，无法代表实际场景中随机插入的平均情况。
• 未覆盖扩容场景：初始化时指定了超大容量，避免了PriorityQueue的扩容开销，但实际使用中扩容会带来额外的数组复制时间，建议测试不同初始容量下的性能。

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