RFR: 8345314: Add a red–black tree as a utility data structure [v14]

[Casper Norrbin]

On Tue, 21 Jan 2025 20:11:21 GMT, Gerard Ziemski <gziemski at openjdk.org> wrote:

> I remember Lois asked, during your presentation at the staff meeting, how to change our existing code to start using your RBTree and your answer was a single line change. Could you please remind me what that line was? I'd like to benchmark the new RBTree using my NMT benchmark to see whether there is any performance difference from Treap.


To swap out to the red-black tree, you can change these two lines in `vmatree.hpp`:
```c++
  using VMATreap = TreapCHeap<position, IntervalChange, PositionComparator>;
  using TreapNode = VMATreap::TreapNode;

to:
```c++
  using VMATreap = RBTreeCHeap<position, IntervalChange, PositionComparator, mtNMT>;
  using TreapNode = VMATreap::RBNode;


The internal variable names would still refer to the treap, but for testing that shouldn't matter.
If you want the VMATree gtests to compile, you need to do two more things:
Add `friend class NMTVMATreeTest;` to the `RBTree` class.
Change `treap.find(treap._root, key);` to `treap.find_node(key);` in `test_vmatree.cpp:54`

I have also done some benchmarking on my own only comparing the two trees in isolation. In the worst case scenario, which is only sequential inserts/removals, the red-black tree was a bit slower (~10%), but with more balanced operations, the treap was slower. Hopefully you will find similar results. I don't know how large of a % of NMT overhead is tree operations. If it's not high it shouldn't affect overall performance much in either direction.

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

PR Comment: https://git.openjdk.org/jdk/pull/22360#issuecomment-2607127293