Help wanted: fast hash maps in std

[jethrogb]

I actually don’t find this too bad:

let mut map=HashMap::<_,_,FnvState>::default();

The fnv crate (and all other crates providing hashers) just needs to have a pub type FnvState = BuildHasherDefault<FnvHasher>

[bluss]

What about just a type alias FnvHashMap<K, V> = ... ?

[DanielFath]

• A solution that removes from the default HashMap Rust’s long-established strong protection against collision-based attacks is unlikely to be accepted, for backwards-compatibility reasons if nothing else, so the most likely path forward is to add additional hashers in some form to std.

What sort of hash functions adhere to this requirement? I assume FnvHasher is out, by the virtue of not being a keyed cryptographic function (list of what I mean).

[bluss]

I think we can fix this in a “perfect” way by having the hash map automatically use one-shot hashing when possible.

For example if the key is String, it’s hashed in one go without terminator. If it’s a compound type (containing Strings etc), it uses the current method.

hashing in one go has more upsides than just skipping the terminator; it also means that the handling for partial blocks can be omitted in SipHash for that case.

Edit: Although, the above has been attempted and no good solution was found yet.

[dns2utf8]

What if the default Hasher would stay the same and with a builder, the user could change the hasher?

I think an elegant way would be with an optional type parameter or a new new.

For example to create a fast hash table for u8:

let map = HashMap::with_hasher(|e: u8| e % 64)

[sfackler]

@bluss

We unfortunately can’t use oneshot hashing for any type where the oneshot version would be different than the non-oneshot version. Notably this includes strings since we add the 0xff byte and primitive slices since we prepend with the length.

You run into breakage when a user has defined their own type which can borrow to a &str (think InternedString). If we add a oneshot hash implementation to &str and use it in HashMap and HashSet, the user’s code would suddenly fail to successfully look up things if InternedString is missing an identical oneshot implementation.

@dns2utf8

I think this is what you’re looking for? https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.with_hasher

[briansmith]

We unfortunately can’t use oneshot hashing for any type where the oneshot version would be different than the non-oneshot version. Notably this includes strings since we add the 0xff byte and primitive slices since we prepend with the length.

Why is it important to continue doing those things?

[sfackler]

It avoids trivial collisions between things like ("foo", "bar") and ("foob", "ar").

[sfackler]

We also can’t realistically change it for the same reason as we run into with oneshot - user defined types that have to has the same way as a &str because they’re linked via Borrow.

[aturon]

I wanted to point out a relevant idea and commentary from the 2017 planning thread:

Setting our vision for the 2017 cycle

I brought this up in a different thread, but I think 'insecure but fast hashing' is a red herring in most cases. Instead, the default HashMap should use an adaptive scheme that starts with an insecure hash and switches to a secure one if an attack is detected (based on load factor and maximum distance of entries from their ideal location). That should provide the best of both worlds except if code size needs to be minimized, which is not the reason most people seem to want to use insecure hash…

Setting our vision for the 2017 cycle

This is a beautiful example of the kind of curve-bending that the Rust community has gotten so good at. Instead of just assuming that some ostensible tradeoff is a hard tradeoff, identify ways to get many of the benefits of both solutions at the same time. That shrinks down the set of cases that aren't reasonably handled by the default (in this case, codebases with both fast-hash requirements and significant code size limitations), which makes the justification for escape valves much easier …

@comex, @wycats, maybe you can continue discussion here?

[ahmedcharles]

Wouldn’t the solution be more generic if it was implemented as part of the hashing of a tuple rather than as part of String?

For example:

    fn hash<S: Hasher>(&self, state: &mut S) {
        let (ref a, ref b) = *self;
        a.hash(state);
        state.write_u8(0xff);
        b.hash(state);
        state.write_u8(0xff);
    }

[ahmedcharles]

Just curious, what’s meant by ‘oneshot’?

[sfackler]

But then you still have collisions between e.g. ([0xff], []) vs ([], [0xff]). 0xff works specifically for strings because that’s not a valid UTF-8 byte.

[sfackler]

Oneshot hashing is when you have a single byte buffer you need to hash and can give it to the hasher all at once. It can be more efficient than iterative hashing since you don’t need to carry a bunch of state around. You can also pick an algorithm based on the input size to maximize throughput.

[ahmedcharles]

I hadn’t considered that, but that’s because my initial suggestion was something that the current api can’t do, for example:

    fn hash<S: Hasher>(&self, state: &mut S) {
        let (ref a, ref b) = *self;
        let a_s = S::new(); // This doesn't exist currently.
        a.hash(a_s);
        state.write_u64(a_s.finish());
        let b_s = S::new(); // This doesn't exist currently.
        b.hash(b_s);
        state.write_u64(b_s.finish());
    }

There are probably other implications to this that I’m not aware of, but does solve the problem.

[infogulch]

For tuples, how about first hashing the lengths of all the variable length sub components, together, before any of their contents? Wouldn’t this defeat any attempts to trigger a collision?

(The tuple collision problem reminds me of the issue of unambiguously serializing data. Perhaps some techniques in this space could be useful?)

[sfackler]

How is the implementation going to find the lengths of all variable length sub components?

[comex]

See also:

https://github.com/contain-rs/hashmap2/pull/5/files

a fairly old (March) PR to a fork of the current HashMap implementation, which implements this already. I’m not sure what the current state is.

I really should try hacking on HashMap myself as there are a bunch of other potential optimizations I’d like to look at.

[Ichoran]

For some reason, MurmurHash3 hasn’t been extensively investigated. It performs vastly better than xxHash for short keys because it has much less state to populate, but has top-quality (non-cryptographic) properties. For example, a 1-byte array can give a 32 bit hash in ~4 ns in Scala, which handily beats everything on https://cdn.rawgit.com/Gankro/hash-rs/7b9cf787a830c1e52dcaf6ec37d2985c8a30bce1/index.html save FNV. A somewhat-carefully optimized Rust implementation could probably outdo that substantially.

I strongly support the idea of having context-dependent hashing (switch to a slower algorithm if many collisions are detected), but I am not sure that FNV is a good choice for a default for anything. You don’t have to spend very much more time to get at least somewhat better hashing even at very short key sizes.

[arthurprs]

I’m improving the cache awareness in this PR https://github.com/rust-lang/rust/pull/36692 This will add up to any hashing improvements.