Почему фильтрация несортированного списка быстрее, чем фильтрация отсортированного списка

Я играл с 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)

Итак, мой вопрос: почему фильтрация несортированного списка быстрее, чем фильтрация отсортированного списка?

Ответы на вопрос(1)

Ваш ответ на вопрос