Move HashMap to liballoc

[Gankra]

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

[munyari]

Looks like I unassigned you? oops

[eddyb]

@munyari Sadly I don't think progress can be made on this without adopting some strategy for type parameter defaulting.

[steveklabnik]

libcollections is gone, so I believe this can be closed. @gankro if that's wrong please let me know!

[jethrogb]

@steveklabnik all the collections now live in liballoc instead, except for HashMap which is still in std for the same reason it wasn't in libcollections. Please re-open.

[cjgillot]

Since libstd now uses hashbrown, is this still relevant/doable?

[Gankra]

So I didn't explain this well, but historically the main blocker was the the default random hasher relied on thread-locals to allow HashMap instances on the same thread to share a seed (since generating it was expensive, and this was regarded as sufficient to guard against HashDOS).

Thread-local storage is a feature "exclusive" to std, which liballoc (then libcollections) wasn't allowed to use.

That said it looks like things may have changed a lot with how hashbrown does seeding. @Amanieu: is it now trivial for us to move HashMap to libcollections? Or does the std shim still use the thread-localy stuff?

[Amanieu]

hashbrown itself is #[no_std] since it uses a non-HashDOS-safe hasher. The std shim is what adds the SipHash hasher which depends on randomness and TLS.

Personally, I've just been using hashbrown directly in my no_std code.

[jethrogb]

This is certainly still relevant and hashbrown hasn't made it more doable. The main reason why this hasn't already been done is the random state for the secure hasher. Thread local storage is only part of the story, the main issue is a that a cryptographically-secure randomness source is needed to initialize the state. This is not available in (the platform-independent) libcore/liballoc. This hasn't changed with hashbrown.

Btw, the tasks in the issue description need updating from the pre-1.0 era.

Yes, you can use hashbrown in no_std, but library crates that use that in their public APIs are not compatible with the std HashMap.

[programmerjake]

imho rather than making a alloc_internals crate, that stuff should just be in core since it's only the interface traits and functions, not actually a global allocator.

turns out Allocator is already in core, what does hashbrown need that isn't in core?

[Amanieu]

I took a quick look at hashbrown and here's what it uses alloc for:

• The default type parameter for the HashMap and HashSet allocators.
• ToOwned for HashSet::get_or_insert_owned.
• handle_alloc_error for allocation failures.

This is sufficiently small that it's probably possible to make hashbrown only depend on core (with an optional dependency on alloc), though I'm not entirely sure how to deal with handle_alloc_error. Perhaps we could manually include of copy of the implementation directly in hashbrown? It should be fine to depend on unstable implementation details when building as part of the standard library.

[clarfonthey]

Is there any actual reason ToOwned can't be defined in core, setting aside the fact that the compiler currently doesn't allow incoherent trait impls?

[m-ou-se]

Is there any actual reason ToOwned can't be defined in core, setting aside the fact that the compiler currently doesn't allow incoherent trait impls?

I don't think ToOwned belongs outside alloc. It is quite specific/biased to alloc types. For example, it considers alloc::string::String to be the (one and only) owned version of &str, even though there exist perfectly good alternatives in other crates (e.g. owned string types with small string optimization, or strings that store the length in the allocation, etc.).

[scottmcm]

I would love it if we could find a lang way to allow splitting Clone into

pub trait CloneFrom<Other: ?Sized> {
    fn clone_from(&mut self, other: &Other);
}
pub trait Clone : CloneFrom<Self> where Self: Sized {
    fn clone(&self) -> Self;
}

so that that CloneFrom can be in core for all the "update my arraystr from that str" cases, and thus reduce some of the ToOwned needs...

[clarfonthey]

I don't think ToOwned belongs outside alloc. It is quite specific/biased to alloc types. For example, it considers alloc::string::String to be the (one and only) owned version of &str, even though there exist perfectly good alternatives in other crates (e.g. owned string types with small string optimization, or strings that store the length in the allocation, etc.).

So, my reasoning for this is that while most of the relevant types for this do exist in the alloc crate, there's nothing that explicitly requires it other than the fact that it would be incoherent to defer implementations to the alloc crate.

There currently isn't a supported way to do this besides (maybe) the proposed rust-lang/rfcs#3482, but it feels kind of arbitrary to require that something depend on allocations to itself use the trait. The way it effectively would work is a negative impl in core that is "replaced" with a positive impl in alloc, although again, this is absolutely nothing that is currently supported.

(This example is probably way beyond the scope of this issue, although I figured I might as well explain what's going on in my head at the moment.)

[JustForFun88]

I would love it if we could find a lang way to allow splitting Clone into

pub trait CloneFrom<Other: ?Sized> {
    fn clone_from(&mut self, other: &Other);
}
pub trait Clone : CloneFrom<Self> where Self: Sized {
    fn clone(&self) -> Self;
}

It would be great. This would also eliminate the need for A: Clone in CloneFrom for collections including Hashbrown.

[dtolnay]

#116113 has a different approach for ?Sized Clone.

[safinaskar]

Is this true that after this change std::collections::HashMap will be vulnerable to that DoS?

[KisaragiEffective]

The only difference is HashMap can be referred from #![no_std] environment.
It will not change std::collections::HashMap's default hasher (RandomState, which is HashDoS-resistant)

[safinaskar]

@KisaragiEffective, cool!

So, std::collections::HashMap and alloc::collections::HashMap will behave slightly differently? This will be very hard-to-discover, so this should be properly documented on both rustdoc pages.

Maybe we should call alloc::collections::HashMap differently to make sure nobody will assume it is DoS-resistant?

[bjorn3]

As I understand alloc::collections::HashMap will require explicitly passing a hasher (eg alloc::collections::HashMap::<u32, String, MyHasher> is a valid type, but alloc::collections::HashMap::<u32, String> is not due to missing the hasher), while std::collections::HashMap will default to RandomState if you don't explicitly pass a hasher. And unless you depend on libstd, HashMap::new() and other methods which assume RandomState to be the used hasher will be unavailable.

[clarfonthey]

Poking back in here just to reprocess the current requirements on implementing this.

My understanding is that right now, the issue is that the hashbrown crate internally uses liballoc for some of its methods in order to work, and thus can't be added as a dependency for the liballoc crate.

One of the biggest concerns was the fact that it references ToOwned, which we don't really want to add into the core crate.

Would it be possible to, perhaps, add ToOwned under a perma-unstable feature flag to core, alongside marking it for incoherent impls so it can have all its implementations in alloc? That way, hashbrown should be able to access it without us changing the public API.

(Also, if anyone with permissions to do so would like to update the issue description, that would be appreciated, since right now it is very outdated.)

[GrigorenkoPV]

I would love it if we could find a lang way to allow splitting Clone into

pub trait CloneFrom<Other: ?Sized> {
    fn clone_from(&mut self, other: &Other);
}
pub trait Clone : CloneFrom<Self> where Self: Sized {
    fn clone(&self) -> Self;
}

so that that CloneFrom can be in core for all the "update my arraystr from that str" cases, and thus reduce some of the ToOwned needs...

There's something similar in #126799

[clarfonthey]

To make my former request even easier, here's a potential issue description you could copy-paste in to make it more up to date:

Currently, `HashMap` and `HashSet` are only available in `std` because they depend on `RandomState`, even though this is only a *soft* dependency. These types could be moved to `alloc` as long as the user provides an implementation of `BuildHasher` themself.

Right now, this is difficult because the implementation for `HashMap` and `HashSet` is in the external `hashbrown` crate, which depends on the `alloc` crate, and thus can't be used as a dependency for `alloc`.

So, there are effectively two steps here:

- [ ] Make `hashbrown` crate able to work without depending on the `alloc` crate.
- [ ] Move code that doesn't depend on `RandomState` into `alloc` crate so we can have these types.
- [ ] Convert the `std` types into aliases which default the `BuildHasher` type to `RandomState`, and implement the various methods for this default on the alias instead of its own type.

### Unresolved Questions

* Should `hashbrown` still exist as a standalone crate once this move is complete? Its primary purpose at the moment is to have `no_std` support, so, we could potentially solve a lot of these problems by just moving its code directly into `alloc`. However, its `RawTable` API would have to be made available in these cases, and it's unclear how long that would take to stabilise.

### Implementation history

*None currently.*

Rendered version

Currently, HashMap and HashSet are only available in std because they depend on RandomState, even though this is only a soft dependency. These types could be moved to alloc as long as the user provides an implementation of BuildHasher themself.

Right now, this is difficult because the implementation for HashMap and HashSet is in the external hashbrown crate, which depends on the alloc crate, and thus can't be used as a dependency for alloc.

So, there are effectively two steps here:

• Make hashbrown crate able to work without depending on the alloc crate.
• Move code that doesn't depend on RandomState into alloc crate so we can have these types.
• Convert the std types into aliases which default the BuildHasher type to RandomState, and implement the various methods for this default on the alias instead of its own type.

Unresolved Questions

• Should hashbrown still exist as a standalone crate once this move is complete? Its primary purpose at the moment is to have no_std support, so, we could potentially solve a lot of these problems by just moving its code directly into alloc. However, its RawTable API would have to be made available in these cases, and it's unclear how long that would take to stabilise.

Implementation history

None currently.

[clarfonthey]

Current progress/conclusion on figuring out how to make this work: I'm, very close to just copying the hashbrown code directly into liballoc. This would effectively solve all the current issues, but it would mean that we'd have to find another way to expose the RawTable APIs that crates currently depend on. So, here's my thought process:

1. We make hashbrown just contain these raw table APIs which are currently unstable. Or at least, make its other stuff under a feature flag which does not require alloc. (Not requiring alloc can be a separate feature flag only used by the standard library, since it will require unstable core::alloc stuff.)
2. We use those parts as the dependency in alloc, and then implement the proper HashMap and HashSet using those types.
3. The raw table APIs can continue to evolve and iterate and eventually find their way into alloc, but this doesn't necessarily block alloc from incorporating the parts that we consider stable. (the HashMap/HashSet APIs themselves)

This feels like the best conclusion since it avoids what I assume are some of the pitfalls to just moving everything into alloc:

• People still want the RawTable APIs, but they're not stable enough for the standard library to use.
• People currently depending on the no_std versions can still use them stably while the alloc version is unstable.

This feels like the right approach to me, but please feel free to provide your feedback/concerns before I go all in on it, since it'll probably be a bit.

[FeldrinH]

Correct me if I'm wrong, but another reason to use the hashbrown crate right now is the Equivalent trait, which allows you to use some types for lookup that you can't with the standard library API. What will happen to that trait and the related methods under the plan you outlined?

[bjorn3]

Could we handle hashbrown the same way as backtrace-rs? Keep it available as external crate, but at the same time use #[path = "..."] mod foo; to include it in the standard library.

[clarfonthey]

Could we handle hashbrown the same way as backtrace-rs? Keep it available as external crate, but at the same time use #[path = "..."] mod foo; to include it in the standard library.

I had no idea we did this in the standard library, or that it works as you'd expect. That feels promising, actually…

Correct me if I'm wrong, but another reason to use the hashbrown crate right now is the Equivalent trait, which allows you to use some types for lookup that you can't with the standard library API. What will happen to that trait and the related methods under the plan you outlined?

I think that the best path forward would be to try and get this incorporated into the standard library, rather than rely on it existing in hashbrown. While the raw table API is relatively complicated and thus won't be easy to stabilise, this isn't.

---

EDIT: Right now, hashbrown just refers to the equivalent crate, which currently has 8 dependents on crates.io. If people are using this trait and have compelling examples, I would recommend they file the ACP for that on the standard library, likely moving the trait to core::cmp::Equivalent. I was thinking of just writing up the ACP for this but genuinely cannot justify it myself, since as far as the publicly available data is concerned, nobody has ever had this problem.

EDIT 2: There appears to be an issue open on the equivalent crate repo for moving this to libstd, so, I would encourage you put your discussion there first: indexmap-rs/equivalent#3