13 ms·

XXH3 – a new speed-optimized hash algorithm

275 points by corysama 8y ago

terrelln 8y 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 8y ago
  That is pretty dang fast!
  - clanrebornx 8y ago
    Dang is a moderator of HN, you are not allowed to use the world, "dang"
- mcbain 8y 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.
pcwalton 8y 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.
- adrianratnapala 8y 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 8y 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?)
    - deleted 8y ago
      [deleted]
  - BeeOnRope 8y 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.
kevin_thibedeau 8y ago
Seems a bit funny that CRC32 is so slow.
- corysama 8y 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 http://www.gotw.ca/publications/concurrency-ddj.htm
  - mark-r 8y 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.
    - dragontamer 8y ago
      > 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. Instruction-level parallelism is incredibly important. I'd say that any optimizing programmer needs to fully understand ILP, and how it interacts with pipelines and dependency cutting (and register renaming). Modern CPUs are extremely well parallelized with ILP. Any good, modern hash function will take advantage of this feature of modern CPUs. Case in point, it seems like xxhash is SCALAR 32-bit / 64-bit code. No vectorization as far as I can tell, its purely using ILP to get its speed. Intel Assembly has a 64-bit multiplier (but vectorized only has 32-bit multipliers). I've theorized to myself that this 64-bit multiplier could lead to better mixing than the vectorized instructions, and it seems like xxhash goes for that. The 32-bit version of xxhash can likely be vectorized and optimized even further.
jfk13 8y 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 https://news.ycombinator.com/item?id=19357895. Anyone have a TL;DR regarding how these two compare?
- Cyan4973 8y ago
  wyhash is a close relative to mumhashv2, and feature approximately the same performance strength and weaknesses.
- JanecekPetr 8y ago
  Here's the smhasher output for XXH3 on an i9: https://pastebin.com/ryLN24Qy 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.
- rurban 8y 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.
  - rurban 8y 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.
dragontamer 8y ago
https://github.com/RedSpah/xxhash_cpp/blob/master/xxhash/xxhash.cpp 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.
- petschge 8y 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.
adrianratnapala 8y 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 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.
- terrelln 8y 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 8y ago
I would be interested in the avx2 transition penalty under real world workloads.
rurban 8y 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.
injinj 8y ago
I added xxh3 to my fork of smhasher: https://github.com/injinj/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/plot64.svg https://github.com/injinj/smhasher/blob/master/plot128.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/plot64lat.svg https://github.com/injinj/smhasher/blob/master/plot128lat.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 8y ago
  Thank you! Currently using XXH64 to good success for small keys, and xxh3 looks fantastic as the next upgrade.
- BeeOnRope 8y 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/benchmark/benchmark.h#L309 https://github.com/google/benchmark/blob/master/include/benc...
  - injinj 8y 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 ); }
switch33 8y ago
https://github.com/switch33?tab=repositories 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 8y 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 8y ago
Here is a comparsion with meowhash: https://twitter.com/mmozeiko/status/1106714583761215488 https://twitter.com/mmozeiko/status/1106714583761215488 Meow is faster than xxh3 for all sizes, small or large.
- injinj 8y 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 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.
  - injinj 8y ago
    Hmm, Meow fails the TwoLongNeighbors test. More information on this test here: https://github.com/hmakholm/smhasher/blob/master/src/LongNeighborTest.md 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*********
    - injinj 8y ago
      I can make Meow pass the LongNeighbors test by doubling the number of AES rounds on each pass. The original Meow algo: while(Len >= 64) { S0 = Meow128_AESDEC_Mem(S0, Source); S1 = Meow128_AESDEC_Mem(S1, Source + 16); S2 = Meow128_AESDEC_Mem(S2, Source + 32); S3 = Meow128_AESDEC_Mem(S3, Source + 48); Len -= 64; Source += 64; } The modified algo: while(Len >= 64) { S0 = Meow128_AESDEC_Mem(S0, Source); S0 = Meow128_AESDEC_Mem(S0, Source); S1 = Meow128_AESDEC_Mem(S1, Source + 16); S1 = Meow128_AESDEC_Mem(S1, Source + 16); S2 = Meow128_AESDEC_Mem(S2, Source + 32); S2 = Meow128_AESDEC_Mem(S2, Source + 32); S3 = Meow128_AESDEC_Mem(S3, Source + 48); S3 = Meow128_AESDEC_Mem(S3, Source + 48); Len -= 64; Source += 64; } (also changed the partial rounds, but this is not shown here) This doesn't change it's performance that much, maybe 1 or 2 extra CPU cycles. My i9 CPU must be able to run these extra rounds in parallel... I do have hyperthreading disabled, if that matters. Update: Ah, it does cause the bulk speed test to be 50% of the original (48MiB vs 24Mib). The small key test only adds 1/2/3/4 extra AES instructions since they are manipulating 16 bytes at a time. It looks like this is only taking a cycle.
cryptonector 8y ago
Those images are unreadable. Can we get higher res. images, or larger fonts? Thanks.
- terrelln 8y ago
  The images are high res, but you have to download them to view the larger image.
mitchtbaum 8y 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 8y 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?

275 points by corysama 8y 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 8y ago
That is pretty dang fast!
- clanrebornx 8y ago
  Dang is a moderator of HN, you are not allowed to use the world, "dang"
mcbain 8y 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.

pcwalton 8y 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.

adrianratnapala 8y 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 8y 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?)
  - deleted 8y ago
    [deleted]
- BeeOnRope 8y 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.

kevin_thibedeau 8y ago

Seems a bit funny that CRC32 is so slow.

corysama 8y 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 http://www.gotw.ca/publications/concurrency-ddj.htm
- mark-r 8y 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.
  - dragontamer 8y ago
    > 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. Instruction-level parallelism is incredibly important. I'd say that any optimizing programmer needs to fully understand ILP, and how it interacts with pipelines and dependency cutting (and register renaming). Modern CPUs are extremely well parallelized with ILP. Any good, modern hash function will take advantage of this feature of modern CPUs. Case in point, it seems like xxhash is SCALAR 32-bit / 64-bit code. No vectorization as far as I can tell, its purely using ILP to get its speed. Intel Assembly has a 64-bit multiplier (but vectorized only has 32-bit multipliers). I've theorized to myself that this 64-bit multiplier could lead to better mixing than the vectorized instructions, and it seems like xxhash goes for that. The 32-bit version of xxhash can likely be vectorized and optimized even further.

jfk13 8y 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 https://news.ycombinator.com/item?id=19357895. Anyone have a TL;DR regarding how these two compare?

Cyan4973 8y ago
wyhash is a close relative to mumhashv2, and feature approximately the same performance strength and weaknesses.
JanecekPetr 8y ago
Here's the smhasher output for XXH3 on an i9: https://pastebin.com/ryLN24Qy 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.
rurban 8y 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.
- rurban 8y 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.

dragontamer 8y ago

https://github.com/RedSpah/xxhash_cpp/blob/master/xxhash/xxhash.cpp 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.

petschge 8y 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.

adrianratnapala 8y 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 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.

terrelln 8y 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 8y ago

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

rurban 8y 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.

injinj 8y ago

I added xxh3 to my fork of smhasher: https://github.com/injinj/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/plot64.svg https://github.com/injinj/smhasher/blob/master/plot128.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/plot64lat.svg https://github.com/injinj/smhasher/blob/master/plot128lat.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 8y ago
Thank you! Currently using XXH64 to good success for small keys, and xxh3 looks fantastic as the next upgrade.
BeeOnRope 8y 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/benchmark/benchmark.h#L309 https://github.com/google/benchmark/blob/master/include/benc...
- injinj 8y 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 ); }

switch33 8y ago

https://github.com/switch33?tab=repositories 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 8y 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 8y ago

Here is a comparsion with meowhash: https://twitter.com/mmozeiko/status/1106714583761215488 https://twitter.com/mmozeiko/status/1106714583761215488 Meow is faster than xxh3 for all sizes, small or large.

injinj 8y 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 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.
- injinj 8y ago
  Hmm, Meow fails the TwoLongNeighbors test. More information on this test here: https://github.com/hmakholm/smhasher/blob/master/src/LongNeighborTest.md 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*********
  - injinj 8y ago
    I can make Meow pass the LongNeighbors test by doubling the number of AES rounds on each pass. The original Meow algo: while(Len >= 64) { S0 = Meow128_AESDEC_Mem(S0, Source); S1 = Meow128_AESDEC_Mem(S1, Source + 16); S2 = Meow128_AESDEC_Mem(S2, Source + 32); S3 = Meow128_AESDEC_Mem(S3, Source + 48); Len -= 64; Source += 64; } The modified algo: while(Len >= 64) { S0 = Meow128_AESDEC_Mem(S0, Source); S0 = Meow128_AESDEC_Mem(S0, Source); S1 = Meow128_AESDEC_Mem(S1, Source + 16); S1 = Meow128_AESDEC_Mem(S1, Source + 16); S2 = Meow128_AESDEC_Mem(S2, Source + 32); S2 = Meow128_AESDEC_Mem(S2, Source + 32); S3 = Meow128_AESDEC_Mem(S3, Source + 48); S3 = Meow128_AESDEC_Mem(S3, Source + 48); Len -= 64; Source += 64; } (also changed the partial rounds, but this is not shown here) This doesn't change it's performance that much, maybe 1 or 2 extra CPU cycles. My i9 CPU must be able to run these extra rounds in parallel... I do have hyperthreading disabled, if that matters. Update: Ah, it does cause the bulk speed test to be 50% of the original (48MiB vs 24Mib). The small key test only adds 1/2/3/4 extra AES instructions since they are manipulating 16 bytes at a time. It looks like this is only taking a cycle.

cryptonector 8y ago

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

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

mitchtbaum 8y 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 8y 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?