Implement a fast HashMap / hash function

[brson]

Our current HashMap uses cryptographically secure hashing but it is slow. Sometimes this is a big problem. Implement another hash map that is very fast.

[brson]

Not all the performance problems of our HashMap may be due to the hashing algorithm. The Rust implementation, paired with our IterBytes trait may also be a part of it.

[thestinger]

A single-pass SipHash implementation is indeed faster than the stateful implementation used by Rust, but it's not an enormous improvement. Rust's hash table is faster than the libstdc++/libc++ unordered_map when using a C++ (no asm or SIMD intrinsics) single-pass SipHash implementation because linear open addressing is a good fit for a strong hash function.

SipHash fundamentally requires a 60-120 cycle (on x86_64) setup time, and then provides a hashing rate of ~2 cycles per byte (maybe you can do better with asm and SIMD intrinsics). This is tolerable for long strings, because it's only twice as slow as good hash functions without the same guarantees. For integers and short strings, the setup time is a huge expense.

I'm sure that a hash function can exist for small fixed-size keys with far better performance and the same security guarantees, and we may be able to find a weak block cipher to use for this. It will of course still be slower than using the identity function as the hash like C++ standard library implementations all seem to do (with a few extra bit operations in the table itself while matching it to a bucket).

[thestinger]

Tagged with I-compiletime since I think this a major bottleneck in librustc. It may be able to use an improved TrieMap instead, but it's currently not a good enough implementation.

[huonw]

Something like SmallIntMap would also be usable for NodeId tables that have a high occupancy since NodeIds increment by 1 from 0. (This gave a few tens of megabytes memory saving when I converted the ast map in #11616, although, I imagine no other tables will be as full as that one.)

[c-a]

Go uses the AESENC instruction available on newer x86/amd64 processors to implement a fast, and supposedly secure against hash collision DOS attacks, hash function. Unfortunately I can't find any other references of using AESENC for this purpose.

[thestinger]

What do we do on other processors though?

[bnoordhuis]

Is it a requirement that the hash function is cryptographically secure? For example, is a hash function that's seeded by a random number at start-up acceptable?

[thestinger]

@bnoordhuis: SipHash provides security against DoS attacks. That's the sense in which it's cryptographically secure. Hash functions like murmurhash don't actually provide working DoS protection.

[bnoordhuis]

@thestinger I think we're talking about the same thing: preventing collision attacks, right?

Taking V8 as an example, it uses what looks like a Jenkins hash derivative (the inner loop is two adds, two shifts and a xor) with a randomized initial value. It doesn't give quite the same guarantees as SipHash but the tradeoff is that it's much faster. Is an approach like that acceptable?

Apropos random numbers, I noticed that each hash map is created with a new random seed. Has anyone measured what happens when you generate the random seed once instead of repeatedly?

[brson]

@bnoordhuis It's not necessarily a requirement that it prevents collision attacks. I think it is a requirement that the default hash map prevents these attacks, as long as we have a fast option. If the default is both fast and prevents collisions then that is even better.

I don't recall anybody measuring the difference in seeding strategies. We do have a task-local rng that imo should generally be used for these types of things.

[thestinger]

@brson: At one point, I tried using a constant as the key and it didn't make an impact. The speed issue is entirely caused by SipHash, although a weak hash wouldn't mix as well with linear open addressing.

[bnoordhuis]

@thestinger Can you qualify 'weak hash'? As long as the hash function's output is unpredictable and has the avalanche property, it should be good, right?

[cgaebel]

I am currently investigating using Robin Hood Hashing [1][2] for this. I will report back with results and a pull request.

[1] http://codecapsule.com/2013/11/11/robin-hood-hashing/
[2] http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/

[huonw]

#11863 is relevant to this since it changes the infrastructure of hashing in std.

I've ported the xxHash algorithm's single-pass version, and plan on doing more of these, like MurmurHash3. I'm unsure what a good Rust hashing API would look like though, so I'm holding off on that for now.