RFR: Add generations to freeset [v10]

[Kelvin Nilsen]

On Fri, 21 Apr 2023 22:15:50 GMT, Y. Srinivas Ramakrishna <ysr at openjdk.org> wrote:

>> Kelvin Nilsen has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   Add TODO comment for work on recompute_bounds
>
> src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp line 37:
> 
>> 35:   OldCollector
>> 36: };
>> 37: 
> 
> Did you consider avoiding templates and having a FreeSet class with the relevant methods `in_set(idx)`, `add_to_set(idx)`, etc. that you instantiate three of, a mutator, collector, and old_collector. Then, instead of `in_set<Mutator>(idx)`, etc. you would do `mutator.in_set(idx)`, etc. The downside is that we you can't then do assertion checks about membership of other sets (i.e. mutual exclusion checks) inside the methods that add to a specific set, so would need some wrapper machinery for that outside in ShenandoahFreeSet.
> 
> However, the advantage is that such a FreeSet can hide your interval bounds adjustment and checks nicely. Also, that kind of encapsulation allows your `assert_bounds()` to just do `mutator.assert_bounds(); collector.assert_bounds(); ...` etc.
> 
> One question was why the addition of a single element doesn't just do the interval adjustment. 
> 
> 
>    add(x) {
>        if (x < leftmost) {
>            leftmost = x;
>        } else if (x > rightmost) {
>            rightmost = x;
>        } // else isn't extremal
>        set_bit(x);
>     }
> 
> 
> Similarly, the removal of an element also doing the interval adjustment, although more expensive:
> 
> 
>     remove(x) {
>         if (x == leftmost) {
>             for (i = leftmost+1; i <= rightmost; i++) {
>                if (is_set_bit(i)) {
>                   leftmost = i;
>                   break;
>                }
>             }
>             assert(leftmost > x, "Error");
>          } else if (x == rightmost) {
>                for (i = rightmost - 1; i >= leftmost; i--) {
>                    if (is_set_bit(i)) {
>                       rightmost = i;
>                       break;
>                    }
>                }
>                assert(rightmost < x, "Error");
>             }
>         }
>         unset_bit(x);
>     }

I've been reluctant to introduce a FreeSet class, because I think a FreeSets class provides better abstraction in that it allows us to encapsulate that as we move regions from one set to another, we want to automate the transfer of capacity between them.

In the most recent commits, I have tried to incorporate some of your suggestions into an implementation of the FreeSets abstraction.

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

PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1180440966