RFR: Add generations to freeset [v5]

Thu Apr 13 16:56:17 UTC 2023

On Wed, 12 Apr 2023 15:08:29 GMT, Kelvin Nilsen <kdnilsen at openjdk.org> wrote:

>> ShenandoahFreeSet has not yet been modified to deal efficiently with the combination of old-gen and young-gen collection set reserves.  This PR makes changes so that we can distinguish between collector_is_free, old_collector_is_free, and mutator_is_free.  Further, it endeavors to keep each set of free regions tightly packed, so the range of regions representing each set is small.
>> 
>> In its current form, this no longer fails existing regression tests (except for known problems that are being addressed independently)
>
> Kelvin Nilsen has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Remove debug instrumentation

Some more incremental comments.

Will finish the remaining ones in the next batch very soon, but submitting these now as I need to step away briefly.

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp line 991:

> 989:       if ((_old_capacity < to_reserve_old) && (r->is_trash() || (r->affiliation() == ShenandoahAffiliation::FREE))) {
> 990:         clear_mutator_free(idx);
> 991:         set_old_collector_free(idx);

this would read:

  remove_from_mutator(idx);
  add_to_old(idx);

or

    move_from_mutator_to_old(idx)

in the suggested set membership nomenclature.

Also, since we are always dealing with things in `ShenandoahFreeSet`, I'd dispense with the `free` adjective altogether and make the names more compact.

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp line 994:

> 992:         size_t ac = alloc_capacity(r);
> 993:         _capacity -= ac;
> 994:         _old_capacity += ac;

This piecemeal adjustment of capacities following change of set membership indicates that the set abstraction should be pushed down to `old`, `mutator` and `young` (?) subsets, which then carry both membership & capacity that is adjusted at the point of membership changes.

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.cpp line 1002:

> 1000:         // ephemeral objects.  It also delays aging of regions, causing promotion in place to be delayed.
> 1001:         clear_mutator_free(idx);
> 1002:         set_collector_free(idx);

Is there a situation when a region can be both in collector and in mutator free sets?

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp line 37:

> 35:   CHeapBitMap _mutator_free_bitmap;
> 36:   CHeapBitMap _collector_free_bitmap;
> 37:   // We keep the _old_collector regions separate from the young collector regions.  This allows us to pack the old regions

Looks like this comment block needs to move down to line 44.

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp line 48:

> 46:   size_t _mutator_leftmost, _mutator_rightmost;
> 47:   size_t _collector_leftmost, _collector_rightmost;
> 48:   size_t _old_collector_leftmost, _old_collector_rightmost;

Would suggest encapsulation in an interval struct with left & right for each of the three intervals.

At that point, it would make sense to talk about whether these intervals can overlap (because of interspersing of the range of indices in a specific subset), and whether there are invariants/properties of the union of the intervals that can be checked as invariants after these sub-intervals are adjusted.

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp line 64:

> 62:   inline bool is_mutator_free(size_t idx) const;
> 63:   inline bool is_collector_free(size_t idx) const;
> 64:   inline bool is_old_collector_free(size_t idx) const;

Would it be correct to assume (when we are stable between transitions in set membership) that the set of all free regions is tiled by its mutually exclusive subsets `collector_free`, `old_collector_free`, and `mutator_free` ?

Thus, when set membership is not being changed, I'd expect a free region to be in exactly one of these three subsets? If so, then (re `peek` methods below) one might be able to do membership assertion checks before and after transitions in membership (i.e. before removing from one subset and after adding to another subset). That would then avoid having to use `peek` versions of the membership querying methods.

I am trying to get a high level mental model so I can better understand the implementation and usage details. This is likely documented somewhere in `ShenandoahFreeSet`, but I am having trouble locating such documentation in the files I am looking at.

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp line 69:

> 67:   inline bool peek_is_mutator_free(size_t idx) const;
> 68:   inline bool peek_is_collector_free(size_t idx) const;
> 69:   inline bool peek_is_old_collector_free(size_t idx) const;

I can imagine needing these during transitions in membership. I am wondering though if the assertion checking can be refactored in such a manner that we don't need these `peek` versions at all. They have a kind of ad-hoc feel to them, as if we were shoe-horning assertion checks in the wrong place(s). See suggestion/comments further above.

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp line 77:

> 75:   inline void clear_mutator_free(size_t idx);
> 76:   inline void clear_collector_free(size_t idx);
> 77:   inline void clear_old_collector_free(size_t idx);

Re an earlier comment, I suggest use of mathematical set nomenclature here for ease of reading, i.e. `set_x_free` -> `add_to_x`, `clear_x_free` -> `remove_from_x`, etc. with suitable assertion checks in those methods (before removal and after addition) that verify global steady-state invariants (under lock, I assume).

src/hotspot/share/gc/shenandoah/shenandoahFreeSet.hpp line 147:

> 145:   void print_on(outputStream* out) const;
> 146: 
> 147:   void reserve_regions(size_t young_reserve, size_t old_reserve);

Documentation comment, preferably here, but if not then in the implementation as a block header.

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

Changes requested by ysr (Author).

PR Review: https://git.openjdk.org/shenandoah/pull/250#pullrequestreview-1383762723
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1165772465
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1165775161
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1165769619
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1165758963
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1165762097
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1165747592
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1165754694
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1165757749
PR Review Comment: https://git.openjdk.org/shenandoah/pull/250#discussion_r1165780321