Stream.skip behavior with unordered terminal operation

by

Recall that the goal of stream flags (ORDERED, SORTED, SIZED, DISTINCT) is to enable operations to avoid doing unnecessary work. Examples of optimizations that involve stream flags are:

  • If we know the stream is already sorted, then sorted() is a no-op;
  • If we know the size of the stream, we can pre-allocate a correct-sized array in toArray(), avoiding a copy;
  • If we know that the input has no meaningful encounter order, we need not take extra steps to preserve encounter order.

Each stage of a pipeline has a set of stream flags. Intermediate operations can inject, preserve, or clear stream flags. For example, filtering preserves sorted-ness / distinct-ness but not sized-ness; mapping preserves sized-ness but not sorted-ness or distinct-ness. Sorting injects sorted-ness. The treatment of flags for intermediate operations is fairly straightforward, because all decisions are local.

The treatment of flags for terminal operations is more subtle. ORDERED is the most relevant flag for terminal ops. And if a terminal op is UNORDERED, then we do back-propagate the unordered-ness.

Why do we do this? Well, consider this pipeline:

set.stream()
   .sorted()
   .forEach(System.out::println);

Since forEach is not constrained to operate in order, the work of sorting the list is completely wasted effort. So we back-propagate this information (until we hit a short-circuiting operation, such as limit), so as not to lose this optimization opportunity. Similarly, we can use an optimized implementation of distinct on unordered streams.

Is this behavior intended or it’s a bug?

Yes 🙂 The back-propagation is intended, as it is a useful optimization that should not produce incorrect results. However, the bug part is that we are propagating past a previous skip, which we shouldn’t. So the back-propagation of the UNORDERED flag is overly aggressive, and that’s a bug. We’ll post a bug.

If yes is it documented somewhere?

It should be just an implementation detail; if it were correctly implemented, you wouldn’t notice (except that your streams are faster.)

More Related Contents:

  1. Custom thread pool in Java 8 parallel stream
  2. Should I always use a parallel stream when possible?
  3. Java 8’s streams: why parallel stream is slower?
  4. Parallel streams, collectors and thread safety
  5. Is this a bug in Files.lines(), or am I misunderstanding something about parallel streams?
  6. Java 8 Collectors.toMap SortedMap
  7. Why parallel stream get collected sequentially in Java 8
  8. Java 8 grouping using custom collector?
  9. Java8: HashMap to HashMap using Stream / Map-Reduce / Collector
  10. Parallel stream from a HashSet doesn’t run in parallel
  11. How to add elements of a Java8 stream into an existing List
  12. Why is Files.list() parallel stream performing so much slower than using Collection.parallelStream()?
  13. Why does Collectors.toMap report value instead of key on Duplicate Key error?
  14. How to apply Filtering on groupBy in java streams
  15. Nested Java 8 parallel forEach loop perform poor. Is this behavior expected?
  16. Visualization of Java Stream parallelization
  17. What’s the difference between map() and flatMap() methods in Java 8?
  18. Can you split a stream into two streams?
  19. Why does parallel stream with lambda in static initializer cause a deadlock?
  20. Java 8, Streams to find the duplicate elements
  21. forEach vs forEachOrdered in Java 8 Stream
  22. Why does Iterable not provide stream() and parallelStream() methods?
  23. Java Streams: How to do an efficient “distinct and sort”?
  24. stream on JPA lazy list
  25. How does combiner in Stream.collect method work in java 8?
  26. How to short-circuit a reduce() operation on a Stream?
  27. How to get a Stream from a float[]
  28. Difference between findAny() and findFirst() in Java 8
  29. Want to create a stream of characters from char array in java
  30. non-interference requirement on Java 8 streams

Leave a Comment