RFR: 8366363: MemBaseline accesses VMT without using lock [v2]

[Casper Norrbin]

On Tue, 2 Sep 2025 09:00:19 GMT, Afshin Zafari <azafari at openjdk.org> wrote:

> We can avoid one, by a new function like: `visit_all()` for the source tree, or for the destination tree use the `hint_node` somehow (that I don't know how, ping @caspernorrbin) in `RBTree::upsert(K, V, Node* hint_node)`

I don't think we would see much improvement iterating differently on the source tree. However, for the destination tree we traverse down the tree for each upsert, which could have quite an impact on large trees. `hint_node` decides where to start searching from, so if we cache the previous node we can avoid this traversal and start directly at the insert point.

To achieve this we could change the return type of `upsert` from `void` to `RBNode<K, V>*`, which is easily done and change the copy-constructor to something like:
```c++
  RBTree(const RBTree& other) : BaseType(), _allocator() {
    static_assert(std::is_copy_constructible<K>::value, "Key type must be copy-constructible when copying a RBTree");
    static_assert(std::is_copy_constructible<V>::value, "Value type must be copy-constructible when copying a RBTree");
    RBNode<K, V>* prev_node = nullptr;
    other.visit_in_order([&](RBNode<K, V>* node) {
      RBNode<K, V>* new_node = this->upsert(node->key(), node->val(), prev_node);
      prev_node = new_node;
      return true;
    });
  }

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

PR Comment: https://git.openjdk.org/jdk/pull/27003#issuecomment-3244565428