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

[Thomas Stuefe]

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

Looking back at this, I wonder whether we should reduce the table size. 64k for this lookup table is pretty big. The MallocSizeTable itself, that arguably holds a lot more allocations, is just have as wide.

src/hotspot/share/services/nmtPreInit.hpp line 159:

> 157:     // Keep hash function simple, the modulo
> 158:     // operation in index function will do the "heavy lifting".
> 159:     return (unsigned)p2i(p);

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.

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

PR Review: https://git.openjdk.org/jdk/pull/14607#pullrequestreview-1493613061
PR Review Comment: https://git.openjdk.org/jdk/pull/14607#discussion_r1238778595