RFR: 8330465: Stable Values and Collections (Internal)

Chen Liang liach at openjdk.org
Tue May 14 14:14:21 UTC 2024 

On Tue, 16 Apr 2024 11:47:23 GMT, Per Minborg <pminborg at openjdk.org> wrote:

> # Stable Values & Collections (Internal)
> 
> ## Summary
> This PR proposes to introduce an internal _Stable Values & Collections_ API, which provides immutable value holders where elements are initialized _at most once_. Stable Values & Collections offer the performance and safety benefits of final fields while offering greater flexibility as to the timing of initialization.
> 
> ## Goals
>  * Provide an easy and intuitive API to describe value holders that can change at most once.
>  * Decouple declaration from initialization without significant footprint or performance penalties.
>  * Reduce the amount of static initializer and/or field initialization code.
>  * Uphold integrity and consistency, even in a multi-threaded environment.
>  
> For more details, see the draft JEP: https://openjdk.org/jeps/8312611
> 
> ## Performance 
> Performance compared to instance variables using an `AtomicReference` and one protected by double-checked locking under concurrent access by 8 threads:
> 
> 
> Benchmark                       Mode  Cnt  Score   Error  Units
> StableBenchmark.instanceAtomic  avgt   10  1.576 ? 0.052  ns/op
> StableBenchmark.instanceDCL     avgt   10  1.608 ? 0.059  ns/op
> StableBenchmark.instanceStable  avgt   10  0.979 ? 0.023  ns/op <- StableValue (~40% faster than DCL)
> 
> 
> Performance compared to static variables protected by `AtomicReference`, class-holder idiom holder, and double-checked locking (8 threads):
> 
> 
> Benchmark                       Mode  Cnt  Score   Error  Units
> StableBenchmark.staticAtomic    avgt   10  1.335 ? 0.056  ns/op
> StableBenchmark.staticCHI       avgt   10  0.623 ? 0.086  ns/op
> StableBenchmark.staticDCL       avgt   10  1.418 ? 0.171  ns/op
> StableBenchmark.staticList      avgt   10  0.617 ? 0.024  ns/op
> StableBenchmark.staticStable    avgt   10  0.604 ? 0.022  ns/op <- StableValue ( > 2x faster than `AtomicInteger` and DCL)
> 
> 
> Performance for stable lists in both instance and static contexts whereby the sum of random contents is calculated for stable lists (which are thread-safe) compared to `ArrayList` instances (which are not thread-safe) (under single thread access):
> 
> 
> Benchmark                                     Mode  Cnt  Score   Error  Units
> StableListSumBenchmark.instanceArrayList      avgt   10  0.356 ? 0.005  ns/op
> StableListSumBenchmark.instanceList           avgt   10  0.373 ? 0.017  ns/op <- Stable list
> StableListSumBenchmark.staticArrayList        avgt   10  0.352 ? 0.002  ns/op
> StableListSumBenchmark.staticList             avgt   10  0.356 ? 0.00...

Glad to see this! Some API design remarks.

Also, I want to mention a few important differences between `@Stable` and Stable Values:

Patterns:
1. Benign race (does not exist in StableValue API): multiple threads can create an instance and upload, any non-null instance is functionally equivalent so race is ok (seen in most of JDK)
2. compareAndSet (setIfUnset): multiple threads can create instance, only one will succeed in uploading; usually for when the instance computation is cheap but we want single witness.
3. atomic computation (computeIfUnset): only one thread can create instance which will be witnessed by other threads; this pattern ensures correctness and prevents wasteful computation by other threads at the cost of locking and lambda creation.

Allocation in objects: `@Stable` field is local to an object but `StableValue` is another object; thus sharing strategy may differ, as stable fields are copied over but StableValue uses a shared cache (which is even better for avoiding redundant computation)

Question:
1. Will we ever try to expose the stable benign race model to users?
2. Will we ever try to inline the stable values in object layout like a stable field?

Just curious, can you test other samples, like `StableValue<List<Object>>` where the contained `List` is an immutable list from `List.of` factories? I think that would be a meaningful case too.

Also on a side note, I just realized there's no equivalent of `@Stable int[]` etc. stable primitive arrays exposed, yet immutable arrays will be useful. Is the Frozen Arrays JEP still active, or will this Stable Values consider expose stable primitive arrays?

src/java.base/share/classes/java/lang/reflect/Field.java line 179:

> 177:         AccessibleObject.checkPermission();
> 178:         // Always check if the field is a final StableValue
> 179:         if (StableValue.class.isAssignableFrom(type) && Modifier.isFinal(modifiers)) {

This doesn't protect the Stable Collections.

src/java.base/share/classes/java/util/ImmutableCollections.java line 173:

> 171:                             .map(Objects::requireNonNull)
> 172:                             .toArray();
> 173:                     return keys instanceof EnumSet

We can move this instanceof check before the stream call.

src/java.base/share/classes/java/util/ImmutableCollections.java line 1457:

> 1455:         private final V[] elements;
> 1456:         @Stable
> 1457:         private final AuxiliaryArrays aux;

Is java.util not trusted package so we need `@Stable`?

src/java.base/share/classes/java/util/ImmutableCollections.java line 1519:

> 1517:     // Internal interface used to indicate the presence of
> 1518:     // the computeIfUnset method that is unique to StableMap and StableEnumMap
> 1519:     interface HasComputeIfUnset<K, V> {

Suggestion:

    interface HasComputeIfUnset<K, V> extends Map<K, StableValue<V>> {


So maybe we can use pattern matching like:

Map<K, StableValue<V>> map = ...
if (map instanceof HasComputeIfUnset<K, V> hciu) {
    // stuff
}

src/java.base/share/classes/java/util/ImmutableCollections.java line 1668:

> 1666:         @Override
> 1667:         public Set<Map.Entry<K, StableValue<V>>> entrySet() {
> 1668:             return new AbstractSet<>() {

Maybe we want to do `AbstractImmutableSet` like in #18522.

src/java.base/share/classes/java/util/ImmutableCollections.java line 1677:

> 1675:     static final class StableEnumMap<K extends Enum<K>, V>
> 1676:             extends AbstractImmutableMap<K, StableValue<V>>
> 1677:             implements Map<K, StableValue<V>>, HasComputeIfUnset<K, V> {

Note that this might be a navigable map, as enums are comparable.

src/java.base/share/classes/java/util/ImmutableCollections.java line 1855:

> 1853:                 @Override
> 1854:                 public boolean equals(Object o) {
> 1855:                     return o == this;

These implementations are violations to the Set contracts; Set's hash code should be its elements' sum (thus an entry set's hash code is equivalent to its map's hash) and equals should check if all elements are present. This also makes two entry sets from two `entrySet()` calls not equal (at least before valhalla)

src/java.base/share/classes/jdk/internal/lang/StableValue.java line 223:

> 221:     /**
> 222:      * {@return an unmodifiable, shallowly immutable, thread-safe, value-stable,
> 223:      * {@linkplain Map } where the {@linkplain java.util.Map#keySet() keys}

Suggestion:

     * {@linkplain Map} where the {@linkplain java.util.Map#keySet() keys}

src/java.base/share/classes/jdk/internal/lang/StableValue.java line 279:

> 277:     static <V> V computeIfUnset(List<StableValue<V>> list,
> 278:                                 int index,
> 279:                                 IntFunction<? extends V> mapper) {

Hmm, these APIs seem unintuitive and error-prone to users. Have you studied the use case where for one stable list/map, there are distinct initialization logics for different indices/keys so that they support different mappers for the same list/map? I cannot recall on top of my head. 

If we drop said ability and restrict mappers to the list/map creation, the whole thing will be much cleaner, and it's a better way to avoid capturing lambdas as well. Users can still go to individual stable values and use functional creation if they really, really want that functionality.

src/java.base/share/classes/jdk/internal/lang/stable/StableUtil.java line 90:

> 88:         // to provide protection against store/store reordering.
> 89:         // See VarHandle::releaseFence
> 90:         UNSAFE.storeFence();

Can we use a storeStoreFence like in #18505?

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

PR Review: https://git.openjdk.org/jdk/pull/18794#pullrequestreview-2004581002
PR Comment: https://git.openjdk.org/jdk/pull/18794#issuecomment-2061350087
PR Comment: https://git.openjdk.org/jdk/pull/18794#issuecomment-2075216073
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1581828312
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1581828721
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1598676330
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1581829255
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1581829489
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1567930612
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1599908641
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1581830287
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1567944454
PR Review Comment: https://git.openjdk.org/jdk/pull/18794#discussion_r1581830884

More information about the compiler-dev mailing list