-
Type:
Enhancement
-
Resolution: Unresolved
-
Priority:
P4
-
None
-
Affects Version/s: None
-
Component/s: core-libs
TreeMap sub-maps use the default IteratorSpliterator implementation for 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.
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).
```
import java.util.Collection;
import java.util.TreeMap;
void main() {
var map = new TreeMap<Long, String>();
for (long i = 0; i < 10_000_000; i++) map.put(i, Long.toString(i));
test(map.tailMap(0L, false).keySet());
test(map.tailMap(0L, false).entrySet());
}
void test(Collection x) {
IO.println(x.getClass());
long start = System.nanoTime();
x.stream().limit(1).count();
IO.println("\t.stream().limit(1).count() took " + (System.nanoTime() - start) / 1_000_000.0 + "ms");
IO.println("\tspliterator = " + x.spliterator().getClass().getSimpleName() + ", estimateSize() = " + x.spliterator().estimateSize());
}
```
```
class java.util.TreeMap$KeySet
.stream().limit(1).count() took 0.421209ms
spliterator = SubMapKeyIterator, estimateSize() = 9223372036854775807
class java.util.TreeMap$AscendingSubMap$AscendingEntrySetView
.stream().limit(1).count() took 141.4435ms
spliterator = IteratorSpliterator, estimateSize() = 9999999
```
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).
```
import java.util.Collection;
import java.util.TreeMap;
void main() {
var map = new TreeMap<Long, String>();
for (long i = 0; i < 10_000_000; i++) map.put(i, Long.toString(i));
test(map.tailMap(0L, false).keySet());
test(map.tailMap(0L, false).entrySet());
}
void test(Collection x) {
IO.println(x.getClass());
long start = System.nanoTime();
x.stream().limit(1).count();
IO.println("\t.stream().limit(1).count() took " + (System.nanoTime() - start) / 1_000_000.0 + "ms");
IO.println("\tspliterator = " + x.spliterator().getClass().getSimpleName() + ", estimateSize() = " + x.spliterator().estimateSize());
}
```
```
class java.util.TreeMap$KeySet
.stream().limit(1).count() took 0.421209ms
spliterator = SubMapKeyIterator, estimateSize() = 9223372036854775807
class java.util.TreeMap$AscendingSubMap$AscendingEntrySetView
.stream().limit(1).count() took 141.4435ms
spliterator = IteratorSpliterator, estimateSize() = 9999999
```
- links to
-
Review(master)
openjdk/jdk/28608