Change SipHash implementation to an optimized assembly version

[brson]

It's crucial that our secure hash maps are as fast as we possibly can make them, and there's more we can do yet. This is worth dropping down to assembly or even C for.

The best candidate is https://github.com/google/highwayhash. Unfortunately, it is apache2 only. We would need to get them to dual-license, but let's not bug them until we're sure we have a patch that's acceptable on our end.

This implementation requires AVX2, which we can not count on any of our shipping targets to support. But it seems relatively simple to me to do cpu feature detection dynamically in some strategic place, then drop to the fast version.

So the steps here:

• Out of tree, create a SipHash13/24 implementation in Rust, backed by the highwaysh implementation
• Benchmark it to prove its fast enough to be worth the effort
• Add the highwayhash siphash implementation to src/rt, and add it to the build system(s)
• Add the optimized SipHash13/24 implementation to std, alongside the existing
• Create another SipHash13/24 definition that delegates to one of the others. During construction detect AVX2 and set a flag. Dispatch based on flag.

An obvious concern is the overhead of that flag, and of the FFI crossing.

cc @alexcrichton what you think?

cc @briansmith

[alexcrichton]

I've updated https://github.com/alexcrichton/siphash-bench to include the highwayhash repo, and the results look like (on nightly):

test c1_siphash24::str_long     ... bench:       5,346 ns/iter (+/- 8)
test c1_siphash24::str_medium   ... bench:         283 ns/iter (+/- 19)
test c1_siphash24::str_small    ... bench:          16 ns/iter (+/- 1)
test c2_siphash24::str_long     ... bench:       3,700 ns/iter (+/- 3)
test c2_siphash24::str_medium   ... bench:         202 ns/iter (+/- 1)
test c2_siphash24::str_small    ... bench:          15 ns/iter (+/- 1)
test cpp_siphash::str_long      ... bench:       5,241 ns/iter (+/- 21)
test cpp_siphash::str_medium    ... bench:         267 ns/iter (+/- 3)
test cpp_siphash::str_small     ... bench:          17 ns/iter (+/- 0)
test rust_siphash13::str_long   ... bench:       2,282 ns/iter (+/- 13)
test rust_siphash13::str_medium ... bench:         123 ns/iter (+/- 1)
test rust_siphash13::str_small  ... bench:           8 ns/iter (+/- 1)
test rust_siphash24::str_long   ... bench:       4,223 ns/iter (+/- 44)
test rust_siphash24::str_medium ... bench:         218 ns/iter (+/- 0)
test rust_siphash24::str_small  ... bench:          11 ns/iter (+/- 0)

That is, SipHash13 in our standard library still beats out everything. There's a lot of hashes in that repo, though, and I could be building it wrong. @brson could you clarify which one you were referring to?

[brson]

Huh, siphash in the highway hash repo is not AVX2 optimized. It's just compatible C. It's only SipTreeHash and HighwayTreeHash that are AVX2 optimized. Neither are the same algorithm (though I think any crypto-hash is fair-game for the default).

But furthermore, the AVX2 optimized hashes are even slower for small inputs than siphash, so we would really need a way to determine the two cases. Frustrating.

[brson]

Here's what I think I want in an ideal world:

• The hasher buffers inputs up to some number of bytes that determines a 'big' input
• If finish is called before the input reaches that size it uses a hypothetical crypto-safe hash that is fast for small inputs (I don't know if such a thing exists)
• Otherwise it does cpu detection and if it has AVX2 drops to HighwayTreeHash / SipTreeHash
• If no AVX2 then SipHash13

[brson]

@alexcrichton In your benches c2_siphash24 is faster than rust_siphash24, or am I misreading?

[alexcrichton]

@brson yes I believe that c2 implementation is faster than the Rust implementation, no idea why though (just threw up some numbers)

[sfackler]

SipHash was specifically designed to be fast for small inputs and I think most of Google's effort for things like CityHash have been targeted around high throughput for long strings.

[bluss]

Here's another person who implemented sse2/ssse3 siphash and if I understand what they mean correctly, on x86-64, their basic (no explict simd) version was the best. https://github.com/floodyberry/siphash

It seems there's a few things pointing towards siphash not being that amenable for optimization using sse/avx?

[briansmith]

It seems there's a few things pointing towards siphash not being that amenable for optimization using sse/avx?

This is why Google made siptreehash: https://github.com/google/highwayhash#siptreehash.

Note that also Java abandoned the whole "strong hash function" approach due to performance concerns, in favor of a totally different way of structuring the hash table buckets in the face of many collisions: https://bugs.openjdk.java.net/browse/JDK-8046170

[brson]

Thanks for that link @briansmith.

In the spirit of the original OP i guess the only thing to do here is to replace the Rust siphash with the C siphash if it is indeed faster, which @alexcrichton's benchmarks indicate may be the case, by a decent percent, assuming the C siphash13 performance compares to the Rust performance similarly to 2-4.

[brson]

Although if we were to add new C code to std that invalidates some of the logic in the -C target-feature=cstatic RFC, which depends on std not containing C code (because MSVC has to compile it differently).

[bluss]

One way to make rust's siphasher faster is to enable one-shot hashing, there's an ongoing rfc for one approach at that rust-lang/rfcs#1666

one-shot hashing would be that the SipHasher type receives a whole byte slice that it can hash into a final hash value in one go. Currently SipHasher is implemented to take chunks at a time, and must have logic that keeps track of non-multiple-of-8 remainders between each call to Hasher::write.

The C implementation of siphash that was compared with does it all in one shot, so that's certainly a factor in its favour. I'm sure Rust would be equivalent if it did too.