std HashSet is not deterministic on repeated simulation runs

[m-mueller678]

#[test]
fn test_madsim(){
    for _ in 0..2{
        println!("check");
        madsim::runtime::Runtime::check_determinism(32, madsim::Config::default(),||async move {
            println!("{:?}", (1..5).collect::<HashSet<u64>>());
        });
    }
    for _ in 0..2{
        println!("simulation");
        madsim::runtime::Runtime::with_seed_and_config(32, madsim::Config::default()).block_on(async move {
            println!("{:?}", (1..5).collect::<HashSet<u64>>());
        });
    }
}

All invocations in check_determinism produce the same ordering of elements. The first call to block_on also produces this same ordering. The second call, however, produces a different order:

check
{2, 3, 4, 1}
{2, 3, 4, 1}
check
{2, 3, 4, 1}
{2, 3, 4, 1}
simulation
{2, 3, 4, 1}
simulation
{3, 1, 2, 4}

[BaldDemian]

I did some research on madsim source code. The real cause of your mentioned problem is that both simulation run on the same system thread. While in the case of check_determinism, two check run on the different system threads. You can see two threads are spawned in this function:

madsim/madsim/src/sim/runtime/mod.rs

Lines 178 to 203 in aaa9f9a

	pub fn check_determinism<F>(seed: u64, config: Config, f: fn() -> F) -> F::Output
	where
	F: Future + 'static,
	F::Output: Send,
	{
	let config0 = config.clone();
	let log = std::thread::spawn(move || {
	let rt = Runtime::with_seed_and_config(seed, config0);
	rt.rand.enable_log();
	rt.block_on(f());
	rt.rand.take_log().unwrap()
	})
	.join()
	.map_err(|e| panic_with_info(seed, e))
	.unwrap();
	std::thread::spawn(move || {
	let rt = Runtime::with_seed_and_config(seed, config);
	rt.rand.enable_check(log);
	rt.block_on(f())
	})
	.join()
	.map_err(|e| panic_with_info(seed, e))
	.unwrap()
	}
	}

When a new madsim runtime is created, this function will be called, creating a new RandomState:

madsim/madsim/src/sim/rand.rs

Lines 173 to 180 in aaa9f9a

	/// Initialize std `RandomState` with specified seed.
	///
	/// You should call this function before constructing any `HashMap` or `HashSet` in a new thread.
	fn init_std_random_state(seed: u64) -> bool {
	SEED.with(|s| s.set(Some(seed)));
	let _ = std::collections::hash_map::RandomState::new();
	SEED.with(|s| s.replace(None)).is_none()
	}

However, RandomState::new uses thread-local variable KEYS, which is initialized in the first simulation, and reused in the second simulation, thus making the RandomState in the HashSet in the two simulation different.

https://doc.rust-lang.org/src/std/hash/random.rs.html#56-77.

Based on above discussion, I don't think this issue is a real bug in madsim. Maybe we should just create madsim runtime in different threads🤔.