RFR: 8293972: runtime/NMT/NMTInitializationTest.java#default_long-off failed with "Suspiciously long bucket chains in lookup table." [v2]

[Gerard Ziemski]

On Thu, 22 Jun 2023 16:34:20 GMT, Thomas Stuefe <stuefe at openjdk.org> wrote:

> How can the modulo do the "heavy lifting" if you shear off half of the value space? (well, about a quarter to a third, since most kernels have 48..52 bit addresses.
> 
> In fact, I would go the other direction and improve this hash like this: return (tmp >> 3) ^ (tmp >> 35)
> 
> since the lower 3 bits are always 0 for malloc pointers.

I ported the code wrong from my sandbox. The hash function should be dealing with 64 bits, not 32 bits:


  static uint64_t calculate_hash(const void* p) {
    // Keep hash function simple, the modulo
    // operation in index function will do the "heavy lifting".
    return (uint64_t)(p);
  }

  static index_t index_for_key(const void* p) {
    const uint64_t hash = calculate_hash(p);
    // "table_size" is a Mersenne prime, so "modulo" is all we need here.
    return hash % table_size;
  }


I will fix this shortly in the code.

The problem with your approach is that you are trying to extract "good" bits, by hand. I ran multiple experiments trying to find "uniform" bits by hand and it was hard. I never gotten a better hash compared to using full 64 bits, and using modulo operation (with Mersenne prime table size) to mix those 64 bits for us.

I will try your proposed hash function and report bak here.

Good catch about the 64 to 32 bit clipping - thank you.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/14607#discussion_r1238796756