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

[Kelvin Nilsen]

On Fri, 1 Mar 2024 15:18:40 GMT, Aleksey Shipilev <shade at openjdk.org> wrote:

>> 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
>
> src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp line 68:
> 
>> 66:   // Count consecutive ones in forward order, starting from start_idx.  Requires that there is at least one zero
>> 67:   // between start_idx and index value (_num_bits - 1), inclusive.
>> 68:   size_t count_leading_ones(ssize_t start_idx) const;
> 
> Does the argument have to me `ssize_t`, not `size_t`? Is this because you want it to be signed?

I'm going to add the following comment at the top of shenandoahFreeSet.hpp:

// The API and internal implementation of ShenandoahSimpleBitMap and ShenandoahRegionPartitions use ssize_t to                      
// represent index, even though index is "inherently" unsigned.  There are two reasons for this choice:                             
//  1. We use -1 as a sentinel value to represent empty partitions.  This same value may be used to represent                       
//     failure to find a previous set bit or previous range of set bits.                                                            
//  2. Certain loops are written most naturally if the iterator, which may hold the sentinel -1 value, can be                       
//     declared as signed and the terminating condition can be < 0.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/17561#discussion_r1509554566