RFR: 8313708: NMT: cleanup _mst_marker

[Thomas Stuefe]

On Thu, 3 Aug 2023 18:44:43 GMT, Gerard Ziemski <gziemski at openjdk.org> wrote:

> While learning the NMT code I came across _mst_marker and I don't really like how it combines 16bit index and 16bit position into single 32bit mst_marker using bit sizzling.
> 
> Consequently, right now we need the following 3 APIs: build_marker(), bucket_idx_from_marker(), pos_idx_from_marker() to support this. They are really not adding any value, in my opinion, and in fact obfuscate the code.
> 
> I'd like to propose that we simplify the code and pass a struct value (as suggested by Thomas) which hides away the 2 individual fields that are implementation detail.

Hi Gerard,

I added the mst_marker with JDK-8281015  https://github.com/openjdk/jdk/commit/b96b743727a628c1b33cc9b3374f010c2ea30b78 for two reasons:
- to simplify things: I hated that many interfaces had to carry two separate arguments that both together refer to an MST entry. One argument too many, and implementation details exposed. The `mst_marker` OTOH is an opaque reference to an MST entry, and its form is an implementation detail that is not exposed and could be changed.
- to prepare further improvements: the point of the marker is to quickly resolve MST entries. But that could be done in a better way, without having to manually walk bucket chains and count buckets with O(n). For example, by storing MST entries in a linear array (they never go away, so one would not have to deal with deletion) and redefining the mst_marker to be an index into that table. That way, access to these entries would be O(1).

The latter improvement never materialized outside of a prototype I did. But it should be easy enough to do if you feel up to it. Just reverting 8281015 is, I feel, just a sideways step that arguably increases complexity, since a lot of interfaces now carry one argument more.

Cheers, Thomas

(P.S. if you really hate the bit fiddling, just make the mst marker a struct with two 16 bit members and pass it by reference; but a STATIC_ASSERT would be needed to make sure the compiler does not add padding.).

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

PR Comment: https://git.openjdk.org/jdk/pull/15145#issuecomment-1665092672