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

[Chen Liang]

On Mon, 23 Feb 2026 11:16:16 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 using `Spliterators.spliteratorUnknownSize` for `EntrySetView`, marking the size as unknown avoids accidentally iterating the whole thing for simple operations.
>> 
>> 
>> 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):
>> 
>> 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):
>> 
>> 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.115419ms
>> 	spliterator = IteratorSpliterator, estimateSize() = 9223372036854775807
>> 
>> 
>> Behaviour is tested by the test cases added in https://bugs.openjdk.org/browse/JDK-8376698.
>> 
>> CollectionAndMapModifyStreamTest 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, so added descendingMap to the ignore list similar to headMap.
>
> Oli Gillespie has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Use Spliterators.spliteratorUnknownSize

test/jdk/java/util/stream/test/org/openjdk/tests/java/util/stream/CollectionAndMapModifyStreamTest.java line 123:

> 121: 
> 122:         // The following are not lazy
> 123: //        maps.put(TreeMap.class.getName() + ".descendingMap()", () -> new TreeMap<>(content).descendingMap());

Is this test modification still necessary?

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

PR Review Comment: https://git.openjdk.org/jdk/pull/28608#discussion_r2840959875