haphazard icon indicating copy to clipboard operation
haphazard copied to clipboard

Improve shard hash function to use 128 bit mutiply with xor #2

Open TroyNeubauer opened this issue 4 years ago • 1 comments

New PR for #8, with no_std support split up into #11.

TroyNeubauer avatar Nov 11 '21 16:11 TroyNeubauer

From #8: This prevents adding a dependency and produces quite good hashes compared to AHash and std's DefaultHasher: I wrote a simulation program that calculates the quality of the spread for each algorithm based on real pointer values from the allocator. The full code is available here: https://github.com/TroyNeubauer/hash_test/blob/master/src/main.rs Here is an example run of the simulation: This implementation is on par with hashing from the standard library and AHash for this use case. I couldn't find a MOCK_SIZE or number of runs that lead to a > 10% standard deviation difference between Multiply Hash and the others. Interestingly, the pointer hash works decently well for being so simple lol.The simulation also allocates unrelated objects to simulate a user allocating objects other than hazard pointers.

These results look promising but should be taken with a grain of salt for using pointer values from my machine and for general weirdness for using pointer values as entropy.

Also the efficiency is quite good. On x86 LLVM produces a single mul instruction (64 bit inputs, 128 bit outputs) and is just 5 instructions total: https://godbolt.org/z/o1n15dncd

Linking the point in stream where you discuss this for reference: https://youtu.be/tGn0mQF0804?t=11883

TroyNeubauer avatar Nov 11 '21 16:11 TroyNeubauer