On Tue, 2 Dec 2025 15:31:43 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
Tier2 test failure. I will investigate.
java.util.ConcurrentModificationException
at
java.base/java.util.TreeMap$NavigableSubMap$SubMapIterator.prevEntry(TreeMap.java:2068)
at
java.base/java.util.TreeMap$NavigableSubMap$DescendingSubMapEntryIterator.next(TreeMap.java:2156)
at
java.base/java.util.TreeMap$NavigableSubMap$DescendingSubMapEntryIterator.forEachRemaining(TreeMap.java:2166)
at
java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:570)
at
java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:560)
at
java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:635)
at
java.base/java.util.stream.AbstractPipeline.evaluateToArrayNode(AbstractPipeline.java:291)
at
java.base/java.util.stream.ReferencePipeline.toArray(ReferencePipeline.java:652)
at
java.base/java.util.stream.ReferencePipeline.toArray(ReferencePipeline.java:658)
at
org.openjdk.tests.java.util.stream.CollectionAndMapModifyStreamTest.testEntrySetSizeRemove(CollectionAndMapModifyStreamTest.java:164)
at
org.openjdk.tests.java.util.stream.CollectionAndMapModifyStreamTest.testMapEntriesSizeRemove(CollectionAndMapModifyStreamTest.java:155)
-------------
PR Comment: https://git.openjdk.org/jdk/pull/28608#issuecomment-3602932282
