Headers 是参考Why is it faster to process a sorted array than an unsorted array?
这也是分支预测效果吗?注意:这里对排序数组的处理速度较慢!!
请考虑以下代码:
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 .
UPDATE
似乎与连续的内存访问有关(按顺序访问的Double对象与随机顺序访问) . 对于我来说,对于大约10k或更小的阵列长度,效果开始消失 .
感谢assylias提供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
*/
3 回答
它看起来像缓存/预取效果 .
线索是你比较双打(对象),而不是双打(基元) . 在一个线程中分配对象时,它们通常按顺序分配在内存中 . 因此,当
indexOf
扫描列表时,它会通过顺序存储器地址 . 这有利于CPU缓存预取启发式 .但是在对列表进行排序之后,您仍然必须进行相同数量的内存查找,但这次内存访问将按随机顺序进行 .
UPDATE
Here is the benchmark证明分配对象的顺序很重要 .
我想我们正在看到内存缓存未命中的影响:
创建未排序列表时
所有double都很可能在连续的内存区域中分配 . 迭代这将产生很少的缓存未命中 .
另一方面,在排序列表中,引用以混乱的方式指向内存 .
现在,如果您创建一个具有连续内存的排序列表:
这个排序列表具有与原始列表相同的性能(我的时间) .
作为确认answer by wero和answer by apangin(1!)的简单示例:以下是两个选项的简单比较:
创建随机数,并可选择对其进行排序
创建序列号,并可选择改组它们
它也没有作为JMH基准实现,但与原始代码类似,只需稍加修改即可观察效果:
我机器上的输出是
很好地显示时间恰好与另一个时间相反:如果对随机数进行排序,则排序后的版本会更慢 . 如果随机数被洗牌,那么洗牌版本会变慢 .