为什么过滤未排序的列表比过滤排序列表更快
我一直在玩Java 8 Streams - API ，我决定使用microbenchmark stream()和parallelStream()流。 正如预期的那样， parallelStream()速度提高了两倍，但是其他东西弹出 – 如果我在将数据传递给filter之前对数据进行排序，则需要花费5-8倍的时间来filter->map->collect结果，而不是传递未排序的列表。
未分类
(Stream) Elapsed time [ns] : 53733996 (53 ms) (ParallelStream) Elapsed time [ns] : 25901907 (25 ms)
排序
(Stream) Elapsed time [ns] : 336976149 (336 ms) (ParallelStream) Elapsed time [ns] : 204781387 (204 ms)
这是代码
package com.github.svetlinzarev.playground.javalang.lambda; import static java.lang.Long.valueOf; import java.util.ArrayList; import java.util.List; import java.util.Random; import java.util.stream.Collectors; import com.github.svetlinzarev.playground.util.time.Stopwatch; public class MyFirstLambda { private static final int ELEMENTS = 1024 * 1024 * 16; private static List getRandom(int nElements) { final Random random = new Random(); final List data = new ArrayList(nElements); for (int i = 0; i < MyFirstLambda.ELEMENTS; i++) { data.add(random.nextInt(MyFirstLambda.ELEMENTS)); } return data; } private static void benchStream(List data) { final Stopwatch stopwatch = new Stopwatch(); final List smallLongs = data.stream() .filter(i -> i.intValue() < 16) .map(Long::valueOf) .collect(Collectors.toList()); stopwatch.log("Stream"); System.out.println(smallLongs); } private static void benchParallelStream(List data) { final Stopwatch stopwatch = new Stopwatch(); final List smallLongs = data.parallelStream() .filter(i -> i.intValue() < 16) .map(Long::valueOf) .collect(Collectors.toList()); stopwatch.log("ParallelStream"); System.out.println(smallLongs); } public static void main(String[] args) { final List data = MyFirstLambda.getRandom(MyFirstLambda.ELEMENTS); // Collections.sort(data, (first, second) -> first.compareTo(second)); //<- Sort the data MyFirstLambda.benchStream(data); MyFirstLambda.benchParallelStream(data); MyFirstLambda.benchStream(data); MyFirstLambda.benchParallelStream(data); MyFirstLambda.benchStream(data); MyFirstLambda.benchParallelStream(data); MyFirstLambda.benchStream(data); MyFirstLambda.benchParallelStream(data); MyFirstLambda.benchStream(data); MyFirstLambda.benchParallelStream(data); } }
更新
这是一个更好的基准代码
package com.github.svetlinzarev.playground.javalang.lambda; import static java.lang.Long.valueOf; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Random; import java.util.stream.Collectors; import com.github.svetlinzarev.playground.util.time.Stopwatch; public class MyFirstLambda { private static final int ELEMENTS = 1024 * 1024 * 10; private static final int SMALLER_THAN = 16; private static final int WARM_UP_ITERRATIONS = 1000; private static List getRandom(int nElements) { final Random random = new Random(); final List data = new ArrayList(nElements); for (int i = 0; i < MyFirstLambda.ELEMENTS; i++) { data.add(random.nextInt(MyFirstLambda.ELEMENTS)); } return data; } private static List filterStream(List data) { final List smallLongs = data.stream() .filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN) .map(Long::valueOf) .collect(Collectors.toList()); return smallLongs; } private static List filterParallelStream(List data) { final List smallLongs = data.parallelStream() .filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN) .map(Long::valueOf) .collect(Collectors.toList()); return smallLongs; } private static long filterAndCount(List data) { return data.stream() .filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN) .count(); } private static long filterAndCountinParallel(List data) { return data.parallelStream() .filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN) .count(); } private static void warmUp(List data) { for (int i = 0; i < MyFirstLambda.WARM_UP_ITERRATIONS; i++) { MyFirstLambda.filterStream(data); MyFirstLambda.filterParallelStream(data); MyFirstLambda.filterAndCount(data); MyFirstLambda.filterAndCountinParallel(data); } } private static void benchmark(List data, String message) throws InterruptedException { System.gc(); Thread.sleep(1000); // Give it enough time to complete the GC cycle final Stopwatch stopwatch = new Stopwatch(); MyFirstLambda.filterStream(data); stopwatch.log("Stream: " + message); System.gc(); Thread.sleep(1000); // Give it enough time to complete the GC cycle stopwatch.reset(); MyFirstLambda.filterParallelStream(data); stopwatch.log("ParallelStream: " + message); System.gc(); Thread.sleep(1000); // Give it enough time to complete the GC cycle stopwatch.reset(); MyFirstLambda.filterAndCount(data); stopwatch.log("Count: " + message); System.gc(); Thread.sleep(1000); // Give it enough time to complete the GC cycle stopwatch.reset(); MyFirstLambda.filterAndCount(data); stopwatch.log("Count in parallel: " + message); } public static void main(String[] args) throws InterruptedException { final List data = MyFirstLambda.getRandom(MyFirstLambda.ELEMENTS); MyFirstLambda.warmUp(data); MyFirstLambda.benchmark(data, "UNSORTED"); Collections.sort(data, (first, second) -> first.compareTo(second)); MyFirstLambda.benchmark(data, "SORTED"); Collections.sort(data, (first, second) -> second.compareTo(first)); MyFirstLambda.benchmark(data, "IN REVERSE ORDER"); } }
结果再次类似：
16:09:20.470 [main] INFO cgsplayground.util.time.Stopwatch - (Stream: UNSORTED) Elapsed time [ns] : 66812263 (66 ms) 16:09:22.149 [main] INFO cgsplayground.util.time.Stopwatch - (ParallelStream: UNSORTED) Elapsed time [ns] : 39580682 (39 ms) 16:09:23.875 [main] INFO cgsplayground.util.time.Stopwatch - (Count: UNSORTED) Elapsed time [ns] : 97852866 (97 ms) 16:09:25.537 [main] INFO cgsplayground.util.time.Stopwatch - (Count in parallel: UNSORTED) Elapsed time [ns] : 94884189 (94 ms) 16:09:35.608 [main] INFO cgsplayground.util.time.Stopwatch - (Stream: SORTED) Elapsed time [ns] : 361717676 (361 ms) 16:09:38.439 [main] INFO cgsplayground.util.time.Stopwatch - (ParallelStream: SORTED) Elapsed time [ns] : 150115808 (150 ms) 16:09:41.308 [main] INFO cgsplayground.util.time.Stopwatch - (Count: SORTED) Elapsed time [ns] : 338335743 (338 ms) 16:09:44.209 [main] INFO cgsplayground.util.time.Stopwatch - (Count in parallel: SORTED) Elapsed time [ns] : 370968432 (370 ms) 16:09:50.693 [main] INFO cgsplayground.util.time.Stopwatch - (Stream: IN REVERSE ORDER) Elapsed time [ns] : 352036140 (352 ms) 16:09:53.323 [main] INFO cgsplayground.util.time.Stopwatch - (ParallelStream: IN REVERSE ORDER) Elapsed time [ns] : 151044664 (151 ms) 16:09:56.159 [main] INFO cgsplayground.util.time.Stopwatch - (Count: IN REVERSE ORDER) Elapsed time [ns] : 359281197 (359 ms) 16:09:58.991 [main] INFO cgsplayground.util.time.Stopwatch - (Count in parallel: IN REVERSE ORDER) Elapsed time [ns] : 353177542 (353 ms)
所以，我的问题是为什么过滤未排序的列表比过滤排序列表更快？
当您使用未排序列表时，将按内存顺序访问所有元组。 它们已在RAM中连续分配。 CPU喜欢顺序访问内存，因为它们可以推测性地请求下一个缓存行，以便在需要时始终存在。
当您对列表进行排序时，您将其按随机顺序排列，因为您的排序键是随机生成的。 这意味着对元组成员的内存访问是不可预测的。 CPU无法预取内存，几乎每次访问元组都是缓存未命中。
这是GC内存管理特定优势的一个很好的例子：已经分配在一起并一起使用的数据结构表现得非常好。 他们有很好的参考地点。
在这种情况下，缓存未命中的惩罚超过了保存的分支预测惩罚。
这个问题已被接受的答案，也回答了我的问题： 为什么处理排序的数组比未排序的数组慢？
当我创建原始List排序时 – 即它的元素在内存中是后续的，执行时间没有区别，当List用随机数填充时，它等于unsorted版本。