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

[Roman Kennke]

On Tue, 9 Apr 2024 01:41:49 GMT, Y. Srinivas Ramakrishna <ysr at openjdk.org> wrote:

>> If consensus is we should not re-invent the wheel, I'll make an effort to make the additional changes required to use BitMap instead of ShenandoahSimpleBitMap.
>
> Thank you Kelvin:
> 
>> Here's a rough outline of the differences between ShenandoahSimpleBitMap and src/hotspot/share/utilities/bitMap.*
>> 
>> 1. ShenandoahSimpleBitMap finds next bit in the forward and backward direction.  BitMap only searches in forward direction.  We use backward searches when we prefer to pack certain types of objects into the high end of the heap.
> 
> BitMap could be extended to optionally search backwards as well? (In fact as I realized after I wrote this, BitMap already has that capability, I think, or at least has an API that does so.)
> 
>> 2. ShenandoahSimpleBitMap also searches for clusters of bits, to facilitate efficient satisfaction of humongous allocation requests.  BitMap only searches for a single bit.  We could add this capability to BitMap.
> 
> I agree.
> 
>> 3. If we were to generalize BitMap to handle reverse searches, this may have far-reaching impact on the API.   The type of results and idx_t (typedef size_t).  When we do backward searches, ShenandoahSimpleBitMap treats -1 as the sentinel NOT_FOUND value.
> 
> I think that's easy to fix. Backwards searches from index x (exclusive), can use `find_last_set_bit(idx_t 0, idx_t x)`. If you get back `x` that indicates NOT_FOUND:
> 
> 
>   // Return the index of the last set (or clear) bit in the range [beg, end),
>   // or end if none found.
>   // precondition: beg and end form a valid range for the bitmap.
>   idx_t find_last_set_bit(idx_t beg, idx_t end) const;
>   idx_t find_last_clear_bit(idx_t beg, idx_t end) const;
> 
> 
> You can use a wrapper to return `-1` if you want for your specific use case.
> 
> Would that work?
> 
> PS: I have not looked at `cluster of bits`, but I am guessing it's not a bit but a specific pattern/sequence you are looking for. I'll take a look at the code of `ShenandoahSimpleBitMap` to understand.

I'd say, let's keep the duplicate ShSimpleBitMap for now, but make a note (bug-entry?) to attempt a merge later on. We can help that by trying to keep the style, types, algorithmic and API approaches similar.

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

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