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

[Thomas Stuefe]

On Wed, 4 Oct 2023 03:36:50 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:
> 
>   add IntrusiveListEntry::is_attached()

Cursory glance.

The list hook element costs 16 bytes on 64-bit. Would it be possible to get a single-linked variant? For many (most?) cases, traversing backward or random access deletion is not needed.

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

> 67:  *
> 68:  * * entry_member is a pointer to class member referring to the
> 69:  * IntrusiveListEntry subobject of T used by this list.

nit, "subobject" confused me a little. Maybe "element" or "member" ?

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

PR Review: https://git.openjdk.org/jdk/pull/15896#pullrequestreview-1657025470
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1345453689