In my previous article on the subject, we learned that JDK 8’sstream()::count takes longer time to execute the more elements there are in theStream. For more recent JDKs, such as Java 11, that is no longer the case for simple stream pipelines. Learn how things have gotten improved within the JDK itself.
Java 8
In my previous article, we could conclude that the operationlist.stream().count() isO(N) under Java 8, i.e. the execution time depends on the number of elements in the original list. Read the article
here.
Java 9 and Upwards
As rightfully pointed out by Nikolai Parlog (@nipafx) and Brian Goetz (@BrianGoetz) on Twitter, the implementation ofStream::count was improved beginning from Java 9. Here is a comparison of the underlyingStream::count code between Java 8 and later Java versions:
Java 8 (from the ReferencePipeline class)
1 | return mapToLong(e -> 1L).sum(); |
Java 9 and later (from the ReduceOps class)
1 2 3 | if (StreamOpFlag.SIZED.isKnown(flags)) { return spliterator.getExactSizeIfKnown();} |
1 | ... |
It appears Stream::count in Java 9 and later is O(1) for Spliterators of known size rather than beingO(N). Let’s verify that hypothesis.
Benchmarks
The big-O property can be observed by running the following JMH benchmarks under Java 8 and 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(); }} |
This will produce the following outputs on my laptop (MacBook Pro mid 2015, 2.2 GHz Intel Core i7):
JDK 8 (from my previous article)
1 2 3 4 5 6 7 | Benchmark (size) Mode Cnt Score Error UnitsCountBenchmark.listSize 1 thrpt 5 966658591.905 ± 175787129.100 ops/sCountBenchmark.listSize 1000 thrpt 5 862173760.015 ± 293958267.033 ops/sCountBenchmark.listSize 1000000 thrpt 5 879607621.737 ± 107212069.065 ops/sCountBenchmark.listStreamCount 1 thrpt 5 39570790.720 ± 3590270.059 ops/sCountBenchmark.listStreamCount 1000 thrpt 5 30383397.354 ± 10194137.917 ops/sCountBenchmark.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 UnitsCountBenchmark.listSize 1 thrpt 5 898916944.365 ± 235047181.830 ops/sCountBenchmark.listSize 1000 thrpt 5 865080967.750 ± 203793349.257 ops/sCountBenchmark.listSize 1000000 thrpt 5 935820818.641 ± 95756219.869 ops/sCountBenchmark.listStreamCount 1 thrpt 5 95660206.302 ± 27337762.894 ops/sCountBenchmark.listStreamCount 1000 thrpt 5 78899026.467 ± 26299885.209 ops/sCountBenchmark.listStreamCount 1000000 thrpt 5 83223688.534 ± 16119403.504 ops/s |
As can be seen, in Java 11, the list.stream().count() operation is nowO(1) and notO(N).
Brian Goetz pointed out that some developers, who were using Stream::peek method calls under Java 8, discovered that these methods were no longer invoked if theStream::count terminal operation was run under Java 9 and onwards. This generated some negative feedback to the JDK developers. Personally, I think it was the right decision by the JDK developers and that this instead presented a great opportunity forStream::peek users to get their code right.
More Complex Stream Pipelines
In this chapter, we will take a look at more complex stream pipelines.
JDK 11
Tagir Valeev concluded that pipelines like stream().skip(1).count() are not O(1) forList::stream.
This can be observed by running the following benchmark:
1 2 3 4 | @Benchmarkpublic long listStreamSkipCount() { return list.stream().skip(1).count();} |
1 2 3 4 5 6 | CountBenchmark.listStreamCount 1 thrpt 5 105546649.075 ± 10529832.319 ops/sCountBenchmark.listStreamCount 1000 thrpt 5 81370237.291 ± 15566491.838 ops/sCountBenchmark.listStreamCount 1000000 thrpt 5 75929699.395 ± 14784433.428 ops/sCountBenchmark.listStreamSkipCount 1 thrpt 5 35809816.451 ± 12055461.025 ops/sCountBenchmark.listStreamSkipCount 1000 thrpt 5 3098848.946 ± 339437.339 ops/sCountBenchmark.listStreamSkipCount 1000000 thrpt 5 3646.513 ± 254.442 ops/s |
Thus, list.stream().skip(1).count() is still O(N).
Speedment
Some stream implementations are actually aware of their sources and can take appropriate shortcuts and merge stream operations into the stream source itself. This can improve performance massively, especially for large streams with more complex stream pipelines likestream().skip(1).count()
The Speedment ORM tool allows databases to be viewed as Stream objects and these streams can optimize away many stream operations like theStream::count, Stream::skip,Stream::limit operation as demonstrated in the benchmark below. I have used the open-source Sakila exemplary database as data input. The Sakila database is all about rental films, artists etc.
1 2 3 4 5 6 7 8 9 | @Benchmarkpublic long rentalsSkipCount() { return rentals.stream().skip(1).count();}@Benchmarkpublic long filmsSkipCount() { return films.stream().skip(1).count();} |
When run, the following output will be produced:
1 2 | SpeedmentCountBenchmark.filmsSkipCount N/A thrpt 5 68052838.621 ± 739171.008 ops/sSpeedmentCountBenchmark.rentalsSkipCount N/A thrpt 5 68224985.736 ± 2683811.510 ops/s |
The “rental” table contains over 10,000 rows whereas the “film” table only contains 1,000 rows. Nevertheless, their stream().skip(1).count() operations complete in almost the same time. Even if a table would contain a trillion rows, it would still count the elements in the same elapsed time. Thus, the stream().skip(1).count() implementation has a complexity that is O(1) and notO(N).
Note: The benchmark above were run with “DataStore” in-JVM-memory acceleration. If run with no acceleration directly against a database, the response time would depend on the underlying database’s ability to execute a nested“SELECT count(*) …” statement.
Summary
Stream::count was significantly improved in Java 9.
There are stream implementations, such as Speedment, that are able to compute Stream::count in O(1) time even for more complex stream pipelines like stream().skip(...).count() or evenstream.filter(...).skip(...).count().
Resources
Speedment Stream ORM Initializer:https://www.speedment.com/initializer/
Sakila: https://dev.mysql.com/doc/index-other.html orhttps://hub.docker.com/r/restsql/mysql-sakila
Published on Java Code Geeks with permission by Per Minborg, partner at our JCG program. See the original article here: Java Stream: Part 2, Is a Count Always a Count? Opinions expressed by Java Code Geeks contributors are their own. |
