haphazard
haphazard copied to clipboard
Improve shard hash function to use 128 bit mutiply with xor #2
New PR for #8, with no_std support split up into #11.
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