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

标题是在为什么处理sorting的数组比未sorting的数组更快？

这也是分支预测效果吗？ 注意：这里sorting后的数组处理速度较慢 ！

考虑下面的代码：

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左右的值。

现在，如果我激活收集sorting调用，该值下降到142.为什么？！？

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

Java版本是1.8.0_71（Oracle VM，64位），在Windows 10下运行，在Eclipse Mars中进行JUnittesting。

UPDATE

似乎与连续内存访问有关（Double对象按顺序与随机顺序访问）。 效果开始消失，对于我约10k和更less的数组长度。

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

Answer 1

它看起来像caching/预取效果。

线索是，你比较双打（对象），而不是双打（基元）。 在一个线程中分配对象时，通常在内存中按顺序分配。 所以当indexOf扫描一个列表时，它会经历连续的内存地址。 这对于CPU高速caching预取启发式是很好的。

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

UPDATE

这里是基准来certificate分配对象的顺序很重要。

 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 

Answer 2

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

当你创build未sorting的列表

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

所有的双重最有可能分配在一个连续的内存区域。 迭代通过这将会产生很less的caching未命中。

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

现在，如果您创build一个连续内存的sorting列表：

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

这个sorting的列表具有与原来的（我的时间）相同的性能。

Answer 3

作为一个简单的例子， 通过wero和apangin （+1！）的答案来确认答案 ：下面做了两个选项的简单比较：

• 创build随机数字，并可selectsorting
• 创build连续的数字，并随意混洗

它也没有作为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 

很好地表明时间正好是另一个时间的对立面：如果随机数被sorting，那么sorting后的版本就会变慢。 如果顺序号码被混洗，则混洗版本会变慢。