> `TreeMap` sub-maps use the default `IteratorSpliterator` implementation for > `TreeMap$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. This showed up in my application, where it was trivial to > mitigate by switching to a for loop, but I think the fix is easy enough. > > `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). I'm *assuming* this optimization was > simply missed for the EntryIterator in the original implementation, but I > don't know for sure. > > This patch fixes the issue by providing a custom spliterator for > `EntrySetView`, which is not SIZED. The implementation is copied almost > exactly from the equivalent `KeyIterator` classes in this file > (`SubMapKeyIterator`, `DescendingSubMapKeyIterator`). The only difference is > in `SubMapEntryIterator.getComparator`, for which I copied the implementation > from `TreeMap$EntrySpliterator`. > > > Basic performance test: `map.tailMap(0L, > false).entrySet().stream().limit(1).count()` for a `TreeMap` with > `10_000_000` entries. > > Before (keySet is fast using `SubMapKeyIterator`, entrySet is slow using > `IteratorSpliterator`): > > class java.util.TreeMap$KeySet > .stream().limit(1).count() took 0.046ms > spliterator = SubMapKeyIterator, estimateSize() = 9223372036854775807 > class java.util.TreeMap$AscendingSubMap$AscendingEntrySetView > .stream().limit(1).count() took 218ms > spliterator = IteratorSpliterator, estimateSize() = 9999999 > > > After (entrySet is now fast, using `SubMapEntryIterator`): > > class java.util.TreeMap$KeySet > .stream().limit(1).count() took 0.017ms > spliterator = SubMapKeyIterator, estimateSize() = 9223372036854775807 > class java.util.TreeMap$AscendingSubMap$AscendingEntrySetView > .stream().limit(1).count() took 0.013ms > spliterator = SubMapEntryIterator, estimateSize() = 9223372036854775807
Oli Gillespie has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains three additional commits since the last revision: - Merge remote-tracking branch 'origin/master' into 8372946 - Fix failing test - Attempt to fix 8372946 ------------- Changes: - all: https://git.openjdk.org/jdk/pull/28608/files - new: https://git.openjdk.org/jdk/pull/28608/files/9e669145..e8bda724 Webrevs: - full: https://webrevs.openjdk.org/?repo=jdk&pr=28608&range=02 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=28608&range=01-02 Stats: 783324 lines in 5939 files changed: 403540 ins; 330673 del; 49111 mod Patch: https://git.openjdk.org/jdk/pull/28608.diff Fetch: git fetch https://git.openjdk.org/jdk.git pull/28608/head:pull/28608 PR: https://git.openjdk.org/jdk/pull/28608
