为什么过滤未排序的列表比过滤排序列表更快 [英] Why filtering an unsorted list is faster than filtering a sorted list
问题描述
我一直在玩Java 8 Streams - API ，我决定使用microbenchmark stream（）和 parallelStream（） streams。正如预期的那样， parallelStream（）的速度是原来的两倍，但还有其他东西弹出 - 如果我在将数据传递给过滤器之前对数据进行排序 filter-> map-> collect 结果需要花费5-8倍的时间，而不是传递未排序的列表。
I've been playing with Java 8 Streams - API and I decided to microbenchmark stream() and parallelStream() streams. As expected the parallelStream() was as twice as fast, but something else popped up - If I sort the data before passing them to the filter it takes 5-8 times more time to filter->map->collect the result, than passing an unsorted list.
(Stream) Elapsed time [ns] : 53733996 (53 ms)
(ParallelStream) Elapsed time [ns] : 25901907 (25 ms)
已排序
Sorted
(Stream) Elapsed time [ns] : 336976149 (336 ms)
(ParallelStream) Elapsed time [ns] : 204781387 (204 ms)
以下是代码
Here is the code
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<Integer> getRandom(int nElements) {
final Random random = new Random();
final List<Integer> data = new ArrayList<Integer>(nElements);
for (int i = 0; i < MyFirstLambda.ELEMENTS; i++) {
data.add(random.nextInt(MyFirstLambda.ELEMENTS));
}
return data;
}
private static void benchStream(List<Integer> data) {
final Stopwatch stopwatch = new Stopwatch();
final List<Long> 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<Integer> data) {
final Stopwatch stopwatch = new Stopwatch();
final List<Long> 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<Integer> 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);
}
}
更新
这是一个更好的基准代码
Update
Here is a better benchmark code
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<Integer> getRandom(int nElements) {
final Random random = new Random();
final List<Integer> data = new ArrayList<Integer>(nElements);
for (int i = 0; i < MyFirstLambda.ELEMENTS; i++) {
data.add(random.nextInt(MyFirstLambda.ELEMENTS));
}
return data;
}
private static List<Long> filterStream(List<Integer> data) {
final List<Long> smallLongs = data.stream()
.filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN)
.map(Long::valueOf)
.collect(Collectors.toList());
return smallLongs;
}
private static List<Long> filterParallelStream(List<Integer> data) {
final List<Long> smallLongs = data.parallelStream()
.filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN)
.map(Long::valueOf)
.collect(Collectors.toList());
return smallLongs;
}
private static long filterAndCount(List<Integer> data) {
return data.stream()
.filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN)
.count();
}
private static long filterAndCountinParallel(List<Integer> data) {
return data.parallelStream()
.filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN)
.count();
}
private static void warmUp(List<Integer> 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<Integer> 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<Integer> 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 c.g.s.playground.util.time.Stopwatch - (Stream: UNSORTED) Elapsed time [ns] : 66812263 (66 ms)
16:09:22.149 [main] INFO c.g.s.playground.util.time.Stopwatch - (ParallelStream: UNSORTED) Elapsed time [ns] : 39580682 (39 ms)
16:09:23.875 [main] INFO c.g.s.playground.util.time.Stopwatch - (Count: UNSORTED) Elapsed time [ns] : 97852866 (97 ms)
16:09:25.537 [main] INFO c.g.s.playground.util.time.Stopwatch - (Count in parallel: UNSORTED) Elapsed time [ns] : 94884189 (94 ms)
16:09:35.608 [main] INFO c.g.s.playground.util.time.Stopwatch - (Stream: SORTED) Elapsed time [ns] : 361717676 (361 ms)
16:09:38.439 [main] INFO c.g.s.playground.util.time.Stopwatch - (ParallelStream: SORTED) Elapsed time [ns] : 150115808 (150 ms)
16:09:41.308 [main] INFO c.g.s.playground.util.time.Stopwatch - (Count: SORTED) Elapsed time [ns] : 338335743 (338 ms)
16:09:44.209 [main] INFO c.g.s.playground.util.time.Stopwatch - (Count in parallel: SORTED) Elapsed time [ns] : 370968432 (370 ms)
16:09:50.693 [main] INFO c.g.s.playground.util.time.Stopwatch - (Stream: IN REVERSE ORDER) Elapsed time [ns] : 352036140 (352 ms)
16:09:53.323 [main] INFO c.g.s.playground.util.time.Stopwatch - (ParallelStream: IN REVERSE ORDER) Elapsed time [ns] : 151044664 (151 ms)
16:09:56.159 [main] INFO c.g.s.playground.util.time.Stopwatch - (Count: IN REVERSE ORDER) Elapsed time [ns] : 359281197 (359 ms)
16:09:58.991 [main] INFO c.g.s.playground.util.time.Stopwatch - (Count in parallel: IN REVERSE ORDER) Elapsed time [ns] : 353177542 (353 ms)
所以，我的问题是为什么过滤未排序的列表是比筛选列表过滤更快？
So, my question is why filtering an unsorted list is faster than filtering a sorted list ?
推荐答案
当您使用未排序列表时，将访问所有元组在
memory-o中刻申。它们已在RAM中连续分配。 CPU喜欢
顺序访问内存，因为他们可以推测性地请求
下一个缓存行，以便在需要时始终存在。
When you are using the unsorted list all tuples are accessed in memory-order. They have been allocated consecutively in RAM. CPUs love accessing memory sequentially because they can speculatively request the next cache line so it will always be present when needed.
当你排序时你把它放入随机顺序的列表因为
你的排序键是随机生成的。这意味着内存
访问元组成员是不可预测的。 CPU无法预取
内存，几乎每次访问元组都是一次缓存未命中。
When you are sorting the list you put it into random order because your sort keys are randomly generated. This means that the memory accesses to tuple members are unpredictable. The CPU cannot prefetch memory and almost every access to a tuple is a cache miss.
这是GC内存特定优势的一个很好的例子
管理：已经分配在一起并且
一起使用的数据结构表现非常好。它们具有很好的
参考位置。
This is a nice example for a specific advantage of GC memory management: data structures which have been allocated together and are used together perform very nicely. They have great locality of reference.
在这种情况下，缓存未命中的惩罚超过了保存的分支预测
惩罚。
The penalty from cache misses outweighs the saved branch prediction penalty in this case.
这个问题是接受的答案，也回答了我的问题：
为什么处理排序的数组比未排序的数组慢？
This question's accepted answer, answers my question too: Why is processing a sorted array slower than an unsorted array?
当我创建原始 List sorted时 - 即它的元素在内存中是后续的，执行时间没有差别，它等于<$ c $当 List 填充随机数时，c> unsorted 版本。
When I create the original List sorted - i.e. it's elements are sequentally in memory, there is no difference in the execution time and it is equal to the unsorted version when the List is filled with random numbers.
这篇关于为什么过滤未排序的列表比过滤排序列表更快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
