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 two AtomicReference and two protected by double-checked locking under concurrent access by all threads:

Benchmark                                      Mode  Cnt      Score      Error   Units
StableBenchmark.atomic                        thrpt   10    259.478 ?   36.809  ops/us
StableBenchmark.dcl                           thrpt   10    225.710 ?   26.638  ops/us
StableBenchmark.stable                        thrpt   10   4382.478 ? 1151.472  ops/us <- StableValue significantly faster

Performance compared to static variables protected by AtomicReference, class-holder idiom holder, and double-checked locking (all threads):

Benchmark                                      Mode  Cnt      Score      Error   Units
StableStaticBenchmark.atomic                  thrpt   10   6487.835 ?  385.639  ops/us
StableStaticBenchmark.dcl                     thrpt   10   6605.239 ?  210.610  ops/us
StableStaticBenchmark.stable                  thrpt   10  14338.239 ? 1426.874  ops/us
StableStaticBenchmark.staticCHI               thrpt   10  13780.341 ? 1839.651  ops/us

Performance for stable lists (thread safe) in both instance and static contexts whereby we access a single value compared to ArrayList instances (which are not thread-safe) (all threads):

Benchmark                                      Mode  Cnt      Score      Error   Units
StableListElementBenchmark.instanceArrayList  thrpt   10   5812.992 ? 1169.730  ops/us
StableListElementBenchmark.instanceList       thrpt   10   4818.643 ?  704.893  ops/us
StableListElementBenchmark.staticArrayList    thrpt   10   7614.741 ?  564.777  ops/us
StableListElementBenchmark.staticList         thrpt   10  13584.829 ? 1579.200  ops/us

Performance when summing lists:

Benchmark                                      Mode  Cnt      Score      Error   Units
StableListSumBenchmark.instanceArrayList      thrpt   10     19.873 ?    0.961  ops/us
StableListSumBenchmark.instanceList           thrpt   10      4.707 ?    0.196  ops/us <- Slow
StableListSumBenchmark.instanceStored         thrpt   10      9.874 ?    1.860  ops/us
StableListSumBenchmark.staticArrayList        thrpt   10     21.358 ?    0.973  ops/us
StableListSumBenchmark.staticList             thrpt   10      7.741 ?    0.262  ops/us <- Slow
StableListSumBenchmark.staticStored           thrpt   10     12.267 ?    0.248  ops/us

Performance for stable maps in a static context compared to a ConcurrentHashMap (all threads):

Benchmark                                      Mode  Cnt      Score      Error   Units
StablePropertiesBenchmark.chmRaw              thrpt   10   2102.393 ?  448.307  ops/us
StablePropertiesBenchmark.stableRaw           thrpt   10   3119.437 ?  148.899  ops/us

All figures above are from local tests on a Mac M1 laptop and should only be constructed as indicative figures.

Implementation details

There are some noteworthy implementation details in this PR:

A field is trusted if it is declared as a final StableValue. Previously, the determination of trustworthiness was connected to the class in which it was declared (e.g. is it a record or a hidden class). In order to grant such trust, there are extra restrictions imposed on reflection and sun.misc.Unsafe usage for such declared StableValue fields. This is similar to how record classes are handled.
In order to allow plain memory semantics for read operations across threads (rather than volatile semantics which is slower and which is normally required for double-checked-locking access), we perform a freeze operation before an object becomes visible to other threads. This will prevent store-store reordering and hence, we are able to guarantee complete objects are always seen even under plain memory semantics.
In collections with StableValue elements/values, a transient StableValue view backed by internal arrays is created upon read operations. This improves initialization time, reduces storage requirements, and improves access performance as these transient objects are eliminated by the C2 compiler.

Progress

[ ] Change must be properly reviewed (1 review required, with at least 1 Reviewer)
[x] Change must not contain extraneous whitespace
[x] Commit message must refer to an issue

Issue

JDK-8330465: Stable Values and Collections (Internal) (Enhancement - P3)

Reviewing

Using git

Checkout this PR locally:
$ git fetch https://git.openjdk.org/jdk.git pull/18794/head:pull/18794
$ git checkout pull/18794

Update a local copy of the PR:
$ git checkout pull/18794
$ git pull https://git.openjdk.org/jdk.git pull/18794/head

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 18794

View PR using the GUI difftool:
$ git pr show -t 18794

Using diff file

Download this PR as a diff file:
https://git.openjdk.org/jdk/pull/18794.diff

Webrev

Link to Webrev Comment

Apr 16 '24 11:04 minborg

:wave: Welcome back pminborg! A progress list of the required criteria for merging this PR into master will be added to the body of your pull request. There are additional pull request commands available for use with this pull request.

Apr 16 '24 11:04 bridgekeeper[bot]

❗ This change is not yet ready to be integrated. See the Progress checklist in the description for automated requirements.

Apr 16 '24 11:04 openjdk[bot]

@minborg The following labels will be automatically applied to this pull request:

compiler
core-libs
hotspot-compiler
security

When this pull request is ready to be reviewed, an "RFR" email will be sent to the corresponding mailing lists. If you would like to change these labels, use the /label pull request command.

Apr 16 '24 11:04 openjdk[bot]

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

Patterns:

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)
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.
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:

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

Apr 17 '24 14:04 liach

Question:

Will we ever try to expose the stable benign race model to users?

Will we ever try to inline the stable values in object layout like a stable field?

I think there is little or no upside in exposing the benign race. It would also be difficult to assert the invariant, competing objects are functionally equivalent. So, I think no.
In a static context, the stable value will be inlined (or rather constant-folded). So we are partly already there. For pure instance contexts, I have some ideas about this but it is non-trivial.

Apr 17 '24 15:04 minborg

⚠️ @minborg This pull request contains merges that bring in commits not present in the target repository. Since this is not a "merge style" pull request, these changes will be squashed when this pull request in integrated. If this is your intention, then please ignore this message. If you want to preserve the commit structure, you must change the title of this pull request to Merge <project>:<branch> where <project> is the name of another project in the OpenJDK organization (for example Merge jdk:master).

Apr 18 '24 16:04 openjdk[bot]

@minborg Just curious, why are you adding holder-in-holder benchmark cases?

Apr 24 '24 14:04 liach

@minborg Just curious, why are you adding holder-in-holder benchmark cases?

I'd like to test the transitive constant folding capabilities.

Apr 24 '24 14:04 minborg

I've run some benchmarks on various platforms for static fields (higher is better):

Apr 24 '24 14:04 minborg

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?

Apr 24 '24 15:04 liach

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.

Good suggestion. I've added such a test. It turns out the performance is great there too.

Apr 25 '24 07:04 minborg

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?

Good question. In one of the previous prototypes, we accepted a class literal that would enable the use of primitive arrays. We now think that we can achieve the same thing once Valhalla is integrated. This will allow not just StableValue to use primitive flattened arrays but also a large number of other constructs like ArrayList.

One thing we are considering is adding support for stable multi-dimensional reference arrays. For an overwhelming majority of the use cases, we would be able to eliminate the second layer of indirection that is there for arrays of rank > 1.

Apr 25 '24 07:04 minborg

Here are some figures for various platforms where we compare AtomicReference, double-checked locking holder, and StableValue using instance variables and where we iterate and sum 20 values from said constructs:

Note: The figures should be taken with a grain of salt pending a deeper analysis.

Apr 25 '24 07:04 minborg

/label remove security

May 01 '24 12:05 wangweij

@wangweij The security label was successfully removed.

May 01 '24 12:05 openjdk[bot]

Webrevs

May 14 '24 14:05 mlbridge[bot]

I have reworked the stable collections so that we create StableValues on demand and store them in a lazily populated backing array. This improved performance significantly as well as gave us improved startup times (only one array needs to be created upfront). Also, StableValue is now monomorphic. On the flip side is the fact that slightly more memory is needed.

May 15 '24 15:05 minborg

Here are some updated benchmark graphs where we sum two instance variables of different sorts (higher is better):

May 16 '24 14:05 minborg

Mailing list message from Olexandr Rotan on compiler-dev:

Is it possible to make stable values and collections Serializable? I see various applications for this feature in entity classes as a way to preserve immutability of entity fields and at the same time not break current JPA specifications. It is a *very* common task in commercial development. Current workarounds lack either thread safety or performance, and this looks like a really good solution for both of those problems. However, unless StableValue is serializable, it is really unlikely that JPA will adopt them (we have precedent with Optional).

On Thu, May 16, 2024 at 5:07?PM Per Minborg <pminborg at openjdk.org> wrote:

-------------- next part -------------- An HTML attachment was scrubbed... URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20240516/7fa869a5/attachment-0001.htm>

May 16 '24 18:05 mlbridge[bot]

Mailing list message from Olexandr Rotan on compiler-dev:

Is it possible to make stable values and collections Serializable? I see various applications for this feature in entity classes as a way to preserve immutability of entity fields and at the same time not break current JPA specifications. It is a very common task in commercial development. Current workarounds lack either thread safety or performance, and this looks like a really good solution for both of those problems. However, unless StableValue is serializable, it is really unlikely that JPA will adopt them (we have precedent with Optional).

On Thu, May 16, 2024 at 5:07?PM Per Minborg wrote:

-------------- next part -------------- An HTML attachment was scrubbed... URL: https://mail.openjdk.org/pipermail/compiler-dev/attachments/20240516/7fa869a5/attachment-0001.htm

Serializable is on the list to explore.

May 17 '24 06:05 minborg

Here are some results of a recently added benchmark that uses a memorized function (with 0 and 1 as input values):

See test/micro/org/openjdk/bench/java/lang/stable/MemoizedFunctionBenchmark.java for details

May 17 '24 09:05 minborg

We are considering another implementation with less complexity. So, for now, thank you for all the feedback so far. We will try to make sure to carry over them to a new PR.

May 21 '24 12:05 minborg

Thanks for the insights. Also, I wonder what is a good amount of metadata you are considering, as original stable values only take one possible representation out of all to indicate a mutable state, much lighter in weight compared to the current implementation, which takes many bits; this might disencourage StableValue use.

May 21 '24 14:05 liach

@minborg this pull request can not be integrated into master due to one or more merge conflicts. To resolve these merge conflicts and update this pull request you can run the following commands in the local repository for your personal fork:

git checkout stable-value
git fetch https://git.openjdk.org/jdk.git master
git merge FETCH_HEAD
# resolve conflicts and follow the instructions given by git merge
git commit -m "Merge master"
git push

Jun 06 '24 16:06 openjdk[bot]

A new PR will be made available shortly.

Jun 10 '24 11:06 minborg

jdk jdk copied to clipboard

8330465: Stable Values and Collections (Internal)

Stable Values & Collections (Internal)

Summary

Goals

Performance

Implementation details

Progress

Issue

Reviewing

Webrev

Webrevs

jdk
jdk copied to clipboard