为什么处理已排序的数组比未排序的数组*慢*？（Java的ArrayList.indexOf）

Question

标题是参考自为什么处理排序数组比未排序的数组更快？

这也是分支预测效应吗？请注意：在这里，排序数组的处理速度更慢了！！

考虑以下代码：

private static final int LIST_LENGTH = 1000 * 1000;
private static final long SLOW_ITERATION_MILLIS = 1000L * 10L;

@Test
public void testBinarySearch() {
    Random r = new Random(0);
    List<Double> list = new ArrayList<>(LIST_LENGTH);
    for (int i = 0; i < LIST_LENGTH; i++) {
        list.add(r.nextDouble());
    }
    //Collections.sort(list);
    // remove possible artifacts due to the sorting call
    // and rebuild the list from scratch:
    list = new ArrayList<>(list);

    int nIterations = 0;
    long startTime = System.currentTimeMillis();
    do {
        int index = r.nextInt(LIST_LENGTH);
        assertEquals(index, list.indexOf(list.get(index)));
        nIterations++;
    } while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
    long duration = System.currentTimeMillis() - startTime;
    double slowFindsPerSec = (double) nIterations / duration * 1000;
    System.out.println(slowFindsPerSec);

    ...
}

在我的机器上，这将打印出大约720的值。

现在，如果我激活了集合排序调用，该值会降至142。为什么？！

结果是确凿的，如果我增加迭代/时间的数量，它们不会改变。

Java版本是1.8.0_71(Oracle VM, 64位)，运行在Windows 10下，在Eclipse Mars中进行JUnit测试。

更新

似乎与连续内存访问有关(按顺序访问Double对象与随机访问的效果)。对于长度约为10k及以下的数组长度，该效应开始消失。

感谢assylias提供结果：

/**
 * Benchmark                     Mode  Cnt  Score   Error  Units
 * SO35018999.shuffled           avgt   10  8.895 ± 1.534  ms/op
 * SO35018999.sorted             avgt   10  8.093 ± 3.093  ms/op
 * SO35018999.sorted_contiguous  avgt   10  1.665 ± 0.397  ms/op
 * SO35018999.unsorted           avgt   10  2.700 ± 0.302  ms/op
 */

- user1050755

---

可能是 为什么处理已排序的数组比未排序的数组更快？ 的重复问题。 - Iłya Bursov

https://dev59.com/hHRB5IYBdhLWcg3wz6UK - Andy Turner

如果您想得到有意义的结果，请使用适当的基准测试框架（如JMH）重新进行测量。请勿忘记重新校准。 - Clashsoft

即使没有使用JMH，你的测试方法在概念上也存在缺陷。你正在测试各种各样的东西，包括随机数生成器（RNG）、System.currentTimeMillis以及assertEquals。没有预热迭代，通常也没有迭代，你依赖于恒定的时间量，并检查在该时间内完成了多少。很抱歉，但这个测试是无效的。 - Clashsoft

使用jmh获取类似的结果... - assylias

Answer 1

看起来像是缓存/预取效果。

关键在于比较对象(Double)而非基本数据类型(double)。当你在一个线程中分配对象时，它们通常会按顺序在内存中依次分配。因此，当indexOf扫描列表时，它会遍历顺序的内存地址。这对于CPU缓存预取启发式算法非常有利。

但是，当你对列表进行排序后，在平均情况下仍需要执行相同数量的内存查找，但这一次内存访问将是随机的。

更新

这里是基准测试，证明分配对象的顺序很重要。

Benchmark            (generator)  (length)  (postprocess)  Mode  Cnt  Score   Error  Units
ListIndexOf.indexOf       random   1000000           none  avgt   10  1,243 ± 0,031  ms/op
ListIndexOf.indexOf       random   1000000           sort  avgt   10  6,496 ± 0,456  ms/op
ListIndexOf.indexOf       random   1000000        shuffle  avgt   10  6,485 ± 0,412  ms/op
ListIndexOf.indexOf   sequential   1000000           none  avgt   10  1,249 ± 0,053  ms/op
ListIndexOf.indexOf   sequential   1000000           sort  avgt   10  1,247 ± 0,037  ms/op
ListIndexOf.indexOf   sequential   1000000        shuffle  avgt   10  6,579 ± 0,448  ms/op

- apangin

---

如若事实属实，则洗牌而非排序应产生相同结果。 - David Soroko

@DavidSoroko 它确实如此。 - assylias

@DavidSoroko 在基准测试代码的底部，提供了未排序、洗牌、排序和排序连续的完整基准测试结果。 - assylias

@assylias 一个有趣的扩展可以是创建连续的数字（并在此发布生成的代码将使我的答案过时）。 - Marco13

@Marco13 你说得对。我已经用JMH基准测试更新了答案。 - apangin

强调一下，在 list.indexOf(list.get(index)) 中，list.get(index) 不会因为预取而受益，因为 index 是随机的。无论列表是否排序，list.get(index) 的价格都是相同的。预取仅适用于 list.indexOf()。 - David Soroko

Answer 2

我认为我们正在看到内存缓存未命中的影响：

当您创建未排序列表时

for (int i = 0; i < LIST_LENGTH; i++) {
    list.add(r.nextDouble());
}

所有的双倍数很可能被分配在连续的内存区域中。通过迭代这些数，将会产生较少的缓存未命中。

另一方面，在排序列表中，引用以混乱的方式指向内存。

现在，如果您创建一个具有连续内存的已排序列表：

Collection.sort(list);
List<Double> list2 = new ArrayList<>();
for (int i = 0; i < LIST_LENGTH; i++) {
    list2.add(new Double(list.get(i).doubleValue()));
}

这个排序后的列表与原始列表相比具有相同的性能（我的计时）。

- wero

Answer 3

作为一个简单的例子，证实了wero的答案和apangin的答案（+1！）：以下对两个选项进行了简单比较：

• 创建随机数，并可选择排序
• 创建顺序数字，并可选择洗牌

它也没有实现为JMH基准测试，但类似于原始代码，只对其进行了微小修改以观察效果：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class SortedListTest
{
    private static final long SLOW_ITERATION_MILLIS = 1000L * 3L;

    public static void main(String[] args)
    {
        int size = 100000;
        testBinarySearchOriginal(size, true);
        testBinarySearchOriginal(size, false);
        testBinarySearchShuffled(size, true);
        testBinarySearchShuffled(size, false);
    }

    public static void testBinarySearchOriginal(int size, boolean sort)
    {
        Random r = new Random(0);
        List<Double> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++)
        {
            list.add(r.nextDouble());
        }
        if (sort)
        {
            Collections.sort(list);
        }
        list = new ArrayList<>(list);

        int count = 0;
        int nIterations = 0;
        long startTime = System.currentTimeMillis();
        do
        {
            int index = r.nextInt(size);
            if (index == list.indexOf(list.get(index)))
            {
                count++;
            }
            nIterations++;
        }
        while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
        long duration = System.currentTimeMillis() - startTime;
        double slowFindsPerSec = (double) nIterations / duration * 1000;

        System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
            size, sort, slowFindsPerSec, count);
    }

    public static void testBinarySearchShuffled(int size, boolean sort)
    {
        Random r = new Random(0);
        List<Double> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++)
        {
            list.add((double) i / size);
        }
        if (!sort)
        {
            Collections.shuffle(list);
        }
        list = new ArrayList<>(list);

        int count = 0;
        int nIterations = 0;
        long startTime = System.currentTimeMillis();
        do
        {
            int index = r.nextInt(size);
            if (index == list.indexOf(list.get(index)))
            {
                count++;
            }
            nIterations++;
        }
        while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
        long duration = System.currentTimeMillis() - startTime;
        double slowFindsPerSec = (double) nIterations / duration * 1000;

        System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
            size, sort, slowFindsPerSec, count);
    }

}

我的电脑上的输出是：

Size   100000 sort  true iterations   8560,333 count      25681
Size   100000 sort false iterations  19358,667 count      58076
Size   100000 sort  true iterations  18554,000 count      55662
Size   100000 sort false iterations   8845,333 count      26536

展示得很好，时间正好相反：如果随机数被排序，则排序版本较慢。如果顺序数被洗牌，则洗牌版本较慢。

- Marco13