RFR: 8266789: devirtualize find_node and remove of LinkedList

[Ioi Lam]

On Mon, 10 May 2021 07:49:49 GMT, Xin Liu <xliu at openjdk.org> wrote:

> Devirtualize find, find_node and remove. This patch make both LinkedListImpl
> and SortedLinkedList more generic. If the client doesn't use those member functions,
> it's not necessary to define equals() for the user-defined class E.
> 
> Remove those 3 member functions from the pure interface LinkedList. subclasses
> implement them using regular member functions.

By design, the `LinkedList` API supports polymorphism which is used by the existing code. For example: here we are moving from a `LinkedListImpl` into a `SortedLinkedList`.


void MemBaseline::malloc_sites_to_size_order() {
...
    SortedLinkedList<MallocSite, compare_malloc_size> tmp;
    tmp.move(&_malloc_sites); // _malloc_sites is a LinkedListImpl<...>


It will be odd if you change part of the API to non virtual just so that you can avoid implementing `equals`. I don't think this is the right thing to do.

Regarding the following comments in linkedlist.hpp:


  // Select member function 'bool U::equals(const U&) const' if 'U' is of class
  // type. This works because of the "Substitution Failure Is Not An Error"
  // (SFINAE) rule. Notice that this version of 'equal' will also be chosen for
  // class types which don't define a corresponding 'equals()' method (and will
  // result in a compilation error for them). It is not easily possible to
  // specialize this 'equal()' function exclusively for class types which define
  // the correct 'equals()' function because that function can be in a base
  // class, a dependent base class or have a compatible but slightly different
  // signature.
  template <class U>
  static bool equal(const U& a, const U& b, bool (U::*t)(const U&) const) {
    return a.equals(b);
  }


If you want to implement SFINAE to filter out element types that don't implement `equals`, maybe you can try this:

https://gist.github.com/fenbf/d2cd670704b82e2ce7fd

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

PR: https://git.openjdk.java.net/jdk/pull/3944