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

[Johan Sjölen]

On Fri, 17 May 2024 08:05:16 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

>> src/hotspot/share/nmt/nmtTreap.hpp line 175:
>> 
>>> 173: #ifdef ASSERT
>>> 174:   void verify_self() {
>>> 175:     const double expected_maximum_depth = log(this->_node_count+1) * 5;
>> 
>> Where did 5 come from, shouldn't this be:
>> 
>> `    const double expected_maximum_depth = log(this->_node_count+1) * (this->_node_count+1)
>> `
>> ?
>
> The depth of a binary tree is on the order of `log(n)`, "the order of" is important here. Essentially, we need some wiggle room. I found that 3 fails, so I bumped it to 5. This did cause me to investigate whether we can pick a tighter bound, and `3.5` fits as long as we perform `ceil` instead of `floor` on the result.
> 
> I'll comment where the constant comes from.

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.

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

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