RFR: 8324649: Shenandoah: refactor implementation of free set [v14]

[Kelvin Nilsen]

> Several objectives:
> 1. Reduce humongous allocation failures by segregating regular regions from humongous regions
> 2. 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
> 3. Track range of empty regions in addition to range of available regions in order to expedite humongous allocations
> 4. Treat collector reserves as available for Mutator allocations after evacuation completes
> 5. 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

Kelvin Nilsen has updated the pull request with a new target base due to a merge or a rebase. The pull request now contains 60 commits:

 - Remove instrumentation and cleanup magic numbers
   
   Two places, I had used 63 when I should have used
   _bits_per_array_element -1.
 - Address 32-bit compile issues
 - Fix 32-bit size formatting in log messages
 - Fix white space
 - Merge remote-tracking branch 'origin/master' into restructure-free-set
 - Merge branch 'openjdk:master' into master
 - Two bug fixes for better performance
   
   1. Collector reserve size is based on memory available within regions
      rather than the region size (oops).
   
   2. If an attempt to allocate within a region fails and the region has
      already provided the percentage presumed by ShenandoahEvacWaste,
      retire this region.  This is motivated by observations that
      otherwise, we end up with large numbers of regions that have only
      a small amount of memory within them (e.g. 4k) and every allocation
      request has to wade through all of these regions before it eventually
      finds a region that has a sufficiently large amount of available
      memory.  In the original Shenandoah free-set implementation, the
      behavior was to retire the first time an allocation within that
      regions fails, regardless of whether the region has already reached
      the ShenandoahEvacWaste threshold.
 - Fix off-by-one error in is_forward_consecutive_ones()
 - Fix whitespace
 - Bug fixes and performance improvements
   
   1. Correct off-b-one-error in count of trailingones
   2. Speed up search for contiguous regions (for humongous allocations) by
      sliding window instead of initiating new search each time
   3. Bias regular region allocations to favor regions that are already
      partially consumed
   4. Fix bug in move_regions_from_collector_to_mutator which caused some
      non-empty regions to be ignored.
 - ... and 50 more: https://git.openjdk.org/jdk/compare/be2b92bd...1aa5a3e6

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

Changes: https://git.openjdk.org/jdk/pull/17561/files
 Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=17561&range=13
  Stats: 1847 lines in 5 files changed: 1488 ins; 168 del; 191 mod
  Patch: https://git.openjdk.org/jdk/pull/17561.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/17561/head:pull/17561

PR: https://git.openjdk.org/jdk/pull/17561