jdk 8324649: Shenandoah: replace implementation of free set

Several objectives:

Reduce humongous allocation failures by segregating regular regions from humongous regions
Do not retire regions just because an allocation failed within the region if the memory remaining within the region is large enough to represent a LAB
Track range of empty regions in addition to range of available regions in order to expedite humongous allocations
Treat collector reserves as available for Mutator allocations after evacuation completes
Improve encapsulation so as to enable an OldCollector reserve for future integration of generational Shenandoah

We have compared performance of existing FreeSet implementation with the proposed PR over a broad set of performance workloads and see that the impact is mostly neutral.

Comparing 105235.0 metrics from control, 220638.0 from experiment. Compare: 0.589s Most impacted benchmarks | Most impacted metrics

                             Shenandoah/jython |                                          cwr_total


                            Only in experiment |                                    Only in control

             crypto.signverify/trigger_failure |                        crypto.rsa/cmr_thread_roots
            extremem-large-31g/adjust_pointers |       scimark.sparse.small/concurrent_thread_roots
        extremem-large-31g/calculate_addresses |              xml.transform/concurrent_thread_roots
  crypto.signverify/class_unloading_rendezvous |                    mpegaudio/concurrent_weak_roots
                              serial/cmr_total |                        crypto.rsa/ctr_thread_roots

Shenandoah

+5.64% jython/cwr_total p=0.00037 Control: 1.928ms (+/-272.40us) 170 Test: 2.037ms (+/-322.73us) 344

Progress

[x] 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-8324649: Shenandoah: replace implementation of free set (Bug - P4)

Reviewers

William Kemper (@earthling-amzn - Committer) ⚠️ Review applies to 4b1d6a32
Y. Srinivas Ramakrishna (@ysramakrishna - Reviewer) ⚠️ Review applies to b2ba4cf2

Reviewing

Using git

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

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

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 17561

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

Using diff file

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

Webrev

Link to Webrev Comment

Jan 24 '24 16:01 kdnilsen

:wave: Welcome back kdnilsen! 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.

Jan 24 '24 16:01 bridgekeeper[bot]

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

hotspot-gc
shenandoah

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.

Jan 24 '24 16:01 openjdk[bot]

Webrevs

Jan 24 '24 16:01 mlbridge[bot]

I've been trying to understand the reported trigger failure regression on hyperalloc. I cannot reproduce that result. The host on which I'm experimenting apparently has more cores than what runs the pipeline, so I have to push hyperalloc to higher allocation rates and higher memory utilization in order to see any "trigger failures at all". On my host, I see a small number of trigger failures beginning at 6144 KB/s allocation rate with live memory 4096 MB out of heap size 10 GB. On this workload, I see slightly more trigger failures with the original free set implementation than with the new one. Here are the results of all my recent experiments:

Screenshot 2024-01-26 at 10 43 47 AM

Jan 26 '24 18:01 kdnilsen

An earlier comment had requested impact on SpecJBB. I have this information from an internal performance pipeline. Seems to improve critical-jops and max-jops, but also increases P100 jhiccup. Screenshot 2024-01-31 at 10 15 07 AM

Jan 31 '24 18:01 kdnilsen

Many of our internal performance tools are defaulted for comparisons tor GenShen (and on the GenShen branch). Here is a graph showing key specjbb metrics comparing this branch against openjdk/jdk:master:

Jan 31 '24 18:01 earthling-amzn

Would be great to get some feedback also from either @shipilev or @rkennke . Thanks!

Feb 09 '24 21:02 ysramakrishna

@kdnilsen This change now passes all automated pre-integration checks.

ℹ️ This project also has non-automated pre-integration requirements. Please see the file CONTRIBUTING.md for details.

After integration, the commit message for the final commit will be:

8324649: Shenandoah: replace implementation of free set

Reviewed-by: wkemper, ysr, rkennke

You can use pull request commands such as /summary, /contributor and /issue to adjust it as needed.

At the time when this comment was updated there had been 136 new commits pushed to the master branch:

259915168d6656b1b8ddad03c377082d6a5224e5: 8331202: Support for Duration until another Instant
6f7ddbec7d0bc459d44b6518fe1d982eaba7f37b: 8260633: [macos] java/awt/dnd/MouseEventAfterStartDragTest/MouseEventAfterStartDragTest.html test failed
fa3e94d30f11bdccbe290041ae19490ce4940bb1: 8332393: Problemlist compiler/rangechecks/TestArrayAccessAboveRCAfterRCCastIIEliminated.java
a33cb9045b2c0cae7d894715d1484e77b7607de6: 8332098: Add missing @ since tags to jdk.jdi
910d77becd15580296687b00fed085ab106cb2eb: 8331953: ubsan: metaspaceShared.cpp:1305:57: runtime error: applying non-zero offset 12849152 to null pointer
f9f8d0b48057a02923e36c8e11286b57cc72279e: 8332101: Add an @since to StandardOperation:REMOVE in jdk.dynalink
f398cd225012694a586e528936159b6df7b1586c: 8331575: C2: crash when ConvL2I is split thru phi at LongCountedLoop
96c5c3fe75103dc45bc1c3ccce0ab36303121a60: 8329998: Remove double initialization for parts of small TypeArrays in ZObjArrayAllocator
ee4a9d34827166ff9ac04e2375058fdc08e43194: 8321622: ClassFile.verify(byte[] bytes) throws unexpected ConstantPoolException, IAE
ab8d7b0cedfaae124262325cd1d4b59cef996d85: 8324517: C2: crash in compiled code because of dependency on removed range check CastIIs
... and 126 more: https://git.openjdk.org/jdk/compare/b20fa7b48b0f0a64c0760f26188d4c11c3233b61...master

As there are no conflicts, your changes will automatically be rebased on top of these commits when integrating. If you prefer to avoid this automatic rebasing, please check the documentation for the /integrate command for further details.

As you do not have Committer status in this project an existing Committer must agree to sponsor your change. Possible candidates are the reviewers of this PR (@earthling-amzn, @ysramakrishna, @shipilev, @rkennke) but any other Committer may sponsor as well.

➡️ To flag this PR as ready for integration with the above commit message, type /integrate in a new comment. (Afterwards, your sponsor types /sponsor in a new comment to perform the integration).

Feb 09 '24 21:02 openjdk[bot]

I'm working on some performance regressions identified on certain tests. Converting to draft until these are resolved.

Feb 21 '24 17:02 kdnilsen

⚠️ @kdnilsen 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).

Feb 23 '24 18:02 openjdk[bot]

Zero build and others look a bit broken.

Apr 17 '24 17:04 earthling-amzn

@rkennke : Thanks for all your careful feedback. If you could be more specific about loops that might result in quadratic behavior, I'll look more closely. There are some loops within loops, but I'm thinking these are not quadratic because the inner loop bounds are constants.

May 07 '24 14:05 kdnilsen

/integrate

May 16 '24 16:05 kdnilsen

@kdnilsen Your change (at version 32191190cf0b104beb841a15d0d9857f96e67360) is now ready to be sponsored by a Committer.

May 16 '24 16:05 openjdk[bot]

/sponsor

May 16 '24 16:05 ysramakrishna

Going to push as commit dc184f1099e09cef095cd8438d88dd8a1e6f5522. Since your change was applied there have been 136 commits pushed to the master branch:

259915168d6656b1b8ddad03c377082d6a5224e5: 8331202: Support for Duration until another Instant
6f7ddbec7d0bc459d44b6518fe1d982eaba7f37b: 8260633: [macos] java/awt/dnd/MouseEventAfterStartDragTest/MouseEventAfterStartDragTest.html test failed
fa3e94d30f11bdccbe290041ae19490ce4940bb1: 8332393: Problemlist compiler/rangechecks/TestArrayAccessAboveRCAfterRCCastIIEliminated.java
a33cb9045b2c0cae7d894715d1484e77b7607de6: 8332098: Add missing @ since tags to jdk.jdi
910d77becd15580296687b00fed085ab106cb2eb: 8331953: ubsan: metaspaceShared.cpp:1305:57: runtime error: applying non-zero offset 12849152 to null pointer
f9f8d0b48057a02923e36c8e11286b57cc72279e: 8332101: Add an @since to StandardOperation:REMOVE in jdk.dynalink
f398cd225012694a586e528936159b6df7b1586c: 8331575: C2: crash when ConvL2I is split thru phi at LongCountedLoop
96c5c3fe75103dc45bc1c3ccce0ab36303121a60: 8329998: Remove double initialization for parts of small TypeArrays in ZObjArrayAllocator
ee4a9d34827166ff9ac04e2375058fdc08e43194: 8321622: ClassFile.verify(byte[] bytes) throws unexpected ConstantPoolException, IAE
ab8d7b0cedfaae124262325cd1d4b59cef996d85: 8324517: C2: crash in compiled code because of dependency on removed range check CastIIs
... and 126 more: https://git.openjdk.org/jdk/compare/b20fa7b48b0f0a64c0760f26188d4c11c3233b61...master

Your commit was automatically rebased without conflicts.

May 16 '24 16:05 openjdk[bot]

@ysramakrishna @kdnilsen Pushed as commit dc184f1099e09cef095cd8438d88dd8a1e6f5522.

:bulb: You may see a message that your pull request was closed with unmerged commits. This can be safely ignored.

May 16 '24 16:05 openjdk[bot]

jdk jdk copied to clipboard

8324649: Shenandoah: replace implementation of free set

Comparing 105235.0 metrics from control, 220638.0 from experiment. Compare: 0.589s Most impacted benchmarks | Most impacted metrics

Shenandoah

Progress

Issue

Reviewers

Reviewing

Webrev

Webrevs

jdk
jdk copied to clipboard