[Bug] test_tir_schedule_sampling.py:test_sample_compute_location can not pass on a M1 mac system

[wrongtest-intellif]

The result sampling dict is always {9: 12, 17: 11, 8: 16, 2: 14, -1: 10, 6: 15, 5: 11, -2: 11}

def test_sample_compute_location():
    n = 100
    sch = tir.Schedule(tiled_conv2d_with_padding, seed=42, debug_mask="all")
    pad_input = sch.get_block("PadInput")
    decision_dict = dict()
    for _ in range(n):
        _ = sch.sample_compute_location(pad_input)  # pylint: disable=invalid-name
        decision = sch.trace.decisions[sch.trace.insts[-1]]
        decision_dict[decision] = decision_dict[decision] + 1 if decision in decision_dict else 1

    n_candidates = 8
    expected_rate = 1.0 / n_candidates
    for _, cnt in decision_dict.items():

      assert (expected_rate - 0.03) * n <= cnt <= (expected_rate + 0.03) * n

E assert 16 <= ((0.125 + 0.03) * 100)

tests/python/unittest/test_tir_schedule_sampling.py:193: AssertionError
============================================================================================== short test summary info ===============================================================================================
FAILED tests/python/unittest/test_tir_schedule_sampling.py::test_sample_compute_location - assert 16 <= ((0.125 + 0.03) * 100)

[junrushao]

CC: @MasterJH5574

[MasterJH5574]

😨 I suggest setting a larger eps slightly. Looks like a same randomness seed behaves differently on different platforms...

[junrushao]

@MasterJH5574 it looks interesting given we already fixed the random seed, and we implemented our own PRNG - shouldn’t the result be deterministic then?

[MasterJH5574]

@MasterJH5574 it looks interesting given we already fixed the random seed, and we implemented our own PRNG - shouldn’t the result be deterministic then?

Really? I don't know that the PRNG is absolutely deterministic with a given seed.

Then I totally have no idea. On my machine the values of cnt are always always

11
14
15
13
11
13
12
11

@wrongtest Would you mind pasting your output?

[wrongtest-intellif]

12, 11, 16, 14, 10, 15, 11, 11

I'm not familiar with RNG issues but I find the implementation here:

tvm/src/tir/schedule/primitive/sampling.cc

Lines 134 to 135 in 187aeb5

	support::LinearCongruentialEngine rand_(rand_state);
	std::uniform_int_distribution<int32_t> dist(min_inclusive, max_exclusive - 1);

For LinearCongruentialEngine (Is it the PRNG generator mentioned by @junrushao1994?), the document of it says It strictly corresponds to std::minstd_rand and is designed to be platform-independent.

For uniform_int_distribution, however, some guys say it is not platform-independent. https://stackoverflow.com/questions/26538627/c11-cross-compiler-standard-library-random-distribution-reproducibility

[junrushao]

That's good point! Thanks for pointing this out :-)

@wrongtest so looks like our bound is probably too tight. Would you mind sending a PR tweaking it a little bit? Thanks!