XXH3 – a new speed-optimized hash algorithm

https://fastcompression.blogspot.com/2019/03/presenting-xxh3.html

by corysama • 7 years ago

275 83 7 years ago

fastcompression.blogspot.com

terrelln4• 7 years ago

I've tested XXH3 using xxhash's built-in benchmark tool with clang-7.0.1 and gcc-8.2.1 on an Intel i9-9900K. The processor was otherwise idle, and was running at 5 GHz. The command I tested is `xxhsum -b5i10`.

    SSE2: CFLAGS=-O3
    AVX2: CFLAGS="-O3 -mavx2"
    ARCH: CFLAGS="-O3 -march=native"

    Compiler  Mode  Speed
    gcc-8     SSE2  32.8 GB/s
    clang-7   SSE2  36.5 GB/s 
    gcc-8     AVX2  44.1 GB/s
    clang-7   AVX2  68.3 GB/s
    gcc-8     ARCH  60.9 GB/s
    clang-7   ARCH  69.7 GB/s

gcc nearly catches up with clang when compiled with -march=native, but with only -mavx2 it isn't performing as well.

felixhandte• 7 years ago

That is pretty dang fast!

mcbain• 7 years ago

I haven’t tried compiling this myself, but gcc does different things with a -march=x flag compared to specifying -mavx2, directly, mostly because -march implies -mtune.

Trying -march=haswell might give closer results.

On the other hand, if using an older gcc and it can’t identify your processor, march=native will result in mtune=generic and much head scratching with results.

pcwalton2• 7 years ago

It's good to see a focus on small input sizes. Small keys are extremely important for hash functions and are often overlooked. Whenever I've looked at the distribution of key sizes in real world Rust code using hash maps it's always turned out to be shockingly small. 8 byte hash inputs are very common in real world code, for instance.

Most hash functions and benchmarks are not tuned for small inputs. This is why SipHash is disfavored in Rust these days, because while its performance is excellent on large keys it suffers quite a bit on small ones.

adrianratnapala2• 7 years ago

Yes, although even here, small is not that very small:

The main focus is about short keys of random lengths, with a distribution of length roughly in the 20-30 bytes area, featuring occasional outliers, both tiny and large.

I have been playing around trying to write interpreters and compilers for a hobby, and though I haven't taken stats, but I suspect that in source code, identifiers half that length are more than twice as common.

It make me wonder if compilers are better of using old-school byte-by-byte hashes rather than new ones optmised for parallelism. (Then again, the hash function probably makes no real difference to speed once in a real-world compiler that does optimisation).

zokier• 7 years ago

Yes, although even here, small is not that very small:
> The main focus is about short keys of random lengths, with a distribution of length roughly in the 20-30 bytes area, featuring occasional outliers, both tiny and large.

Based on the graphs, XXH3 still seems to beat everything at key sizes > 6 (presumably bytes?)

BeeOnRope3• 7 years ago

It make me wonder if compilers are better of using old-school byte-by-byte hashes rather than new ones optmised for parallelism.

Probably not.

Good hashes optimized for small sizes would probably still use wider loads and operations, perhaps overlapping them: e.g., for a 7 byte hash you might do two 4-byte hashes on the first and second half meaning one byte would get done twice, which isn't a problem. High speed small memory copies follow the same approach.

One problem with byte-at-a-time hashes are that byte operations aren't really any faster than wider operations (at least up to 64-bits), so you'll do 7 byte mixing operations in the example above rather than 2.

The other problem is that wider chunks tend to "quantize" the number of loops in the algorithm, which is very helpful for branch prediction. A byte-at-a-time hash that uses a loop or some kind of jump into inline code will necessarily mispredict unless the exact length is predictable: but if it varies by even 1 byte, the branching is different. Hashes with larger chunks may take the same path for a range of lengths, so may have fewer mispredictions even if the size varies. For example, a hash that uses two possibly overlapping 4-byte reads may handle sizes from 5-8 (or even 4-8) bytes with the same path, so random variation within that range doesn't cause a mispredict.

I think the era of the byte-at-a-time hash is really over, except perhaps if gets some special hardware support.

rtfeldman• 7 years ago

SipHash is disfavored in Rust these days

I wasn't aware of this!

What do people use instead?

(I remember reading that part of the motivation for making SipHash the default Hasher was that its randomness guards against hash flooding attacks. Is that something people care about in practice?)

ComputerGuru• 7 years ago

It's a sensitive topic that gets some people really riled up, but essentially it doesn't offer the protection people think it does.

yoklov• 7 years ago

https://github.com/cbreeden/fxhash is reasonably widely used. It doesn't have the security benefits of SipHash, however they are rather dubious in practice -- 64 bits of state is simply not enough to be secure, no matter the hash function (not to mention, real tables will not use the vast majority of those bits).

kevin_thibedeau2• 7 years ago

Seems a bit funny that CRC32 is so slow.

corysama3• 7 years ago

I expect that's because it was designed very well for the days of serial, in-order, static execution. But, CPUs today are all about pipelining and parallelism. Herb Sutter's "Free Lunch" has been over for longer than most people here have been writing software. http://www.gotw.ca/publications/concurrency-ddj.htm

mark-r• 7 years ago

Sutter's solution was to write more concurrent code, but that's not what helps in this case. Rather the CPU vendors have been throwing transistors at doing more math operations in parallel. All you need to do is make sure you're taking advantage of the vector instructions, whether that's done by the compiler or with intrinsic calls.

Traditionally the fastest CRC code has used lookup tables, I wonder if that's creating cache pressure these days? Or maybe that approach was abandoned while I wasn't paying attention.

woadwarrior01• 7 years ago

The OP probably finds it funny because Intel processors since Nehalem have had an instruction for computing CRC32.

nigeltao3• 7 years ago

The comparison is to SMHasher's CRC32 implementation, which is simple but slow, forked from zlib some time ago.

SIMD CRC32 implementations can be more than 14x faster than recent zlib's.

I dropped some details as comments on the original blog post.

jfk13• 7 years ago

Interesting to see this, when just a few days ago we had another "new fast hash" item on the front page: https://news.ycombinator.com/item?id=19357895.

Anyone have a TL;DR regarding how these two compare?

Cyan49739• 7 years ago

wyhash is a close relative to mumhashv2, and feature approximately the same performance strength and weaknesses.

JanecekPetr• 7 years ago

Here's the smhasher output for XXH3 on an i9: https://pastebin.com/ryLN24Qy, the wyhash has its output in its readme.

TLDR: XXH3 uses less cycles per key, by about 30%. The real throughput / latency need a more equal and thorough benchmark of both, though.

rurban5• 7 years ago

Working on it tomorrow. This just got in today. I expect xxh3 to beat everybody on long keys, and because it uses optimized intrinsics it should be close to the optimized th1a variants. wyhash is purely portable code.

rurban5• 7 years ago

Results are now at smhasher. I had to fix all the MSVC issues first.

wyhash still is the recommended hash function: portable and lowest cycles/hash.

However xxxh3 is spectacularly fast, for small and esp. large key sizes. This is now the recommended hash for file or db digests.

String hash table stats not yet done, there FNV1A is still the recommendation, with safe collision handling.

dragontamer10• 7 years ago

https://github.com/RedSpah/xxhash_cpp/blob/master/xxhash/xxh...

The core of the function is as follows:

    static U64 XXH64_round(U64 acc, U64 input)
     {
      acc += input * PRIME64_2;
      acc = XXH_rotl64(acc, 31);
      acc *= PRIME64_1;
      return acc;
     }

Multiplication, rotation, and a 2nd multiplication. These are 64-bit multiplications, which is well known to mix bits well, but CPUs don'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.

My own experiments show that multiplication is a great function for hashing. Multiplication however only spreads the bits in "one direction" (towards the most-significant bit), and very poorly spreads bits towards the LSB.

Rotations, as well as a 2nd multiplication, are helpful at spreading the bits around better.

----------

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'd expect the 32-bit version (if vectorized) would be faster, but the 64-bit version probably mixes the bits around better.

Overall looks like a decent design. Uses ILP with 4x state variables (state->v1, state->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.

Prime numbers are probably not necessary: they just need to be odd numbers to ensure invertibility (Ex: I've achieved decent mixing by multiplying with 0xAAAAAAAA5, which probably isn't a prime number). I'm curious how the prime-constants were selected. There could be some potential for "better numbers" for mixing, depending on how PRIME64_1 and PRIME64_2 were chosen.

Overall checks all of my boxes with regards to good design. Nice! I'm just curious about some details.

----------

I'll note that in my experiments, multiplication seems to "mix" better with XOR, rather than with ADD. I haven't done any tests with this hash yet, but I'm curious how changing the "+=" into "^=" would have on the statistical strength of the hash function.

petschge2• 7 years ago

If I am not mistaken 0xAAAAAAAA5 is 45812984485 = 5 * 28297 * 323801. At least that is what

    factor $(echo -e "ibase=16\nAAAAAAAA5" | bc -l)

claims.

dragontamer10• 7 years ago

Oh man, a typo. Lol. I meant 0xAAAAAAA5... sorry about that.

Lemme muse on the concept: "multiplying by 0xAAAAAAA5" is that the binary is 1010,1010,1010...0101.

A multiplication at its core, is equivalent to a LOT of bitshift-left and add. Multiplying by "1000" is the same as bitshift left by 4. Multiplying by "1010" is bitshift left by 4 + bitshift left by 2.

This is why its important to multiply by an odd number: all those bitshifts lose the top-most bit. You only keep the topmost bit if the bottom-most bit is set.

So multiply by 0xAAAAAAA5 is the same as "bitshift left 31 + bitshift left 29 + bitshift left 27 ... + bitshift left 2 + bitshift left 0", all at once.

Addition itself is a great "mixing" instruction, its an XOR innately with the potential for carries. The carries make the XORs far more complicated to analyze. The 31st bit after all of those bitshifts are not only the XOR of a bunch of bits... but also the "propagated carry bit".

The topmost bit of any multiplication operation is very complex, while the bottom most bit is always the original bit (bit0 is only affected by bit0 from the input). That's why a rotation + 2nd multiply is needed.

terrelln4• 7 years ago

I believe you are looking at XXH64 and XXH32, which is the old version. The new version XXH3 is located in https://github.com/Cyan4973/xxHash/blob/dev/xxh3.h which exposes the public prototypes `XXH3_64bits()` and `XXH3_128bits()` (and variants with seeds).

dragontamer10• 7 years ago

Thanks. This code is IMO far easier to read, despite being intrinsics. It just requires some familiarity with shuffle. Anyone who wants to follow along should use: https://software.intel.com/sites/landingpage/IntrinsicsGuide...

        assert(((size_t)acc) & 31 == 0);
        {   ALIGN(32) __m256i* const xacc  =       (__m256i *) acc;
            const     __m256i* const xdata = (const __m256i *) data;
            const     __m256i* const xkey  = (const __m256i *) key;
    
            size_t i;
            for (i=0; i < STRIPE_LEN/sizeof(__m256i); i++) {
                __m256i const d   = _mm256_loadu_si256 (xdata+i);
                __m256i const k   = _mm256_loadu_si256 (xkey+i);
                __m256i const dk  = _mm256_add_epi32 (d,k);                                  /* uint32 dk[8]  = {d0+k0, d1+k1, d2+k2, d3+k3, ...} */
                __m256i const res = _mm256_mul_epu32 (dk, _mm256_shuffle_epi32 (dk, 0x31));  /* uint64 res[4] = {dk0*dk1, dk2*dk3, ...} */
                __m256i const add = _mm256_add_epi64(d, xacc[i]);
                xacc[i]  = _mm256_add_epi64(res, add);
            }
        }

This is followed up by "ScrambleAcc":

        assert(((size_t)acc) & 31 == 0);
        {   ALIGN(32) __m256i* const xacc = (__m256i*) acc;
            const     __m256i* const xkey  = (const __m256i *) key;
    
            size_t i;
            for (i=0; i < STRIPE_LEN/sizeof(__m256i); i++) {
                __m256i data = xacc[i];
                __m256i const shifted = _mm256_srli_epi64(data, 47);
                data = _mm256_xor_si256(data, shifted);
    
                {   __m256i const k   = _mm256_loadu_si256 (xkey+i);
                    __m256i const dk  = _mm256_mul_epu32 (data,k);          /* U32 dk[4]  = {d0+k0, d1+k1, d2+k2, d3+k3} */
    
                    __m256i const d2  = _mm256_shuffle_epi32 (data,0x31);
                    __m256i const k2  = _mm256_shuffle_epi32 (k,0x31);
                    __m256i const dk2 = _mm256_mul_epu32 (d2,k2);           /* U32 dk[4]  = {d0+k0, d1+k1, d2+k2, d3+k3} */
    
                    xacc[i]  = _mm256_xor_si256(dk, dk2);
            }   }
        }

I don't believe AVX2 rotation exists (correct me if I'm wrong though). So the author has opted for _mm256_srli_epi64 (... 47), which is a 47-bit right shift, followed up with XOR. This is how the author gets those "highly mixed" high-bits back down to the lower-bits.

Vectorization has broadened to 512-bits of state (4x128) so that the vectorized steps can be ILP'd.

The keys are:

    ALIGN(64) static const U32 kKey[KEYSET_DEFAULT_SIZE] = {
        0xb8fe6c39,0x23a44bbe,0x7c01812c,0xf721ad1c,
        0xded46de9,0x839097db,0x7240a4a4,0xb7b3671f,
        0xcb79e64e,0xccc0e578,0x825ad07d,0xccff7221,
        0xb8084674,0xf743248e,0xe03590e6,0x813a264c,
        0x3c2852bb,0x91c300cb,0x88d0658b,0x1b532ea3,
        0x71644897,0xa20df94e,0x3819ef46,0xa9deacd8,
        0xa8fa763f,0xe39c343f,0xf9dcbbc7,0xc70b4f1d,
        0x8a51e04b,0xcdb45931,0xc89f7ec9,0xd9787364,
        0xeac5ac83,0x34d3ebc3,0xc581a0ff,0xfa1363eb,
        0x170ddd51,0xb7f0da49,0xd3165526,0x29d4689e,
        0x2b16be58,0x7d47a1fc,0x8ff8b8d1,0x7ad031ce,
        0x45cb3a8f,0x95160428,0xafd7fbca,0xbb4b407e,
    };

Hmmm... this key is added with the data as it gets mixed in.

---------

Definitely seems like cleaner code actually. Again, I'm not seeing any obvious red-flags in the code, so it looks pretty good to me.

The only thing is that the 32-bit to 64-bit multiply step seems odd to me. It probably isn't losing any information, but I'm kind of mind-farting and can't see whether or not that step is potentially losing entropy or not... I'll probably have to sleep on it.

Specifically this step:

    __m256i const res = _mm256_mul_epu32 (dk, _mm256_shuffle_epi32 (dk, 0x31));  /* uint64 res[4] = {dk0*dk1, dk2*dk3, ...} */

Those numbers aren't necessarily odd. Its a 32-bit multiply that takes two 32-bit numbers, and outputs a 64-bit number (vectorized). It doesn't seem like a "strong" hash, but maybe I need to think about it more. If this is a good hash (and with all the tests done on it... it probably is a good hash), then I'd be surprised.

It reminds me of a RNG that Knuth discussed in his book: where you multiply two numbers and then take the "middle" results of the multiplication (https://en.wikipedia.org/wiki/Middle-square_method). So I feel like there's potential for weakness here. I can't see it one way or the other yet, its just something I'm trying to think about...

adrianratnapala2• 7 years ago

So it took me a while to find the actual algorithm. As far as I can tell it is here:

https://github.com/Cyan4973/xxHash/blob/dev/xxh3.h

Is there a description of the algorithm, the C-source is not only highly optimised, it is also highly #ifdefed to take care of various scenarios. So the file is not optimised for readability.

terrelln4• 7 years ago

I believe that this is just the initial release for testing, and the author plans to clean up the header file to separate out the interface from the implementation, and add documentation.

nerpderp83• 7 years ago

I would be interested in the avx2 transition penalty under real world workloads.

rurban5• 7 years ago

I've already looked at it last week and it looked very good indeed (minus some debugging code Yann ripped out today). It should still be the best hash function for large data digests. The prev. version was already the best for this use case. Interesting is the new property for smaller keys (this was the weak point in xxhash), and the extended tests.

injinj9• 7 years ago

I added xxh3 to my fork of smhasher: https://github.com/injinj/smhasher

I find it to be the fastest hash in my stable of hashes.

Graphs for 64 / 128:

https://github.com/injinj/smhasher/blob/master/plot64.svg

https://github.com/injinj/smhasher/blob/master/plot128.svg

Latency graphs for 64 / 128

https://github.com/injinj/smhasher/blob/master/plot64lat.svg

https://github.com/injinj/smhasher/blob/master/plot128lat.sv...

Latency is using the hash result after each function, the original smhasher algo does not use the result.

unknownknowns• 7 years ago

Thank you! Currently using XXH64 to good success for small keys, and xxh3 looks fantastic as the next upgrade.

BeeOnRope3• 7 years ago

For each size shown on the x-axis, every hashing call using exactly that size?

It would be interesting to also have a test where an average size was chosen, but where the actual sizes varied randomly around that average - because that's a common case in real world code, and the results can be very different since branch prediction won't be perfect any more as it is with the fixed size tests.

Also, latency usually means feeding the output of the function back into the input of the next call. Throughput is what you get when you don't do that but you still need to consume the result, so it's not optimized away. You can use something like DoNotOptimize here:

https://github.com/google/benchmark/blob/master/include/benc...

injinj9• 7 years ago

Yes, it is the same size. I agree, a complex test like that in the original article is better (the Throughput versus Latency section).

The graphs from the "latency" test are doing this:

  for (;;) {
    h = hash( val, seed );
    seed += h;
  }

The original smhasher did this:

  for (;;) {
    hash( val, seed );
  }

tmd83• 7 years ago

What I really loved was the different benchmark ideas e.g. variable input size and hashing as part of a bigger algorithm.

switch33• 7 years ago

https://github.com/switch33?tab=repositories I think mine might match up its written in lorem ipsum you can compile it with utf8.

Can someone benchmark it for me? Because sha with higher values might be faster.

aidenn0• 7 years ago

Slightly OT, but I recently had the need for a rolling hash, and wasn't able to find anything better than Fletcher. Is there anything of similar speed, but better characteristics?

joemanaco• 7 years ago

Here is a comparsion with meowhash: https://twitter.com/mmozeiko/status/1106714583761215488

Meow is faster than xxh3 for all sizes, small or large.

injinj9• 7 years ago

Meow is a freak of nature, it has a constant overhead for all of the small sizes.

I added Meow to my test graphs: https://github.com/injinj/smhasher

I still find xxh3 to slightly faster for small hashes on my machine (i9-7960X), except at the 128bit throughput size > 32b.

injinj9• 7 years ago

Hmm, Meow fails the TwoLongNeighbors test. More information on this test here: https://github.com/hmakholm/smhasher/blob/master/src/LongNei...

  [[[ Keyset 'TestLongNeighbors' Tests ]]]

  Looking for 2-bit collisions in the last 2400 bits.
  Looking for 4-bit collisions in the last 2048 bits.
  Looking for 6-bit collisions in the last 160 bits.
  Trying bases of length 10 to 300, 5 of each length.
  ......[16]...............[32]............... [48]...............[64].

  Among 285 tested bases, we expected 4.25749e-06 bads. 
  Actually there were 5.
  The most striking collision has surprise score 3.52004e+06 and length 46 bytes:
  000: BD 8D 12 8C FB EE 75 2E 17 80 4E 26 8C E7 75 94 DA EF 12 8C 95 CA 91 0D
  018: 08 BD 8D 5F F2 78 FF 64 88 27 88 3F 8E 8F CE FC E2 8A 99 CE 2B E3
                  ^D2^                 ^7F^              ^18^     ^0B^
  The hashes are length 8 bytes:
  000: 35 C1 E6 5B 6B 66 C7 28
  *********FAIL*********

cryptonector• 7 years ago

Those images are unreadable. Can we get higher res. images, or larger fonts? Thanks.

terrelln4• 7 years ago

The images are high res, but you have to download them to view the larger image.

mitchtbaum• 7 years ago

It's cool see these hashing algorithms coming out and excitement about building new libraries and adding them to existing ones, but we also need people gravitating them into an organized and useful project space.

HocusLocus• 7 years ago

Glad to see that part of the human race is still on the track to practical innovation (collision avoidance, small footprint, performance) as opposed to the perpetual Moore's Law paranoia arms race (crypto-secure, more bits, more rounds, constant utilization regardless of input to deter side channel attack).

If you're the slightest bit security conscious you realize that there is NO level below which security is not a factor. If that is the deciding factor these compromises (or as they would tell it, lack of compromise) will decrease overall UTILITY of technology and also increase its FRAGILITY.

The move to aggressively force HTTP to HTTPS even for Joe's Who Cares Web Site for no specifically stated reason is a prime example. If rounds and loops were temperature, it is as if we're shoving the Internet into thermal overload beyond convection cooling, without performing any additional useful work.

Meltdown mitigation is like economic inflation. A general performance decrease for a worst case threat scenario.

What price, paranoia? Is there an upper limit?

XXH3 – a new speed-optimized hash algorithm

Related Stories