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

[Kim Barrett]

On Tue, 17 Oct 2023 09:07:26 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 four additional commits since the last revision:
> 
>  - remove unnecessary code markers in comments
>  - use override for virtual test support functions
>  - remove support for allocation base classes
>  - remove IntrusiveList::operator[]

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

> 1332:    * transferred).
> 1333:    */
> 1334:   template<typename FromList, ENABLE_IF(Impl::IsListType<FromList>::value)>

Why is this not using `can_splice<FromList>()`?  In some earlier development version doing something like that
produced much worse compiler error messages than doing the more limited test and leaving the compatibility
checking to the inner call to `splice` with range arguments.  But I think that shouldn't be true now, and this
should be changed to use `can_splice`.  But look at the compiler error messages before making that change.

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

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