XXH3 – a new speed-optimized hash algorithm
<a href="https:&#x2F;&#x2F;github.com&#x2F;RedSpah&#x2F;xxhash_cpp&#x2F;blob&#x2F;master&#x2F;xxhash&#x2F;xxhash.cpp" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;RedSpah&#x2F;xxhash_cpp&#x2F;blob&#x2F;master&#x2F;xxhash&#x2F;xxh...</a><p>The core of the function is as follows:<p><pre><code>    static U64 XXH64_round(U64 acc, U64 input)
     {
      acc += input * PRIME64_2;
      acc = XXH_rotl64(acc, 31);
      acc *= PRIME64_1;
      return acc;
     }
</code></pre>
Multiplication, rotation, and a 2nd multiplication. These are 64-bit multiplications, which is well known to mix bits well, but CPUs don&#x27;t have many 64-bit multipliers. Four rounds execute in parallel (see XXH64_update_endian), which can hide the long latency (~5 cycles) associated with a 64-bit multiply.<p>My own experiments show that multiplication is a great function for hashing. Multiplication however only spreads the bits in &quot;one direction&quot; (towards the most-significant bit), and very poorly spreads bits towards the LSB.<p>Rotations, as well as a 2nd multiplication, are helpful at spreading the bits around better.<p>----------<p>The 64-bit version is somewhat interesting to me, but the 32-bit version probably has more potential for optimization. 32-bit vectorized multiplication exists in AVX2, so the 32-bit version probably can be vectorized. I&#x27;d expect the 32-bit version (if vectorized) would be faster, but the 64-bit version probably mixes the bits around better.<p>Overall looks like a decent design. Uses ILP with 4x state variables (state-&gt;v1, state-&gt;v2, etc. etc. to allow CPUs to process these multiplications in parallel). Multiply + rotation + multiplication is good from my personal experiments, but the numbers chosen need to be carefully chosen.<p>Prime numbers are probably not necessary: they just need to be odd numbers to ensure invertibility (Ex: I&#x27;ve achieved decent mixing by multiplying with 0xAAAAAAAA5, which probably isn&#x27;t a prime number). I&#x27;m curious how the prime-constants were selected. There could be some potential for &quot;better numbers&quot; for mixing, depending on how PRIME64_1 and PRIME64_2 were chosen.<p>Overall checks all of my boxes with regards to good design. Nice! I&#x27;m just curious about some details.<p>----------<p>I&#x27;ll note that in my experiments, multiplication seems to &quot;mix&quot; better with XOR, rather than with ADD. I haven&#x27;t done any tests with this hash yet, but I&#x27;m curious how changing the &quot;+=&quot; into &quot;^=&quot; would have on the statistical strength of the hash function.