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

[Oli Gillespie]

On Tue, 2 Dec 2025 17:00:54 GMT, Oli Gillespie <ogillespie at openjdk.org> wrote:

>> `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:
> 
>   Fix failing test

Fixed the test failure by skipping that case. The test intentionally modifies the backing map while holding an iterator, which is not safe in general. It got away with it before, but the new implementation reasonably throws CME.
The test only runs on EntrySets, but the equivalent test would already fail on the current `map.tailMap(...).keySet()` implementation, so I _think_ it's expected and reasonable that it now fails for `descendingMap.entrySet()`. Appreciate any second opinions, though.

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

PR Comment: https://git.openjdk.org/jdk/pull/28608#issuecomment-3603104114