How specialized are the Stream implementations returned by the standard collections?

Question

`Stream` is an interface so whenever one gets hold of a `Stream` object there are lots of implementation specific details hidden. For example, take the following code: ``` List list = new ArrayList<>(); ... int size = list.stream() .count(); ``` Does it run in constant or linear time? Or this: ``` Set set = new TreeSet<>(); ... set.stream() .sorted() .forEach(System.out::println); ``` Would that be O(n) or O(n log n)? In general, how specialized are the streams implementations returned by the standard collections?

Accepted Answer

Does it run in constant or linear time?

The current implementation runs in linear time:

```
public final long count() {
    return mapToLong(e -> 1L).sum();
}
```

But, this could be improved (there's an RFE for this somewhere) to run in constant time in some situations.

How? A stream is described by a stream source, zero or more intermediate operations, and a terminal operation (here, `count()` is the terminal operation). The stream implementation maintains a set of characteristics about the source, and knows how the characteristics are modified by the operations. For example, a stream backed by a Collection has the characteristic `SIZED`, whereas a stream backed by an Iterator is not sized. Similarly, the operation `map()` is size-preserving, but the operation `filter()` destroys any a priori knowledge of sized-ness. The stream implementation knows the composed characteristics of the pipeline before it starts the terminal operation, so it knows whether the source is sized and whether all stages are size-preserving, and in such cases, could simply ask the source for the size and bypass all the actual stream computation. (But the implementation in Java 8 does not happen to do this.)

Note that the streams need not be specialized to support this; the Collection classes create the stream with a `Spliterator` that knows its characteristics, so a specialized implementation for Collections is not needed, just updating the shared implementation to take advantage of this particular bit of information.

How specialized are the Stream implementations returned by the standard collections?

Solution

Problem