Implement a fast HashMap / hash function

[steveklabnik]

Issue by brson
Saturday Jan 25, 2014 at 00:54 GMT

For earlier discussion, see rust-lang/rust#11783

This issue was labelled with: A-an-interesting-project, A-libs, I-compiletime, I-slow, I-wishlist in the Rust repository

---

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.

[ilyaraz]

The current version of HashMap is still around 4 times slower than C++ unordered map on int keys. It is quite unfortunate.

[divyekapoor]

Hash maps with integer keys are quite common and they usually operate on trusted data. A DoS resistant hash map should be the exception, not the rule (fast hashmaps should be the default). Is there any intent to change this behavior?

[Luthaf]

Is that still true using BTreeMap and the FNV hasher? (see the first code example). I did not do the checks by myself, but I believe the situation has improved since the creation of this issue.

[steveklabnik]

Yes, @Luthaf is correct.

A DoS resistant hash map should be the exception, not the rule (fast hashmaps should be the default).

This is not the current position of the libs team, in my understanding, but regardless, we cannot change this now; the ship has sailed. /cc @rust-lang/libs

[ticki]

but regardless, we cannot change this now; the ship has sailed.

It actually can. Changing it would be a non-breaking change.

[seanmonstar]

@ticki

It actually can. Changing it would be a non-breaking change.

It'd be worse: it would change the behavior and its guarantee without a user knowing. Suddenly anyone depending on the strength of HashMap is susceptible to DOS attacks.

[ticki]

It'd be worse: it would change the behavior and its guarantee without a user knowing. Suddenly anyone depending on the strength of HashMap is susceptible to DOS attacks.

The HashMap guarantee no such thing.

[ilyaraz]

In 99.9% of the use cases hash tables prone to DOS attacks are perfectly adequate. In the remaining 0.1% percent, a person in charge of the corresponding part of code should be expert enough to be able to choose a right implementation of a hash table, or implement it themselves.

That's why the default option that uses collision-resistant hash functions is a bit stupid.

[apasel422]

In 99.9% of the use cases hash tables prone to DOS attacks are perfectly adequate. In the remaining 0.1% percent, a person in charge of the corresponding part of code should be expert enough to be able to choose a right implementation of a hash table, or implement it themselves.

That's why the default option that uses collision-resistant hash functions is a bit stupid.

The same argument could be made in favor of having HashMap be secure by default. If someone really needs to squeeze some more performance out of a map, after profiling to determine that it is indeed a bottleneck, they can opt for a map that is prone to DOS.

[ticki]

The same argument could be made in favor of having HashMap be secure by default. If someone really needs to squeeze some more performance out of a map, after profiling to determine that it is indeed a bottleneck, they can opt for a map that is prone to DOS.

But the point is that the majority of cases DOS is not a problem.

[apasel422]

But the point is that the majority of cases DOS is not a problem.

That may be true, but is map performance a problem in the majority of cases?

[ticki]

That may be true, but is map performance a problem in the majority of cases?

A lot actually. Let me give you an example:

Recently, I did a changed our ZFS implementation of Redox from using SipHasher to DJB2, this gave a massive speed-up (x2-4!)

[apasel422]

A lot actually. Let me give you an example:

Recently, I did a changed our ZFS implementation of Redox from using SipHasher to DJB2, this gave a massive speed-up (x2-4!)

Right. You profiled your application and determined that you could gain increased performance by switching. There are certainly cases in which DOS is not a concern, but it should be a conscious choice to trade security for speed.