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

[Kelvin Nilsen]

On Fri, 1 Mar 2024 15:21:58 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.cpp line 50:
> 
>> 48:   size_t element_bits = _bitmap[array_idx];
>> 49:   size_t bit_number = start_idx % _bits_per_array_element;
>> 50:   size_t the_bit = ((size_t) 0x01) << bit_number;
> 
> Here and later, we have a special macro for this, `nth_bit`.

Thanks.  I've replaced all explicit bit manipulation with nth_bit where appropriate.

> src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp line 52:
> 
>> 50:   size_t the_bit = ((size_t) 0x01) << bit_number;
>> 51:   size_t omit_mask = the_bit - 1;
>> 52:   size_t mask = ((size_t) ((ssize_t) -1)) & omit_mask;
> 
> Same, we have `right_n_bits` to generate the masks like this.

Thanks.  I've replaced all explicit bit manipulation with right_n_bits() where appropriate.

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

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