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

[Thomas Stuefe]

On Wed, 17 Apr 2024 08:14:56 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

> 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.

Yeah that's what I meant. Meant to say "cannot".

> 
> 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.

There is an argument to be made for simplicity too. If you think degeneration is super improbable, it may be okay. But we should probably assert at some depth rather than rely on the potentially missing stack guard.

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

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