Avoid hashing more than is strictly necessary, in the compiler.

[eddyb]

It should be possible to build cheaper interners than what we currently have, using raw_entry.
cc @rust-lang/compiler @gankro @Amanieu

[Zoxc]

I have a branch which adds functions for interning based on this PR. I suggest that further work be based on that.

cc @nnethercote

Also relevant #55514 #56241

[eddyb]

@Zoxc That is, change the implementation of the HashSetInterner trait to use the new APIs?
That seems good, and I'd even call the abstraction HashingInterner, InternByHash or something similar (since the "set" aspect is less relevant than the fact that this is based on hashing).

[Zoxc]

Sure. I think we have to change things to use a HashMap anyway. HashSet hides all the fun bits.

[eddyb]

Oh, another place where we could take advantage of computing the hash only once is the query engine, in case we had to compute a query, and we're inserting the result.

[michaelwoerister]

Another note, not directly related to interners: We have some things in the compiler that already contain high-quality hash values of themselves. E.g. it's unnecessary work to hash a DefPathHash. There's at least one such map here:

rust/src/librustc/ty/context.rs

Line 919 in 691a7f8

pub def_path_hash_to_def_id: Option<FxHashMap<DefPathHash, DefId>>,

There are probably a few additional, similar cases.

[eddyb]

@michaelwoerister I think we can maybe use a wrapper for the hash state that uses specialization to avoid double-hashing, in that case, instead of relying on raw_entry.

[michaelwoerister]

I think the raw_entry API would be the nicer way to do it. It seems to be tailored to support a case just like this (among other use cases).

[eddyb]

@michaelwoerister Yes but it would require making an entire wrapper of the HashMap public API which carefully avoids letting anything hash the key (going as far as wrapping the key in a type that panics in its Hash impl).

[michaelwoerister]

What would your solution look like?

[eddyb]

I'll reopen this because the discussion mentioned things other than interners.

Also, I still have to write those code examples for @michaelwoerister.

[Noratrieb]

The interners currently do use the raw entry APIs:

rust/compiler/rustc_data_structures/src/sharded.rs

Line 99 in cba1407

let entry = shard.raw_entry_mut().from_key_hashed_nocheck(hash, &value);

[oli-obk]

We should still look for other uses of hash maps with keys that are already hashes

[Mark-Simulacrum]

I ran some analysis to find the maps changed in #120076 by looking for things put into HashMaps that looked like they were already hashes, using a few heuristics (e.g., similar number of 1 and 0 bits). I think that found most or all of the problem places. I don't see a good way to assert we don't regress there -- with a TypeId for non 'static things, we could assert in Hash64/Hash128 etc impls that we're not hashing them with FxHash (or that we're only hashing them with Unhash). But that assert doesn't exist today, and I don't think adding e.g. specialization or a doc(hidden) method on Hasher in std makes sense for this at this time.

I think the next big opportunity for reducing hashing would be maps with dense, relatively small integer valued keys, where we actually don't need to hash because they're sufficiently dense that a vec makes more sense. We saw big wins with #119977 from both (a) removing the hashing and (b) improved cache locality due to keeping things closer together. But those typically aren't as easy of a transformation to make, and to some extent are a time/space tradeoff.