为什么处理排序数组比未排序数组*慢*?(Java 的 ArrayList.indexOf) [英] Why is processing a sorted array *slower* than an unsorted array? (Java's ArrayList.indexOf)

问题描述

标题参考了为什么处理排序数组比处理未排序数组更快吗?

这也是分支预测效果吗?注意:这里对排序数组的处理慢！！

Is this a branch prediction effect, too? Beware: here the processing for the sorted array is slower!!

考虑以下代码:

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 的值.

This prints out a value of around 720 on my machine.

现在，如果我激活集合排序调用，该值会下降到 142.为什么?！?

Now if I activate the collections sort call, that value drops down to 142. Why?!?

结果是决定性的，如果我增加迭代次数/时间，它们不会改变.

The results are conclusive, they don't change if I increase the number of iterations/time.

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

Java version is 1.8.0_71 (Oracle VM, 64 bit), running under Windows 10, JUnit test in Eclipse Mars.

更新

似乎与连续内存访问有关(按顺序访问的双对象与按随机顺序访问的对象).对于大约 10k 或更短的数组长度，效果对我来说开始消失.

Seems to be related to contiguous memory access (Double objects accessed in sequential order vs in random order). The effect starts vanish for me for array lengths of around 10k and less.

感谢 assylias 提供 结果:

Thanks to assylias for providing the results:

/**
 * 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
 */

推荐答案

看起来像缓存/预取效果.

It looks like caching / prefetching effect.

线索是您比较的是双精度数(对象)，而不是双精度数(原语).当您在一个线程中分配对象时，它们通常在内存中按顺序分配.所以当 indexOf 扫描一个列表时，它会遍历连续的内存地址.这对 CPU 缓存预取启发式很有用.

The clue is that you compare Doubles (objects), not doubles (primitives). When you allocate objects in one thread, they are typically allocated sequentially in memory. So when indexOf scans a list, it goes through sequential memory addresses. This is good for CPU cache prefetching heuristics.

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

But after you sort the list, you still have to do the same number of memory lookups in average, but this time memory access will be in random order.

更新

这里是基准来证明分配对象的顺序很重要.

Here is the benchmark to prove that the order of allocated objects matters.

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

这篇关于为什么处理排序数组比未排序数组*慢*?(Java 的 ArrayList.indexOf)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！