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

[Thomas Stuefe]

On Tue, 30 Apr 2024 09:32:27 GMT, Johan Sjölen <jsjolen at openjdk.org> wrote:

> > Started looking at Treap. More tomorrow.
> > About the Treap. Looking at this closer, I don't understand why you don't follow the more canonical way of implementing a treap:
> > ```
> > * Insert: find lexical position for node x, then do tree rotations until the node priority is in line
> > 
> > * Delete: find node, and as long as its not a leaf, rotate until it is. Then cut node out.
> > ```
> >   
> > Would that not be easier to understand, and faster too? No need for recursion either. We would not need merge and split at all. All we need is insert and delete, after all, we don't need any bulk operations on nodes.
> 
> There seems to be two common ways:
> 
>     * The merge/split thing that I did https://cp-algorithms.com/data_structures/treap.html https://www.geeksforgeeks.org/implementation-of-search-insert-and-delete-in-treap/
> 
>     * The rotation implementation: https://yourbasic.org/algorithms/treap/ https://www.drdobbs.com/windows/treaps-in-java/184410231 https://opendatastructures.org/ods-java/7_2_Treap_Randomized_Binary.html
> 
> 
> Both of these are typically implemented in a recursive manner, though the last link is iterative. I found the merge/split to be easier to understand and since the recursion is bounded on the order of `log(n)` not doing it iteratively is fine by me.
> 
> If it's a deal breaker, I'll rewrite it iteratively using rotations.

Hmm, not a deal breaker, but the recursive merge and splits gives me headaches :=) 

If I am not mistaken, it also seems more expensive? A remove node needs two splits and a merge, both seem to be dependent on tree depth. Removing the node via find-and-rotate-til-its-a-leaf only needs one tree traversal (first find the node, then rotate down until its a leaf).

> 
> > Then, the Treap definitly needs an ASSERT-only verify to check consistency, and that needs to be called periodically.
> 
> Okay, so this is irrelevant of how the treap is implemented? I guess it'd check for:
> 
>     * Non-degeneration of the depth of the tree (approximately log n)
> 
>     * Uniqueness of keys
> 
>     * Anything else??

No, I think that covers it. And then stomp on that thing over and over in gtests, and use this function to validate correctness.

> 
> 
> > TreapNode:
> > Aesthetical nits: Its a mix right now. You have getters, but then the owning Treap has private access and uses that. I see you expose the TreapNode to outside access. In that case, I would prefer if you would use getters and setters consistently, and remove the friend declaration. Style-wise, the code could be more condensed.
> 
> I'll look into that.
> 
> > File naming: I see we have inconsistencies. We name some files "nmtXXX", some not. All code lives inside "nmt", so the prefix could be superfluous. Just a small nit.
> 
> Same here. I think that file names have to be unique across the whole of Hotspot (adlc and libadt being exceptions IIRC), so prepending "nmt" to datastructures seemed like a good way to ensure that. Really, the memory file tracker should still not have the `nmt` prepended regardless.
> 
> Addressing the rest of your comments separately.
> 
> Thanks for having another look.

Sure thing

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

PR Comment: https://git.openjdk.org/jdk/pull/18289#issuecomment-2086221922