Move HashMap to liballoc

[Gankra]

View all comments

This is blocked on #26870

• Move FnvHasher from src/librustc/util/nodemap.rs to libcollections
• Expose FnvHasher as DeterministicState
• Move HashMap's implementation into libcollections defaulting to DeterministicState
• Unhardcode HashMap's constructors/methods from using RandomState (instead relying on default fallback)
• Re-export HashMap in std::collections as pub type HashMap<K, V, S = RandomState> = core_collections::HashMap<K, V, S>
• Do the same for HashSet
• Re-export DeterministicState in std as well (so we have a better answer to "HashMap is slow")
• Document the performance-stability/security tradeoff between DeterministicState and RandomState, and that users of the std facade will get a different default from direct users of libcollections (because RandomState requires OS rng to seed its state)

I am willing to mentor this if someone else wants to do it.

Note that re-exporting HashMap may be the trickiest one; it's not clear to me that it's trivial, and may involve manually re-exporting everything in std::collections::hash_map to get the right behaviour (annoying and potentially fragile).

[Gankra]

CC @jroesch to confirm that this will work correctly with your design

[jroesch]

Yeah this seems to be completely compatible with the current design of defaults. Let me know if there are any issues doing this.

[alexcrichton]

I would also be fine just not having a default in libcollections and eschew the DeterministicState entirely.

[Gankra]

I would like to have DeterministicState in std because it's painful to explain that if you want a fast HashMap you need to use such-and-such external crate.

[alexcrichton]

Perhaps, yeah, but I also don't mind expanding std::hash to just have more hashing algorithms. We use RandomState as a name so we're not committing to an algorithm, but that's basically just because it's the default. If you have to explicitly opt-in to an algorithm it seems fine to just expose the names themselves.

[Gankra]

Oh yeah, I'm fine if it's also just straight up FnvState or whatever. Just want a secure and a fast option.

[eddyb]

#26870 landed, but you want a snapshot before you can start moving things around.

[pczarn]

Thanks, snapshot landed just now. I would be happy to do this.

[Gankra]

It sounds like we can't while the feature is gated?

[jroesch]

Niko and I talked today and the feature becoming ungated is a decision the core team has to make. We are already going to make a couple tweaks to the algorithm this week, looking forward to this being stable ;)

[munyari]

@gankro I'd like to work on this in whatever limited capacity I can, if you're still willing to mentor