On Tue, 2 Dec 2025 17:00:54 GMT, Oli Gillespie <[email protected]> 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
Changes requested by liach (Reviewer).
src/java.base/share/classes/java/util/TreeMap.java line 2028:
> 2026: }
> 2027:
> 2028: public abstract Spliterator<Map.Entry<K,V>> spliterator();
I don't think you need this huge a patch. I think you should just do:
Suggestion:
public Spliterator<Map.Entry<K,V>> spliterator() {
return Spliterators.spliterator(iterator(),
Spliterator.DISTINCT);
}
Your patch is introducing spliterator behavioral changes unrelated to the
performance regression fix.
-------------
PR Review: https://git.openjdk.org/jdk/pull/28608#pullrequestreview-3706750477
PR Review Comment: https://git.openjdk.org/jdk/pull/28608#discussion_r2728206435
