Статьи

Поток Java: всегда ли счет?

Декабрь 13, 2018

Может показаться очевидным, что подсчет элементов в Stream занимает больше времени, чем больше элементов в Stream . Но на самом деле,
Иногда Stream::count может быть выполнен за одну операцию, независимо от того, сколько у вас элементов. Прочитайте эту статью и узнайте как.

Сложность графа

Терминальная операция Stream::count считает количество элементов в
Stream Сложность операции часто составляет O(N) , что означает, что количество подопераций пропорционально количеству элементов в
Stream

Напротив, метод List::size имеет сложность O(1) что означает, что независимо от количества элементов в List , метод size() будет возвращаться в постоянное время. Это можно наблюдать, выполнив следующие тесты JMH:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
@State(Scope.Benchmark)
public class CountBenchmark {
 
    private List<Integer> list;
 
    @Param({"1", "1000", "1000000"})
    private int size;
 
    @Setup
    public void setup() {
        list = IntStream.range(0, size)
            .boxed()
            .collect(toList());
    }
 
    @Benchmark
    public long listSize() {
        return list.size();
    }
 
    @Benchmark
    public long listStreamCount() {
        return list.stream().count();
    }
 
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
            .include(CountBenchmark.class.getSimpleName())
            .mode(Mode.Throughput)
            .threads(Threads.MAX)
            .forks(1)
            .warmupIterations(5)
            .measurementIterations(5)
            .build();
 
        new Runner(opt).run();
 
    }
 
}

Это привело к следующему выводу на моем ноутбуке (MacBook Pro середина 2015 года, 2,2 ГГц Intel Core i7):

1
2
3
4
5
6
7
Benchmark                        (size)   Mode  Cnt          Score           Error  Units
CountBenchmark.listSize               1  thrpt    5  966658591.905 ± 175787129.100  ops/s
CountBenchmark.listSize            1000  thrpt    5  862173760.015 ± 293958267.033  ops/s
CountBenchmark.listSize         1000000  thrpt    5  879607621.737 ± 107212069.065  ops/s
CountBenchmark.listStreamCount        1  thrpt    5   39570790.720 ±   3590270.059  ops/s
CountBenchmark.listStreamCount     1000  thrpt    5   30383397.354 ±  10194137.917  ops/s
CountBenchmark.listStreamCount  1000000  thrpt    5        398.959 ±       170.737  ops/s
1
<br>

Как можно видеть, пропускная способность List::size в значительной степени не зависит от количества элементов в List тогда как пропускная способность Stream::count быстро падает по мере увеличения количества элементов. Но так ли это всегда для всех реализаций Stream как таковых?

Source Aware Streams

Некоторые реализации потоков на самом деле знают свои источники и могут использовать соответствующие ярлыки и объединять потоковые операции с самим источником потоков. Это может значительно повысить производительность, особенно для больших потоков. Инструмент Speedment ORM позволяет просматривать базы данных как объекты Stream, и эти потоки могут оптимизировать многие потоковые операции, такие как операция Stream::count как показано в бенчмарке ниже. В качестве ввода данных я использовал примерную базу данных Sakila с открытым исходным кодом. База данных Sakila полностью посвящена прокату фильмов, артистов и т. Д.

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
@State(Scope.Benchmark)
public class SpeedmentCountBenchmark {
 
    private Speedment app;
    private RentalManager rentals;
    private FilmManager films;
 
    @Setup
    public void setup() {
        app =  new SakilaApplicationBuilder()
            .withBundle(DataStoreBundle.class)
            .withLogging(ApplicationBuilder.LogType.STREAM)
            .withPassword(ExampleUtil.DEFAULT_PASSWORD)
            .build();
 
        app.get(DataStoreComponent.class).ifPresent(DataStoreComponent::load);
 
        rentals = app.getOrThrow(RentalManager.class);
        films = app.getOrThrow(FilmManager.class);
 
    }
 
    @TearDown
    public void tearDown() {
        app.close();
    }
 
 
    @Benchmark
    public long rentalsCount() {
        return rentals.stream().count();
    }
 
 
    @Benchmark
    public long filmsCount() {
        return films.stream().count();
    }
 
 
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
            .include(SpeedmentCountBenchmark.class.getSimpleName())
            .mode(Mode.Throughput)
            .threads(Threads.MAX)
            .forks(1)
            .warmupIterations(5)
            .measurementIterations(5)
            .build();
 
        new Runner(opt).run();
 
    }
 
}

При запуске будет получен следующий вывод:

1
2
3
Benchmark                              Mode  Cnt         Score          Error  Units
SpeedmentCountBenchmark.filmsCount    thrpt    5  71037544.648 ± 75915974.254  ops/s
SpeedmentCountBenchmark.rentalsCount  thrpt    5  69750012.675 ± 37961414.355  ops/s
1
<br>
1
<br>

Таблица «прокат» содержит более 10000 строк, тогда как таблица «фильм» содержит только 1000 строк. Тем не менее их операции Stream::count завершаются практически в одно и то же время. Даже если таблица будет содержать триллион строк, она все равно будет считать элементы за то же время. Таким образом
Реализация Stream::count имеет сложность O(1) а не
O(N)

Примечание. Вышеприведенный тест выполнялся с ускорением «DataStore» в JVM-памяти Speedment. При запуске без ускорения непосредственно с базой данных время отклика будет зависеть от способности базовой базы данных выполнить запрос “SELECT count(*) FROM film” .

Резюме

Можно создать реализацию Stream которая подсчитывает их элементы в одной операции, а не подсчитывает каждый элемент в потоке. Это может значительно повысить производительность, особенно для потоков со многими элементами.

Ресурсы

Инициализатор ускорения потока ORM: https://www.speedment.com/initializer/

Сакила: https://dev.mysql.com/doc/index-other.html или https://hub.docker.com/r/restsql/mysql-sakila

См. Оригинальную статью здесь: Поток Java: всегда ли счет?

Мнения, высказанные участниками Java Code Geeks, являются их собственными.

35
Share: