RFR: 8189088: Add intrusive doubly-linked list utility [v7]

[Kim Barrett]

On Mon, 16 Oct 2023 04:38:52 GMT, Kim Barrett <kbarrett at openjdk.org> wrote:

>> Please review this new facility, providing a general mechanism for intrusive
>> doubly-linked lists. A class supports inclusion in a list by having an
>> IntrusiveListEntry member, and providing structured information about how to
>> access that member. A class supports inclusion in multiple lists by having
>> multiple IntrusiveListEntry members, with different lists specified to use
>> different members.
>> 
>> The IntrusiveList class template provides the list management. It is modelled
>> on bidirectional containers such as std::list and boost::intrusive::list,
>> providing many of the expected member types and functions. (Note that the
>> member types use the Standard's naming conventions.) (Not all standard
>> container requirements are met; some operations are not presently supported
>> because they haven't been needed yet.) This includes iteration support using
>> (mostly) standard-conforming iterator types (they are presently missing
>> iterator_category member types, pending being able to include <iterator> so we
>> can use std::bidirectional_iterator_tag).
>> 
>> This change only provides the new facility, and doesn't include any uses of
>> it. It is intended to replace the 4-5 (or maybe more) competing intrusive
>> doubly-linked lists presently in HotSpot.  Unlike most (or perhaps all?) of
>> those alterantives, this proposal provides a suite of unit tests.
>> 
>> An example of a place that I think might benefit from this is G1's region
>> handling. There are various places where G1 iterates over all regions in order
>> to do something with those which satisfy some property (humongous regions,
>> regions in the collection set, &etc). If it were trivial to create new region
>> sublists (and this facility makes that easy), some of these could be turned
>> into direct iteration over only the regions of interest.
>> 
>> Some specific points to consider when reviewing this proposal:
>> 
>> (1) This proposal follows Standard Library API conventions, which differ from
>> HotSpot in various ways.
>> 
>> (1a) Lists and iterators provide various type members, with names per the
>> Standard Library. There has been discussion of using some parts of the
>> Standard Library eventually, in which case this would be important. But for
>> now some of the naming choices are atypical for HotSpot.
>> 
>> (1b) Some of the function signatures follow the Standard Library APIs even
>> though the reasons for that form might not apply to HotSpot. For example, the
>> list pop operations don't return the removed...
>
> Kim Barrett has updated the pull request incrementally with one additional commit since the last revision:
> 
>   const-element nomenclature, other review comments

src/hotspot/share/utilities/intrusiveList.hpp line 87:

> 85:  * * Base is the base class for the list.  This is typically
> 86:  * used to specify the allocation class, such as CHeapObj<>.  The default
> 87:  * is void, indicating the list is not derived from an allocation class.

I'm not certain this Base class for allocation support is actually needed.  I remember one of the alternatives had
(or used to have?) allocation base class support, but haven't found it when I looked recently.  But we have a lot
of these doubly-linked-lists in HotSpot.  Do we have a use-case for a "heap" allocated bare (as in not
embedded in some other object) list?  Removing it would save ~25 lines of code/comments.

src/hotspot/share/utilities/intrusiveList.hpp line 994:

> 992:   const_reference operator[](size_type n) const {
> 993:     return nth_element(cbegin(), cend(), n);
> 994:   }

Do we need these operator[]'s?  Neither std::list nor boost::intrusive::list have such, and I don't think any of the
existing intrusive lists in HotSpot have such either.  Maybe there's no real use-case.  Removal would save
25-30 lines.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1360268160
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1360270735