Use usize instead of u64 for hashes in HashMap

[bluss]

Just a note on the current implementation which stores the hash values per bucket as u64. We can't use more than usize's bits of a hash to select a bucket anyway, so we only need to store that part in the table. This would be an improvement on 32-bit platforms to make the hashmap's data structures smaller, hopefully improving cache utilization during insert and lookup.

[eddyb]

cc @rust-lang/compiler This might be relevant to rustc, although as tempting as x32-style schemes may seem, they're not that portable. Still, it would be interesting to see if we can better perf on linux.

[bluss]

I've made the PR #36595. Can anyone test see what effect it has on bootstrap on 32-bit?

[bluss]

If we're hunting hashmap improvements, maybe one should even get ordermap into finished shape, and use rustc as a benchmark for it.

[arthurprs]

We probably want to investigate switching the layout to HHHHHHKVKVKVKVKVKV as well, that will definitely improve the iteration and growing speed. There was an attempt here #21973

[arthurprs]

regarding the previous, I started experimenting in this branch arthurprs/hashmap2@e18a323 I'm a bit tired so I can't tell why insertions are quite slower, lookups are slight faster.

[arthurprs]

-- removed bench

[bluss]

That's very impressive @arthurps, any improvement like that must be welcome. Any downsides that you know of? The previous try stalled on code style / implementation details.

The simple u64 → usize PR be merged long before, since it's a simple change.

[bluss]

The lookup_100_000_multi_10p performance drop of course attracts some attention, is that something that's consistent between runs? Maybe there's a cache use change that can explain it.

[bluss]

Oh right, one drawback that was mentioned is that (K, V) is stored like that, which leads to losses to alignment especially if K and V are very different.

[arthurprs]

@bluss yeah I'm not sure that's noise.

Since Robin hood puts a good bound on the probing distance I think it may be a gain even if it wastes space in padding. I'll add a bench for that.

[arthurprs]

I was a little skeptical so I made a round of benchmark improvements arthurprs/hashmap2@f8bd579. I tried to make sure value was not a () and that it's actually accessed on lookup benchmarks. I think we can all agree that's more realistic. To my disbelief the improvements are real.

removed bench

[bluss]

It would make sense for .get(k).cloned() lookup to favour the kvkvkv layout more (at least more there than..) and .contains_key(k) for the kkkvvv layout, due to caching effects.

[alexcrichton]

Discussed at libs triage the other day, our thoughts are on the PR.