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

Thu Oct 5 10:54:18 UTC 2023

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()

Hi Kim!

I've now read the initial documentation string in the header file. I feel like this is a very well-written and formal text whose audience is someone intimately familiar with C++, but who doesn't know anything about intrusive linked lists. Unfortunately, Hotspot devs are basically the opposite of that. We know intrusive linked lists and when to reach for them but are not C++ standard experts. If you provide us with a rich API, short and concise documentation and code samples on how to use the API, then we're likely to be very happy! Also, since we're not only users, but also future maintainers of this code, some explanatory documentation of the internals are often very appreciated.

I'm not asking you to be so informal as to be incorrect, but I think that a lot of this writing can be cut down, especially since we can always read the code if we have any specific questions. This is perhaps more of a taste thing, but I don't mind using some active voice when describing how to use the API.

I'm still going through this, but I wanted to get these thoughts posted as this PR is quite large and I don't want to forget anything.

Thank you for your efforts on this.

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

> 37: class IntrusiveListImpl;
> 38: 
> 39: /**

Most long form comments I see in Hotspot do not use `/** */` and instead uses `//`, can the style be changed to this?

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

> 43:  * when inserting objects into the list or referencing list objects,
> 44:  * and removing an object from a list need not involve destroying the
> 45:  * object.

>As a result, [...]

We know what an intrusive linked list is, we have at least 5 of them :)!

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

> 61:  * in a list are externally managed, rather than being embedded values
> 62:  * in the list, the actual type of such objects may be more specific
> 63:  * than the list's element type.

Okay, is there a reason that this shouldn't be true? I assume that what you're saying is that we can have:

```c++
struct Super { IntrusiveListEntry entry; };
struct SubA : public Super {};
struct SubB : public Super {};
void foo() {
  IntrusiveList<Super> my_list; // This my_list may contain SubA, SubB, and Super
}

And this seems like it should be true for any reasonable intrusive list in C++.

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

> 64:  *
> 65:  * * T is the class of the elements in the list.  Must be a possibly
> 66:  * const-qualified class type.

I don't know what it means to be a 'possibly const-qualified class type'.

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

> 71:  * * has_size determines whether the list has a size()
> 72:  * operation, returning the number of elements in the list.  If the
> 73:  * operation is present, it has constant-time complexity.  The default

Surely that depends on the time complexity of the operation?

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

> 76:  * * Base is the base class for the list.  This is typically
> 77:  * used to specify the allocation class.  The default is void, indicating
> 78:  * no allocation class for the list.

What's an allocation class?

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

> 85:  * iterators and access to const-qualified elements.  A const object cannot be
> 86:  * added to a list whose value type is not const-qualified, as that would be
> 87:  * an implicit casting away of the const qualifier.

Okay, I feel like this can be shortened signifcantly:

> A const-qualified type can be part of an IntrusiveList, then you only get const iterators and access to const elements. If you use a non-const type, then you can get both const and non-const iterators and access to elements. You can't add const values to a non-const list, as that would be implicitly casting away the const qualifier.

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

> 91:  * argument, a const reference to a removed element.  This function should
> 92:  * "dispose" of the argument object when called, such as by deleting the
> 93:  * object.  The result of the call is ignored.

A lot of this information is more easily seen by reading the code. Saying something like:

>Operations that remove elements from a list take a disposer function as an argument. A disposer should free up the memory associated with the object.

Shorter documentation is quicker to read and easier to maintain.

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

> 97:  * specialization of the IntrusiveList class, e.g.
> 98:  *
> 99:  * <code>

We don't need these tags

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

PR Review: https://git.openjdk.org/jdk/pull/15896#pullrequestreview-1659471376
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1347183337
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1347196105
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1347192667
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1347193270
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1347194449
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1347195267
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1347200031
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1347206121
PR Review Comment: https://git.openjdk.org/jdk/pull/15896#discussion_r1347194735