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

performance java arraylist

2022-08-31 12:01:44

这也是一种分支预测效应吗？注意：这里排序数组的处理速度较慢！！

请考虑以下代码：

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测试下运行。

更新

似乎与连续内存访问有关（按顺序访问的双对象与按随机顺序访问的对象）。对于大约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
 */

答案 1

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

线索是你比较双打（对象），而不是双打（基元）。在一个线程中分配对象时，它们通常在内存中按顺序分配。因此，当扫描列表时，它会通过顺序内存地址。这适用于 CPU 缓存预取启发式方法。indexOf

但是对列表进行排序后，您仍然需要平均执行相同数量的内存查找，但这次内存访问将按随机顺序进行。

更新

这是证明已分配对象的顺序很重要的基准。

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

答案 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()));
}

这个排序列表的性能与原始列表（我的时间）相同。