RFR: 8372946 - TreeMap sub-map entry spliterator is expensive [v4]

[Oli Gillespie]

> `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 incrementally with one additional commit since the last revision:

  Use Spliterators.spliteratorUnknownSize

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

Changes:
  - all: https://git.openjdk.org/jdk/pull/28608/files
  - new: https://git.openjdk.org/jdk/pull/28608/files/e8bda724..144216ba

Webrevs:
 - full: https://webrevs.openjdk.org/?repo=jdk&pr=28608&range=03
 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=28608&range=02-03

  Stats: 70 lines in 1 file changed: 2 ins; 65 del; 3 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