Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8193641

Stream::distinct should check if Stream is already distinct

    Details

    • Type: Enhancement
    • Status: Open
    • Priority: P4
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: tbd
    • Component/s: core-libs
    • Labels:
      None

      Description

      See: http://richardstartin.uk/spliterator-characteristics-and-performance/

          @Benchmark
          public long countRange() {
              return IntStream.range(0, size).count();
          }

          @Benchmark
          public long countRangeDistinct() {
              return IntStream.range(0, size).distinct().count();
          }

      Currently countRange is always quick (15ns/op) independent of size, but countRange scales with size:

      Benchmark (size) Mode Cnt Score Error Units
      StreamBench.countRange 1024 avgt 5 17.160 ± 8.957 ns/op
      StreamBench.countRangeDistinct 1024 avgt 5 34025.817 ± 15145.915 ns/op

      Benchmark (size) Mode Cnt Score Error Units
      StreamBench.countRange 264444 avgt 5 15.952 ± 5.163 ns/op
      StreamBench.countRangeDistinct 264444 avgt 5 2191633.584 ± 2738022.121 ns/op

      With a patch[1] to trust Streams that are already distinct, the latter op is optimized for all size inputs:

      Benchmark (size) Mode Cnt Score Error Units
      StreamBench.countRange 264444 avgt 5 15.439 ± 1.842 ns/op
      StreamBench.countRangeDistinct 264444 avgt 5 32.939 ± 4.268 ns/op

      [1]
      diff -r 0ee20aad71c4 src/java.base/share/classes/java/util/stream/AbstractPipeline.java
      --- a/src/java.base/share/classes/java/util/stream/AbstractPipeline.java Thu Dec 14 16:05:08 2017 +0100
      +++ b/src/java.base/share/classes/java/util/stream/AbstractPipeline.java Fri Dec 15 20:27:27 2017 +0100
      @@ -509,6 +509,10 @@
               return combinedFlags;
           }
       
      + final boolean isDistinct() {
      + return StreamOpFlag.DISTINCT.isKnown(combinedFlags);
      + }
      +
           final boolean isOrdered() {
               return StreamOpFlag.ORDERED.isKnown(combinedFlags);
           }
      diff -r 0ee20aad71c4 src/java.base/share/classes/java/util/stream/ReferencePipeline.java
      --- a/src/java.base/share/classes/java/util/stream/ReferencePipeline.java Thu Dec 14 16:05:08 2017 +0100
      +++ b/src/java.base/share/classes/java/util/stream/ReferencePipeline.java Fri Dec 15 20:27:27 2017 +0100
      @@ -383,6 +383,9 @@
       
           @Override
           public final Stream<P_OUT> distinct() {
      + if (this.isDistinct()) {
      + return this;
      + }
               return DistinctOps.makeRef(this);
           }
       

        Attachments

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              redestad Claes Redestad
            • Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

              • Created:
                Updated: