Random Stability

[felixdube]

In my tests, I always seed the Python random package, and when I want to reproduce the same results, I just re-use the same seed. In the past, this has been working well.

Now, I am working with a pretty complex random object, and even when I use the same seed, I do not get all the same random values (some are the same, some are not). The random object contains random values, random list, random list with random size, random attributes, random enum, and a bunch of constraints.

I tried to do a standalone test which I could share here, but I was not able to reproduce the issue.

First of all, is this the expected behaviour? Should I expect the same random values when using the same seed (and the same code)? If this is the expected behaviour, how could I go about debugging my issue? I tried setting debug to True in the randomize call, but the info it gives does not really help me.

Best,
Felix

[alwilson]

From what you've described so far I think you're doing the right thing. Pyvsc objects should pull from the random package seed on the first randomization call, if you haven't set the seed yourself already via set_randstate(). Subsequent randomizations should work off each object's seed/randstate then and hopefully be stable.

Maybe pinning each object to a static seed one by one until the issue is gone to narrow it down?
Adding in the "Managing Random Stability" doc in case that helps or if you haven't seen it:
https://fvutils.github.io/pyvsc/methods.html#managing-random-stability

Alternatively you could reach into each object and get the underlying state from the random library, although it's very verbose. Maybe you could hash it and compare the states between two runs and see where/when they diverge?

# Set object randstate
obj.set_randstate(vsc.RandState.mkFromSeed(0))

# Print object randstate hash
print(hash(obj.get_randstate().rng.getstate()))

[felixdube]

Thanks @alwilson for the quick response!
I've tried recording the rand state, post randomisation, for all my random objects and the values are always the same from run to run even when the generated random values are not the same.

I also compared the debug output between different runs and I noticed that the output always start diverging while processing the same rand set. I am not entirely sure what the swizzling is all about, but I looks like it is not always the same fields that are selected for swizzling.

[alwilson]

I think you found a bug, @felixdube ! I believe I reproduced what you were seeing.

The swizzler can sample from 2 different lists, the unordered fields within a randset and the ordered list of fields set by vsc.solve_order.

pyvsc/src/vsc/model/solvegroup_swizzler_partsel.py

Lines 42 to 47 in 5f79289

	if rs.rand_order_l is not None:
	# Perform an ordered randomization
	for ro_l in rs.rand_order_l:
	swizzled_field |= self.swizzle_field_l(ro_l, rs, bound_m, btor)
	else:
	swizzled_field |= self.swizzle_field_l(rs.rand_fields(), rs, bound_m, btor)

You mentioned using randsz_list_t too, so I combined those together. I tried re-seeding and randomizing within a single run, but that was repeatable. Running the entire program appears to change the randsz_list_t field order. I'll have to take a look later with the debugger. I didn't see this happen without vsc.solver_order (yet...) so I'm thinking that code path is the culprit. I tried setting the random package's seed, but I'm not sure that does anything to pyvsc's random usage, or whatever is underlying this.

import vsc
import random

@vsc.randobj
class my_s(object):

    def __init__(self):
        self.a = vsc.rand_bit_t(8)
        self.l = vsc.randsz_list_t(vsc.rand_bit_t(8)) # rand_list_t also causes bug

    @vsc.constraint
    def al_c(self):
        vsc.solve_order(self.a, self.l)

        self.a > 0
        self.a < 20

        self.l.size == 2

        with vsc.foreach(self.l) as it:
            it < self.a

random.seed(0)

obj = my_s()
obj.set_randstate(vsc.RandState.mkFromSeed(0))
obj.randomize(debug=False)
print(obj.a, obj.l)

Output:

$ for i in {1..10}; do ./rand_stability.py; done
3 [1, 2]
3 [1, 2]
3 [1, 2]
3 [2, 1]
3 [1, 2]
3 [1, 2]
3 [1, 2]
3 [1, 2]
3 [1, 2]
3 [2, 1]

I think you may want to file this as a bug.

[alwilson]

(Oh, there's a reply/thread option in discussions.)

Ah, I found it! Ordering constraints use toposort, which internally converts lists of dependencies into python sets, which don't guarantee order. I'm not sure how sets decide what order to take when converted back into a list, but I assume there's some address space randomization plus hashing that gives it back in a random order.

pyvsc/src/vsc/model/rand_info_builder.py

Line 138 in 5f79289

for fs in list(toposort(rs_deps)):

class wrapper():
    def __init__(self, idx):
        self.idx = idx

ws = set([wrapper(i) for i in range(10)])

print([w.idx for w in ws])

Output:

$ for i in {0..10}; do ./settest.py; done
[4, 7, 1, 0, 9, 2, 5, 6, 3, 8]
[4, 7, 1, 0, 9, 2, 5, 6, 3, 8]
[0, 1, 9, 2, 5, 6, 3, 7, 8, 4]
[4, 0, 1, 9, 2, 5, 6, 3, 7, 8]
[0, 1, 9, 2, 5, 6, 3, 7, 8, 4]
[0, 1, 9, 2, 5, 6, 3, 7, 8, 4]
[4, 0, 1, 9, 2, 5, 6, 3, 7, 8]
[4, 0, 1, 9, 2, 5, 6, 3, 7, 8]
[4, 1, 0, 9, 2, 5, 6, 3, 7, 8]
[4, 7, 1, 0, 9, 2, 5, 6, 3, 8]
[4, 0, 1, 9, 2, 5, 6, 3, 7, 8]

[mballance]

Great work tracking this down, @alwilson and @felixdube. So, looks like we need a specialized toposort implementation that doesn't use sets and, thus, is predictable.

[mballance]

Just cut a new release (0.9.1) that contains @alwilson's PR for this.

[felixdube]

Wow you guys were quick! Thank you so much! I confirm that it does fix the random stability issue in my project.

[alwilson]

I'll admit that it nerd sniped me. :) I've had to deal with random instability issues in other tools before that have driven me crazy, so I was extra motivated. Glad it fixed your issue! I realized after I made the PR that it was possible I could have found a different unrelated bug... Hopefully that's the only one.