堆结构中线性搜索indexOf为何比树遍历indexOfSlow快17倍？

我在测试自定义Heap类时发现，indexOfSlow方法的比较次数更少，但运行速度却比indexOf慢约17倍。我猜测这是因为indexOf采用顺序数组访问，有缓存优势，但想知道确切原因。

测试性能数据 #

注：Java的PriorityQueue.indexOf()与本文的indexOf类似，不会像indexOfSlow那样通过树遍历提前终止搜索。

完整代码 #

class Heap<T extends Comparable<T>> {

    public static void main(String[] args) {
        int elementCount = 50_000;

        final List<Integer> elements = new ArrayList<>(elementCount);
        for (int i = 0; i < elementCount; i++)
            elements.add(i);

        for (int j = 0; j < 3; j++) {
            final var heap = new Heap<Integer>();
            for (int i : elements)
                heap.add(i);
            assert heap.peek() == 0;
            final long nanoBefore = System.nanoTime();
            for (int i = elementCount; i > 0; i--)
                heap.indexOf(i - 1);
//                heap.indexOfSlow(i - 1);
            final long nanoAfter = System.nanoTime();
            if (j > 0) // 第一轮作为预热，丢弃结果
                System.out.println("耗时: " + (nanoAfter - nanoBefore) / 1_000_000 + " 毫秒");
        }
    }

    private final ArrayList<T> list = new ArrayList<>();

    public T peek() {
        return list.isEmpty() ? null : list.get(0);
    }

    private void siftUp(int i, T value) {
        while (i > 0) {
            int parentI = (i - 1) / 2;
            final T parentValue = list.get(parentI);
            if (parentValue.compareTo(value) <= 0)
                return;
            list.set(parentI, value);
            list.set(i, parentValue);
            i = parentI;
        }
    }

    public void add(T value) {
        list.add(value);
        siftUp(list.size() - 1, value);
    }

    public int indexOf(T value) {
        final int size = list.size();
        if (size > 0) {
            for (int i = 0; i < list.size(); i++) {
                if (value.compareTo(list.get(i)) == 0)
                    return i;
            }
        }
        return -1;
    }

    public int indexOfSlow(T value) {
        final int size = list.size();
        if (size > 0) {
            Queue<Integer> childrenToVisit = new LinkedList<>();
            childrenToVisit.add(0);
            while (!childrenToVisit.isEmpty()) {
                int i = childrenToVisit.poll();
                final int cmp = list.get(i).compareTo(value);
                if (cmp == 0)
                    return i;
                if (cmp > 0)
                    continue;
                int rightChildIdx = (i + 1) * 2;
                int leftChildIdx = rightChildIdx - 1;
                if (leftChildIdx < size)
                    childrenToVisit.add(leftChildIdx);
                if (rightChildIdx < size)
                    childrenToVisit.add(rightChildIdx);
            }
        }
        return -1;
    }

}

性能差异的核心原因 #

1. CPU缓存命中率的巨大差距 #

indexOf是顺序遍历数组，ArrayList底层是连续内存的数组。CPU读取数组元素时会触发预取机制：读取list.get(i)时，会把i附近的连续内存块加载到L1/L2缓存中，后续访问i+1、i+2时数据已在缓存，无需从主存读取，速度极快。

而indexOfSlow是树的广度优先遍历，访问的数组索引是跳跃式的（比如0→1→2→3→4→6→7...），完全不连续。每次访问list.get(i)时，目标数据大概率不在缓存中，需要从主存加载——主存访问速度比L1缓存慢几百倍，这是性能差距的主要来源。

2. 额外的对象开销与操作复杂度 #

indexOfSlow依赖LinkedList存储待访问节点索引，每次poll()和add()都涉及链表节点的创建、指针操作，带来额外的对象分配和GC压力，以及更多指令执行开销。而indexOf只是简单循环和数组访问，无额外对象操作。

3. 比较次数的“假象” #

虽然indexOfSlow比较次数更少，但每次比较的前置成本（缓存未命中、队列操作）远高于indexOf。CPU执行缓存命中的数组访问+比较，比缓存未命中的访问+队列操作快得多，总耗时反而更低。

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