JDK-8166365 : Small immutable collections should provide optimized implementations when possible
  • Type: Sub-task
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Affected Version: 9
  • Priority: P4
  • Status: Resolved
  • Resolution: Fixed
  • Submitted: 2016-09-20
  • Updated: 2017-03-28
  • Resolved: 2017-01-12
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 9
9 b153Fixed
Related Reports
Relates :  
JDK-8172725 - Two test failures in java/util/concurrent/tck
Relates :  
JDK-8172720 - Collections.SingletonList::hashCode not spec-compliant
Description
Most old empty and single-element java.util.Collections classes override hashCode, contains, containsAll, providing optimized implementations, whereas the default implementations inherited from AbstractSet/List/Map typically are implemented using iterators. The constant sized collections in ImmutableCollections (Set0,1,2, Map0,1, List0,1,2) doesn't. This leads to a surprising amount of allocations during startup when using Set.of in place of Collections.singleton etc

Implementing these for at least Set0,1,2 can provably help startup performance of jigsaw after converting from Collections.emptySet/singleton/unmodifiableSets to Set.of in the bootstrap (which has advantages to footprint).
Comments
Good suggestion! I've verified this brings a noticeable speedup in micros, e.g., 1.4x for SetN.containsAll. Mind if I merge this into the patch above (which is more aimed towards improving startup and reduce JITs during bootstrap)?
10-01-2017
For immutable data, fields (both scalar and arrays) should be uniformly marked @Stable, to unock the HotSpot JIT's ability to constant-fold through truly immutable data. (This is not yet possible for merely final fields, because of certain corner cases involving serialization.) diff --git a/src/java.base/share/classes/java/util/ImmutableCollections.java b/src/java.base/share/classes/java/util/ImmutableCollections.java --- a/src/java.base/share/classes/java/util/ImmutableCollections.java +++ b/src/java.base/share/classes/java/util/ImmutableCollections.java @@ -35,6 +35,7 @@ import java.util.function.Function; import java.util.function.Predicate; import java.util.function.UnaryOperator; +import jdk.internal.vm.annotation.Stable; /** * Container class for immutable collections. Not part of the public API. @@ -115,6 +116,7 @@ } static final class List1<E> extends AbstractImmutableList<E> { + @Stable // substructure can be constant-folded private final E e0; List1(E e0) { @@ -143,7 +145,9 @@ } static final class List2<E> extends AbstractImmutableList<E> { + @Stable // substructure can be constant-folded private final E e0; + @Stable // substructure can be constant-folded private final E e1; List2(E e0, E e1) { @@ -176,6 +180,7 @@ } static final class ListN<E> extends AbstractImmutableList<E> { + @Stable // substructure can be constant-folded private final E[] elements; @SafeVarargs @@ -256,6 +261,7 @@ } static final class Set1<E> extends AbstractImmutableSet<E> { + @Stable // substructure can be constant-folded private final E e0; Set1(E e0) { @@ -287,7 +293,9 @@ } static final class Set2<E> extends AbstractImmutableSet<E> { + @Stable // substructure can be constant-folded private final E e0; + @Stable // substructure can be constant-folded private final E e1; Set2(E e0, E e1) { @@ -358,7 +366,9 @@ * @param <E> the element type */ static final class SetN<E> extends AbstractImmutableSet<E> { + @Stable // substructure can be constant-folded private final E[] elements; + @Stable // substructure can be constant-folded private final int size; @SafeVarargs @@ -499,7 +509,9 @@ } static final class Map1<K,V> extends AbstractImmutableMap<K,V> { + @Stable // substructure can be constant-folded private final K k0; + @Stable // substructure can be constant-folded private final V v0; Map1(K k0, V v0) { @@ -541,7 +553,9 @@ * @param <V> the value type */ static final class MapN<K,V> extends AbstractImmutableMap<K,V> { + @Stable // substructure can be constant-folded private final Object[] table; // pairs of key, value + @Stable // substructure can be constant-folded private final int size; // number of pairs MapN(Object... input) {
06-01-2017
Updated patch: http://cr.openjdk.java.net/~redestad/scratch/8166365.01/ As we've adopted Set.of etc to create a more compact representation of the module descriptors at runtime - which was neutral in terms of startup compared to using HashSet - this patch helps brings a small to medium startup improvement by virtue of removing a couple of synthetic accessors that'd be JITted very early and reducing code size of a few methods that'll be heavily exercised during startup.
21-12-2016
Also found that Map0 and Map1 is missing trivial size() overrides
13-10-2016
Patch that implements most trivial contains, hashCode and containsAll methods. (Objects.requireNonNull when the code implicitly would provoke is superfluous; safe to ignore if not deemed worthwhile as a cleanup)
20-09-2016