SplayTree has many casts

[rakudrama]

TL;DR: _SplayTree is too slow because it does a cast on almost every pointer traversal.

The SplayTree code has many casts to the constrained type parameter Node.
In the NNBD branch, these are now explicit.
The casts are predominantly in _splay, _splayMin, _splayMax and _remove.
These casts make SplayTreeSet and SplayTreeMap slow compared with other collections.

Excerpt:

abstract class _SplayTree<K, Node extends _SplayTreeNode<K>> {
   ...
  Node? _remove(K key) {
    if (_root == null) return null;
    int comp = _splay(key);
    if (comp != 0) return null;
    Node result = _root!;
    if (_root!.left == null) {
      _root = _root!.right as Node?;
    } else {
      Node? right = _root!.right as Node?;
      // Splay to make sure that the new root has an empty right child.
      _root = _splayMax(_root!.left as Node);
      // Insert the original right child as the right child of the new
      // root.
      _root!.right = right;
    }
    return result;
  }

The Node type parameter is trying to constrain all the nodes in the tree to be of the same type, but fails to do a complete job because of subtyping.

The VM has special versions of _splayMin and _splayMax where the pointer traversal is unchecked. This should not be necessary.

• Does the variance extension solve this problem if Node is in out?
• Should SplayTreeMap and SplayTreeSet be written more simply with sealed independent node classes?

[leafpetersen]

Here's a CL that fixes the type parameterization to eliminate the need for the casts, and hence presumably the need for patched implementations as well. I haven't looked into making the node classes concrete yet. I'll run this CL through golem on Monday and see how it looks.

https://dart-review.googlesource.com/c/sdk/+/143200

cc @lrhn @alexmarkov @munificent