TreeMap sub-map entry spliterator is expensive

XMLWordPrintable

    • Type: Enhancement
    • Resolution: Unresolved
    • Priority: P4
    • None
    • Affects Version/s: None
    • Component/s: core-libs

      TreeMap sub-maps use the default IteratorSpliterator implementation for EntrySetView which is slow for some operations, because EntrySetView.size() iterates all elements. This is most trivially shown by something like `largeTreeMap.tailMap(0L, false).entrySet().limit(1).count()` taking a long time.

      keySet() does not have the same problem, as it provides a custom Spliterator implementation which is not Spliterator.SIZED, and returns Long.MAX_VALUE for estimateSize() (which is the recommended approach when the size is expensive to compute).

      ```
      import java.util.Collection;
      import java.util.TreeMap;

      void main() {
          var map = new TreeMap<Long, String>();
          for (long i = 0; i < 10_000_000; i++) map.put(i, Long.toString(i));
          test(map.tailMap(0L, false).keySet());
          test(map.tailMap(0L, false).entrySet());
      }

      void test(Collection x) {
          IO.println(x.getClass());
          long start = System.nanoTime();
          x.stream().limit(1).count();
          IO.println("\t.stream().limit(1).count() took " + (System.nanoTime() - start) / 1_000_000.0 + "ms");
          IO.println("\tspliterator = " + x.spliterator().getClass().getSimpleName() + ", estimateSize() = " + x.spliterator().estimateSize());
      }
      ```

      ```
      class java.util.TreeMap$KeySet
          .stream().limit(1).count() took 0.421209ms
          spliterator = SubMapKeyIterator, estimateSize() = 9223372036854775807
      class java.util.TreeMap$AscendingSubMap$AscendingEntrySetView
          .stream().limit(1).count() took 141.4435ms
          spliterator = IteratorSpliterator, estimateSize() = 9999999
      ```

            Assignee:
            Oli Gillespie
            Reporter:
            Oli Gillespie
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

              Created:
              Updated: