Mismatched types and inaccessible methods for HashMap and HashSet in 0.16-rc

[alice-i-cecile]

Background

rust-lang/hashbrown#563 changed the default hasher for hashbrown to one that doesn't meet our needs. #15801 updated us to that version of hashbrown, following our dependencies. We were originally using hashbrown::HashMap over std::HashMap due to the use of a faster, more vulnerable hashing algorithm, as Bevy apps are generally not exposed to malicious input in this way.

#17460 shuffled our types around, moving HashMap and HashSet into bevy_platform_support, as they replace functionality provided by Rust's std`.

As part of #15801, we also changed hashers.

#18350 attempts to explain this problem somewhat in the docs.

Problems

As discussed in bevyengine/bevy-website#2065, the migration for this is terrible: it's more explicit in confusing ways, there are prominent methods like new and with_capacity that are simply unusable, despite showing up in the docs!

Potential solutions

Use hashbrown's default hasher

This might or might not be slower than whatever we're using. It fixes the migration / UX issues, and avoids duplicate dependencies though!

The really critical stuff is already generally using EntityHashMap etc, which is very optimized. See #17078 for an example.

Downgrade to hashbrown 0.14

This gets us parity with Bevy 0.15, but duplicates the dependency in our tree.

It also doesn't allow us to use the deterministic FixedHash (or whatever else we may choose) by default.

Petition for a better API upstream that can handle non-standard hashers with generics

This would be great, but due to the need to specify generic type defaults when calling methods, it may not be readily accepted.

This is made much worse by the fact that hashbrown is used in and aligns with the std API for these types, which has very strict stability guarantees.

Fork hashbrown and change the default hasher

This also duplicates the code, but allows us to properly fix the issue and pull in new fixes and improvements from upstream.

This is strictly better than relying on 0.14 forever, but adds maintenance burden for a complex utilities crate.

[bushrat011899]

Slight variant on forking hashbrown would be to wrap hashbrown in a new-type, forwarding trait implementations to hashbrown and offering From for conversion and Deref/Mut to avoid recreating all methods from scratch.

[alice-i-cecile]

I'm in favor of "use hashbrown's default hash" as the Bevy 0.16 solution, but would accept "just revert to hashbrown 0.14", reverting #15801. I feel strongly that we shouldn't ship in the current state.

Long-term, the ideal solution is clearly "hasbrown / std make it easier to use alternate hashers", but I would grudgingly tolerate forking if that seems impossible. Newtyping hashbrown's types would work, but seems similarly miserable to forking, and I'm not convinced that all of the possible functionality can be reproduced using that approach.

@Amanieu, do you have opinions / insight here? You're much better acquainted with the various algorithms and the upstream maintenance considerations here.

[alice-i-cecile]

As an aside: I didn't realize the magnitude of UX issues here, and shouldn't have merged #15801 so readily. Dependency bumps are usually much less frustrating than this!

[SpecificProtagonist]

Use hashbrown's default hasher

We do use hashbrown's default hasher, just not its default buildhasher.

[Amanieu]

Hashbrown switched from ahash to foldhash because the latter is faster overall (see benchmarks in https://github.com/orlp/foldhash/). The HashMap::new method is only implemented when using hashbrown's default hasher and this has always been the case. My recommendation is that you stick to hashbrown's default hasher instead of explicitly specifying AHasher if you want to keep using HashMap::new.

[alice-i-cecile]

Can you explain the difference between a hasher and a buildhasher for me? Why shouldn't we use the default buildhasher?

Oh I see: that's the random vs fixed initialization. Bah, okay. We can sacrifice determinism here in favor of ergonomics by default IMO.

I really appreciate you chiming in here Amaneiu.

[Amanieu]

Also keep in mind that hashbrown may change the default hasher again in the future. You should not assume a specific hasher is used and should instead always use hashbrown::DefaultHashBuilder.

[Victoronz]

Was there public discussion where this restriction for HashMap::new was decided on? I haven't been able to find any so far.
The Rust API Guidelines recommend that the Default impl and the new constructor should match, so I'm curious on why a different decision was made here!

(Returning to DefaultHashBuilder for 0.16 seems sensible to me as well)

[Amanieu]

This restriction also exists in the standard library (since Rust 1.0). If HashMap::new were implemented for all hashers then the compiler would often fail to infer H. It was deemed more ergonomic to only implement HashMap::new for the default hasher and require other hashers to use HashMap::with_hasher.