RFR: 8324649: Shenandoah: replace implementation of free set [v53]

[Kelvin Nilsen]

On Fri, 3 May 2024 16:16:44 GMT, Roman Kennke <rkennke 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 114 commits:
>> 
>>  - Merge remote-tracking branch 'origin/master' into restructure-free-set
>>  - Merge branch 'openjdk:master' into master
>>  - Merge branch 'openjdk:master' into master
>>  - Remove unnecessary call to update_watermark
>>  - Assert progress on find_next and find_prev
>>  - Simplify partition_membership_name by code reuse
>>  - Simplify by combining implemnetations of shrink_interval functions
>>  - Fix NumPartition type
>>    
>>    Beautify the code by changing type of NumPartitions and adding Int and
>>    UInt forms of NumPartitions.
>>  - Refinements to support zero-build compiles
>>  - Fix whitespace
>>  - ... and 104 more: https://git.openjdk.org/jdk/compare/a863ef5d...d6e3546c
>
> src/hotspot/share/gc/shenandoah/shenandoahSimpleBitMap.cpp line 79:
> 
>> 77: }
>> 78: 
>> 79: bool ShenandoahSimpleBitMap::is_forward_consecutive_ones(idx_t start_idx, idx_t count) const {
> 
> Is this a more general version of count_trailing_ones(), i.e. which takes a count (e.g. end-index) instead of implicitely counting until the end of the bitmap? If so, maybe write one to call the other? Also, it looks like here you are using an iterative approach - good!

It would be possible to implement is_forward_consecutive_ones(idx start_idx, idx_t count) as count_leading_ones(start_idx) >= count.  However, that would be less efficient than having the independent implementations.  For example, suppose I want to check whether there are 3 consecutive ones, and I call count_leading_ones() and it happens to count 817 consecutive ones.  I didn't really NEED to count all 817 consecutive ones to find out that I have 3 consecutive ones.

> src/hotspot/share/gc/shenandoah/shenandoahSimpleBitMap.cpp line 109:
> 
>> 107: }
>> 108: 
>> 109: bool ShenandoahSimpleBitMap::is_backward_consecutive_ones(idx_t last_idx, idx_t count) const {
> 
> Same here.

same issue here.

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

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