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

[Johan Sjölen]

On Wed, 17 Apr 2024 06:40:19 GMT, Thomas Stuefe <stuefe at openjdk.org> wrote:

>> src/hotspot/share/nmt/nmtTreap.hpp line 66:
>> 
>>> 64:     LEQ // <=
>>> 65:   };
>>> 66: 
>> 
>> Both split and merge use recursion, which worries me, since it is not limited in any way I can see. And I think we can rely on the compiler doing tail recursion optimization. Could a degenerated tree cause stack overflows? Can we do this without recursion?
>
> Hint: test with a rng that returns +1 of last return. Lets see how the tree copes with that.

The acceptability of recursion fully depends on the tree being balanced as this leads to a call stack depth of O(log n). split and merge have recursive self-calls in non-tail positions, so I doubt that this will be optimized out.

A treap with a good RNG cannot be worse than something like `4*log_2(n)`.

I see two ways forward:

1. There are iterative ways of creating a Treap, we could use those. It's a bit more work. I'll have to do research.
2. Reify the callstack as a heap-allocated linked list of activation frames and run the code on that. This modifies the linear code to pushing activation frames onto a stack and a bit.

I'll get back here with an example of what that looks like.

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

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