Статьи

Поток Java: Часть 2, Счетчик Всегда Счетчик?

Февраль 6, 2019

В моей предыдущей статье на эту тему мы узнали, что JDK 8
stream()::count требуется больше времени, чем больше элементов в Stream . Для более новых JDK, таких как Java 11, это больше не относится к простым потоковым конвейерам. Узнайте, как вещи улучшились в самом JDK.

Java 8

В моей предыдущей статье мы могли бы заключить, что операция
list.stream().count() — это O(N) в Java 8, т.е. время выполнения зависит от количества элементов в исходном списке. Прочитать статью
здесь

Java 9 и выше

Как справедливо отметили Николай Парлог (@nipafx) и Брайан Гетц (@BrianGoetz) в Twitter, реализация Stream::count была улучшена, начиная с Java 9. Вот сравнение основных
Код Stream::count между Java 8 и более поздними версиями Java:

Java 8 (из класса ReferencePipeline)

1
return mapToLong(e -> 1L).sum();

Java 9 и более поздние версии (из класса ReduceOps)

1
2
3
if (StreamOpFlag.SIZED.isKnown(flags)) {
    return spliterator.getExactSizeIfKnown();
}
1
...

Похоже, Stream::count в Java 9 и позже O(1) для Spliterators известного размера, а не O(N) . Давайте проверим эту гипотезу.

Ориентиры

Свойство big-O можно наблюдать, выполнив следующие тесты JMH для Java 8 и Java 11:

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):

JDK 8 (из моей предыдущей статьи)

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

JDK 11

1
2
3
4
5
6
7
Benchmark                                  (size)   Mode  Cnt          Score           Error  Units
CountBenchmark.listSize                         1  thrpt    5  898916944.365 ± 235047181.830  ops/s
CountBenchmark.listSize                      1000  thrpt    5  865080967.750 ± 203793349.257  ops/s
CountBenchmark.listSize                   1000000  thrpt    5  935820818.641 ±  95756219.869  ops/s
CountBenchmark.listStreamCount                  1  thrpt    5   95660206.302 ±  27337762.894  ops/s
CountBenchmark.listStreamCount               1000  thrpt    5   78899026.467 ±  26299885.209  ops/s
CountBenchmark.listStreamCount            1000000  thrpt    5   83223688.534 ±  16119403.504  ops/s

Как видно, в Java 11 list.stream().count() выполняется list.stream().count()
O(1) а не O(N) .

Брайан Гетц отметил, что некоторые разработчики, которые использовали вызовы метода Stream::peek в Java 8, обнаружили, что эти методы больше не вызывались, если операция терминала Stream::count выполнялась в Java 9 и более поздних версиях. Это вызвало негативную обратную связь с разработчиками JDK. Лично я думаю, что это было правильное решение разработчиков JDK, и это вместо этого предоставило отличную возможность для
Stream::peek получают правильный код.

Более сложные потоковые трубопроводы

В этой главе мы рассмотрим более сложные потоковые конвейеры.

JDK 11

Тагир Валеев пришел к выводу, что конвейеры типа stream().skip(1).count() не являются O(1) для List::stream .

Это можно наблюдать, выполнив следующий тест:

1
2
3
4
@Benchmark
public long listStreamSkipCount() {
    return list.stream().skip(1).count();
}
1
2
3
4
5
6
CountBenchmark.listStreamCount                  1  thrpt    5  105546649.075 ±  10529832.319  ops/s
CountBenchmark.listStreamCount               1000  thrpt    5   81370237.291 ±  15566491.838  ops/s
CountBenchmark.listStreamCount            1000000  thrpt    5   75929699.395 ±  14784433.428  ops/s
CountBenchmark.listStreamSkipCount              1  thrpt    5   35809816.451 ±  12055461.025  ops/s
CountBenchmark.listStreamSkipCount           1000  thrpt    5    3098848.946 ±    339437.339  ops/s
CountBenchmark.listStreamSkipCount        1000000  thrpt    5       3646.513 ±       254.442  ops/s

Таким образом, list.stream().skip(1).count() по-прежнему равен O (N).

Speedment

Некоторые реализации потоков на самом деле знают свои источники и могут использовать соответствующие ярлыки и объединять потоковые операции с самим источником потоков. Это может значительно повысить производительность, особенно для больших потоков с более сложными потоковыми конвейерами, такими как stream().skip(1).count()

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

1
2
3
4
5
6
7
8
9
@Benchmark
public long rentalsSkipCount() {
    return rentals.stream().skip(1).count();
}
 
@Benchmark
public long filmsSkipCount() {
    return films.stream().skip(1).count();
}

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

1
2
SpeedmentCountBenchmark.filmsSkipCount        N/A  thrpt    5   68052838.621 ±    739171.008  ops/s
SpeedmentCountBenchmark.rentalsSkipCount      N/A  thrpt    5   68224985.736 ±   2683811.510  ops/s

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

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

Резюме

Stream::count был значительно улучшен в Java 9.

Существуют реализации потоков, такие как Speedment, которые могут вычислять Stream::count за O(1) даже для более сложных потоковых конвейеров, таких как stream().skip(...).count() stream.filter(...).skip(...).count() stream().skip(...).count() или даже stream.filter(...).skip(...).count() .

Ресурсы

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

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

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

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

41
Share: