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

[Johan Sjölen]

On Fri, 19 Apr 2024 11:49:22 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.
>
> I looked around a bit and found a formula for computing the probability of the depth of a treap reaching some particular number `H`. This is assuming a truly random number generation for the priorities. Due to slide 32 in [0]. Both `merge` and `split` have a recursive call depth bounded by the depth of the treap.
> 
> Let's assume that a call stack depth of 200 is acceptable. Each call takes 16 bytes or so of stack space (just counting inputs here). let's say I have woefully underestimated it and it's actually 256 bytes per call. That is `(256 * 200) / 1024 = 50.0KiB` of stack space required.  That is `~10%` of a `512KiB` stack, which is the default on non-AMD64 platforms.
> 
> Here's a transcript of an interactive Python session I used to compute the probability a call stack depth of 200 when we have a billion nodes (`N = 1_000_000_000`):
> 
> 
>>>> H = 200
>>>> N = 1_000_000_000
>>>> math.log(N)
> 20.72326583694641
>>>> H / 21
> 9.523809523809524
>>>> H / 21 / 2
> 4.761904761904762
>>>> c = H / 21 / 2
>>>> 2 * c * math.log(N)
> 197.36443654234677   # Close enough, depth of 197
>>>> N * ( (N/math.e) ** (-1 * c * math.log(c/math.e)))
> 1.3542460158348683e-14
>>>> 
> 
> 
> 
> A probability of `1.35 * 10**(-14)`, that is extremely improbable. Unless I messed something up in my calculations or code, I think that we're good. Still, I'll add a `DEBUG_ONLY` call stack depth counter and assert on it.
> 
> [0] https://cseweb.ucsd.edu//~kube/cls/100/Lectures/lec8.treap/lec8.pdf

and as an empirical data point, the maximum stack depth of merge was 23 when upserting 1,000,000 elements.

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

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