compare compiler performance with `hashbrown`

[nikomatsakis]

This https://github.com/Amanieu/hashbrown crate looks nice!

We should do a performance comparison.

cc @Amanieu

[Mark-Simulacrum]

Should be fairly easy -- well, except I think we now don't have the FxHash implementations in-tree so that might be a bit harder...

I think this is a great issue for someone to take on though, if they want to swap out the FxHash implementation and post a PR we can run perf on it!

[Centril]

Better yet... if it is a fully drop-in replacement for HashMap, could we just replace the standard library's implementation with the one in hashbrown?

[shepmaster]

a fully drop-in replacement

depends on if "drop in" means "adheres to every expected requirement of HashMap" or just "API compatible".

[shepmaster]

It also lists

Uses SIMD to speed up lookups

It'd be very good to performance test it on all the architectures we care about people running the compiler on. If we replace the standard library implementation , then expand that to every tier 1 platform.

[Amanieu]

@shepmaster "drop-in" means that I literally copied the HashMap API from libstd and ripped out the internals. The only significant change API-wise is that the default hasher is changed.

[Centril]

@Amanieu are there any guarantees not covered in the signatures that don't fit other than the default hasher? (we would retain the standard library's default hasher...)

[Amanieu]

There is one small detail due to the way re-hashing works: if the Hash impl panics during rehashing then any elements that haven't been rehashed yet will be dropped from the table. There is unfortunately no way around this since the full hashes are not stored in the table.

[Centril]

@Amanieu ah; that seems like sane behavior tho (or at least I don't think it's weird behavior...) and very subtle / unlikely to happen. I'm having a hard time imagining a situation where the the Hash impl would not panic on insertion but then panic on rehash... maybe for some type with interior mutability perhaps (where the Hash impl alters the value of the type / using some sort of global side effect, e.g. reading from file... but that's probably going to be an incorrect implementation...)? Perhaps I'm not creative enough... =P

[scottmcm]

Is there anything that needs to be accounted for in #54043 to ensure that such a replacement would be possible in the future?

[Amanieu]

@scottmcm There is no issue there, the raw entry API can easily be ported to hashbrown.

[Zoxc]

We'd also want a way to avoid double lookups when interning like my PR did. The raw_entry API is supposed to enable that for the libstd's HashMap.

It would be a good idea to pick up the refactoring to use a intern method in my PR. It could just be an utility function in rustc instead of being a method on the hash map.

[Amanieu]

I'm having some trouble replacing rustc_data_structures::FxHashMap: hashbrown uses core::arch for SSE2 support, but core::arch is missing in stage0.