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

[Johan Sjölen]

On Fri, 10 May 2024 11:21:51 GMT, Thomas Stuefe <stuefe at openjdk.org> wrote:

>> Johan Sjölen has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   Some style
>
> src/hotspot/share/nmt/nmtTreap.hpp line 373:
> 
>> 371:     }
>> 372:   }
>> 373: };
> 
> `visit_range_in_order` looks okay, though it surely is a bit of a brain teaser. So the first half of the algorithm walks the outer-left flank of whatever the current head is, up to the point where we "stick a toe outside the range", then it repeats that part, basically, with the right node, which could be a way in, which is why we again have to walk the left flank.
> 
> I assume this is based on a paper, but trust you to have checked that. However, I would really like regression testing for this. Lots of range checks in gtest, please (can just be tacked onto what I did ask you for yesterday).

If you look at the `visit_in_order` function you see the typical iterative algorithm for visiting a binary tree in order, this is modified to being able to shorten the search a bit. This is a case of the recursive algorithm being far clearer, with the stack being implicit.

In pseudo-code:


  walk_in_order(from, to, f, head) {
    if (head == nullptr) return;
    hk = head->key();
    if (hk >= from) {
      walk_in_order(from, to, f, head->left());
    }
    if (hk >= from && hk < to) {
      f(hk);
    }
    if (hk < to) {
      walk_in_order(from, to, f, head->right());
    }
  }

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

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