Почему фильтрация несортированного списка быстрее, чем фильтрация отсортированного списка
Я играл с Java 8Streams - API
и я решил микробенчмарк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<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);
}
}
ОбновитьВот лучший тестовый код
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)
Итак, мой вопрос: почему фильтрация несортированного списка быстрее, чем фильтрация отсортированного списка?