`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
-------------
Commit messages:
- Attempt to fix 8372946
Changes: https://git.openjdk.org/jdk/pull/28608/files
Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=28608&range=00
Issue: https://bugs.openjdk.org/browse/JDK-8372946
Stats: 70 lines in 1 file changed: 68 ins; 0 del; 2 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
