RFR: 8362958: Unnecessary copying / sorting in Streams using Comparator.naturalOrder()

[Viktor Klang]

On Tue, 11 Nov 2025 02:43:14 GMT, Patrick Strawderman <duke at openjdk.org> wrote:

> When `Comparator.naturalOrder()` was explicitly supplied to a collection such as `TreeSet`, or passed into the `sorted` method of a stream, the sorted characteristic was not preserved, causing unnecessary buffering and duplicate sorting.
> 
> Example:
> 
> 
> TreeSet<Integer> sortedSet = new TreeSet<>(Comparator.naturalOrder());
> sortedSet.add(1);
> sortedSet.add(2);
> // SortedOps.OfRef.opWrapSink is not a no-op
> sortedSet.stream().sorted().forEach(System.out::println);
> 
> or
> 
> TreeSet<Integer> sortedSet = new TreeSet<>();
> sortedSet.add(1);
> sortedSet.add(2);
> // SortedOps.OfRef.opWrapSink is not a no-op
> sortedSet.stream().sorted(Comparator.naturalOrder()).forEach(System.out::println);
> 
> 
> This PR updates `SortedOps.makeRef` and `StreamOpFlag.fromCharacteristics` to handle the above cases and avoid the unnecessary sort step.

src/java.base/share/classes/java/util/stream/SortedOps.java line 64:

> 62:                                 Comparator<? super T> comparator) {
> 63:         return Comparator.naturalOrder().equals(comparator) ?
> 64:                 new OfRef<>(upstream) : new OfRef<>(upstream, comparator);

I think it would be better to address this directly in the OfRef constructor, and let the 1-arg constructor delegate to the 2-arg constructor.

src/java.base/share/classes/java/util/stream/StreamOpFlag.java line 754:

> 752:         if ((characteristics & Spliterator.SORTED) != 0 &&
> 753:                 !(spliterator.getComparator() == null ||
> 754:                         spliterator.getComparator().equals(Comparator.naturalOrder()))) {

The following would avoid having to call getComparator() twice and be all &&s.

Suggestion:

        if ((characteristics & Spliterator.SORTED) != 0 &&
                spliterator.getComparator() instanceof Comparator c &&
                !c.equals(Comparator.naturalOrder()))) {

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/28226#discussion_r2514463670
PR Review Comment: https://git.openjdk.org/jdk/pull/28226#discussion_r2514464014