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 15:28:11 GMT, Gerard Ziemski <gziemski at openjdk.org> wrote:

>> We improve the hash function, but using Mersenne prime (2^x - 1) i.e. 8191, which when combined with "modulo" operation, provides uniform bit distribution.
>> 
>> To help with testing this change to make sure we improve the hash function, I collected `NMTPreInitAllocation` data on 3 platforms: macOS, Linux and Windows, using 100 runs of `test/hotspot/jtreg/runtime/NMT/NMTInitializationTest.java` and computed `stdev` as well as average `max chain`:
>> 
>> 
>> mac OS data:
>>  BEFORE total: max chain: 676, empties: 210892, ranges: 676, std_devs: 112.771
>>   AFTER total: max chain: 622, empties: 230762, ranges: 622, std_devs: 111.094
>>  BEFORE avg: max chain: 5.061, empties: 18.695, ranges: 5.061, std_devs: 0.010
>>   AFTER avg: max chain: 4.181, empties: 16.970, ranges: 4.161, std_devs: 0.009
>> 	
>> Linux data:
>>  BEFORE total: max chain: 523, empties: 193174, ranges: 523, std_devs: 103.243
>>   AFTER total: max chain: 432, empties: 175347, ranges: 430, std_devs: 90.670
>>  BEFORE avg: max chain: 6.540, empties: 20.402, ranges: 6.540, std_devs: 0.011
>>   AFTER avg: max chain: 6.017, empties: 22.324, ranges: 6.017, std_devs: 0.011
>> 
>> Windows data:
>>  BEFORE total: max chain: 578, empties: 201224, ranges: 578, std_devs: 108.988
>>   AFTER total: max chain: 491, empties: 218653, ranges: 491, std_devs: 104.879
>>  BEFORE avg: max chain: 5.602, empties: 19.504, ranges: 5.602, std_devs: 0.011
>>   AFTER avg: max chain: 4.759, empties: 21.193, ranges: 4.759, std_devs: 0.010
>> 
>> Note: the lower the number, the better.
>> Note: the `stdedev` and `max chain` are the most important numbers here.
>> 
>> We also, mark output with PID to help identify which test process it is coming from as the attached log was very confusing to read.
>> 
>> Tested manually with `/Volumes/Work/tests/jtreg/jtreg/bin/jtreg -nr -va -jdk:./build/macosx-x86_64-server-fastdebug/images/jdk test/hotspot/jtreg/runtime/NMT/NMTInitializationTest.java` and `Mach5 hs-tier1,2,3,4,5
>> `
>
> Gerard Ziemski has updated the pull request incrementally with one additional commit since the last revision:
> 
>   ^ is XOR, not pow

Here are the results with Thomas proposed hash function `(tmp >> 3) ^ (tmp >> 35)`:


Mac OS data:

original total: max chain: 523, empties: 193174, ranges: 523, std_devs: 103.243
           avg: max chain: 5.061, empties: 18.695, ranges: 5.061, std_devs: 0.010

  gerard total: max chain: 432, empties: 175347, ranges: 430, std_devs: 90.670
           avg: max chain: 4.181, empties: 16.970, ranges: 4.161, std_devs: 0.009

 Thomas1 total: max chain: 485, empties: 207085, ranges: 484, std_devs: 99.429
           avg: max chain: 4.694, empties: 20.041, ranges: 4.684, std_devs: 0.010

 Thomas2 total: max chain: 520, empties: 192194, ranges: 520, std_devs: 102.801
           avg: max chain: 5.032, empties: 18.600, ranges: 5.032, std_devs: 0.010


Linux OS data:

original total: max chain: 676, empties: 210892, ranges: 676, std_devs: 112.771
           avg: max chain: 6.540, empties: 20.402, ranges: 6.540, std_devs: 0.011

  gerard total: max chain: 622, empties: 230762, ranges: 622, std_devs: 111.094
           avg: max chain: 6.017, empties: 22.324, ranges: 6.017, std_devs: 0.011

 Thomas1 total: max chain: 656, empties: 225850, ranges: 656, std_devs: 110.384
           avg: max chain: 6.346, empties: 21.849, ranges: 6.346, std_devs: 0.011

 Thomas2 total: max chain: 680, empties: 210918, ranges: 680, std_devs: 112.780
           avg: max chain: 6.578, empties: 20.404, ranges: 6.578, std_devs: 0.011


Windows OS data:

original total: max chain: 578, empties: 201224, ranges: 578, std_devs: 108.988
           avg: max chain: 5.602, empties: 19.504, ranges: 5.602, std_devs: 0.011

  gerard total: max chain: 491, empties: 218653, ranges: 491, std_devs: 104.879
           avg: max chain: 4.759, empties: 21.193, ranges: 4.759, std_devs: 0.010

 Thomas1 total: max chain: 565, empties: 218421, ranges: 565, std_devs: 107.261
           avg: max chain: 5.476, empties: 21.171, ranges: 5.476, std_devs: 0.010

 Thomas2 total: max chain: 578, empties: 201224, ranges: 578, std_devs: 108.987
           avg: max chain: 5.602, empties: 19.504, ranges: 5.602, std_devs: 0.011

Note:
 original table_size 7919
 gerard table_size 8191
 Thomas1 table_size 8191
 Thomas2 table_size 7919


Summary:

- at the table size of 8191 which is Mersenne Prime (Thomas1), it is less than 1% better in stddev for Linux pointers, but quite a bit worse everywhere else than my proposed one (including max chain length for Linux)
- at the table size of 7919 (Thomas2), it is virtually the same as the original and worse than my proposed one

So we don't gain anything by using clever bit shifts and xors (I know I tried many myself) compared to the "naked" pointer - the opposite in fact.

I will post the code to the sandbox I used for these experiments after I clean it up a bit...

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

PR Comment: https://git.openjdk.org/jdk/pull/14607#issuecomment-1603055065