RFR: 8312132: Add tracking of multiple address spaces in NMT [v89]

[Gerard Ziemski]

On Fri, 17 May 2024 11:24:10 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> This made me a bit curious about other trees bounds. An RB-tree has a bound of `2log_2(N + 1)`, so I decided to find the bound for our treap in base-2 log. Turns out we're at `2.5*log_2(N + 1)`, so very close to the RB-tree.
>
>>#  assert(maximum_depth_found <= ceil(expected_maximum_depth)) failed: depth unexpectedly large, was: 57, expected: 56
> 
> Apparently there's a very small chance of it being worse than that :-). I'll adjust the expectations here a bit more.

The absolute worst case scenario is O(n) and the best is O(log(n)) and since we use random numbers to balance the tree it should be closer to the best case, correct?

I'm just wondering whether we really want:

`    assert(maximum_depth_found <= (int)expected_maximum_depth, "depth unexpectedly large");
`

We cannot guarantee that it will not be triggered at some point in the future, and if it does, how useful it will be for someone to investigate? I would consider printing out a warning instead of using `assert` here.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/18289#discussion_r1605195124