Add an unstable 'extra randomization' compile-time flag for hashers

[Aaron1011]

When working on #64906, I ran into a latent dependency on the iteration order of a HashMap. This resulted in the PR becoming unmergeable - since a FxHashMap was being used, the iteration order ended up differing between platforms, which made it impossible to make the tests pass on all platforms.

It would be nice to have a way of exposing these kinds of hidden ordering dependencies before they result in blocked PRs.

I propose the following:

• Add a new feature called randomize_iteration to std and fxhash. When enabled, this feature will cause the iteration order of iter and iter_mut to be randomized per call.
• Add a config.toml key to enable both of these features.

This will allow producing a special build of the compiler that will (hopefully) expose many hidden ordering dependencies. The overhead could be very high, but that shouldn't matter too much - the only purpose of this build would be to run the testsuite.

Once std-aware Cargo is fully implement, we could consider making this usable by user-written crates (e.g. allowing people to opt-in to recompiling std in this mode).

[Mark-Simulacrum]

Isn't the correct way to deal with this to ... not use hashmaps? Like, FxHashMap is known to have an unstable iteration order, so we should either a) replace it with something that has a stable iteration order (maybe IndexMap, or I saw on Discord that this might have something to do with 32-bit vs. 64-bit systems hashing differently...).

I think this feature as-is isn't tenable, it's just too problematic in practice. You'll probably never finish a compiler build if it does have high overhead, and I suspect it will.

[the8472]

Instead of randomized iteration order you could start at a randomized offset and wrap around, that should be more cache-friendly than fully randomized memory accesses.

[the8472]

the iteration order ended up differing between platforms, which made it impossible to make the tests pass on all platforms.

Isn't the actual issue that FxHashMap doesn't use RandomState, i.e. that the iteration order appears to be the same for all instances on a platform? In the hierarchy of per-platform -> per-execution -> per-instance -> per-iteration couldn't the issue also have been avoided if it were randomized per-execution or per-instance?

Per-iteration randomization may lead to unexpected results such as map.iter().eq(map.iter()) == false even though map was not mutably borrowed.

The std::collections documentation is a bit vague on iteration order

For unordered collections like HashMap, the items will be yielded in whatever order the internal representation made most convenient.

This could be interpreted as iteration order being dependent on internal structure, and the structure of a shared reference is not expected to change.

[pnkfelix]

triage: leaving nominated for discussion, to see if there is any buy-in from any compiler team members. W.r.t. priority... I'll leave this unprioritized for now. (My instinct is that it is P-low, but if that's the case, that's ammunition for just closing it.)

[nikomatsakis]

Some thoughts:

• I could see something like this being useful with flushing out non-deterministic in builds
• But maybe we could instead have a lint (clippy-style) against iterating over a FxHashMap at all? We could set it to deny in the compiler crates
• Then we would provide a unordered_iter method where you're expected to comment why the ordering doesn't matter
• Or else you should use an IndexMap

Then we can basically make a quest issue to resolve all the lint warnings.

[nikomatsakis]

(It seems like a less intrusive and more reliable way of solving the problem.)

[nikomatsakis]

During the meeting I said that a design meeting felt like overkill, but I'm mildly changing my mind here. =) It seems like it could be fruitful to put some thought into the best way to solve this category of bug in general.

[Aaron1011]

Isn't the correct way to deal with this to ... not use hashmaps?

@Mark-Simulacrum The idea here is to detect incorrect dependencies on HashMap iteration order. Unless you're suggesting removing all HashMaps from the compiler, I'm not really sure what you mean,

Isn't the actual issue that FxHashMap doesn't use RandomState, i.e. that the iteration order appears to be the same for all instances on a platform?

@the8472: Yes, I believe that the issue would have been expoesd earlier if FxHashMAp used RandomState.

Per-iteration randomization may lead to unexpected results such as map.iter().eq(map.iter()) == false even though map was not mutably borrowed.

@the8472: That's fine - the point of this is to catch issues, not to be actually be used by a normal rustc build. In my view, any code that actually relies on this is suspect, and it would be good to know about it.