Random with certain seed still seems random

Question

I've got a program which makes heavy use of random numbers to decide what it needs to be doing, and has many many execution paths based on the output of the PRNG. After pulling my hair out trying to debug it, I decided to make all PRNG calls reference the same Random instance, which has been seeded to a hard coded number at instantiation. That way, every time I run the program, the same bug should appear. Unfortunately, I still get different bugs each time I run it (though it seems to behave almost the same way).

I've searched the code many many times for any missed calls to Math.random() and I assure you there are none.

Any ideas?

Edit: I have confirmed that numbers being generated are the same, yet behaviour is still non-deterministic. This program is not multi-threaded. Still completely baffled.

So the PRNG is behaving as expected, but I still have non-determinism. What are some ways that non-determinism might inadvertently be brought into a program?

Answer 1

Ok I think I've located my source of non-determinism. I was iterating over a HashSet at one point. The HashSet would have been populated by the same things in the same order, but because I haven't specified the hash method of the class being added to the HashSet, it would be defaulting to some hash depending on memory location of each instance.

Changing each instance of HashSet to LinkedHashSet seems to have been giving me consistent results for ~30 runs now, where before it would only give me the same behaviour up to a few times in a row.

Answer 2

OK, so this seems like a voodoo. Try creating a custom PRNG that wraps a Random object and logs calls with stacktraces.

public class CustomRNG {

    private static Logger logger = Logger.getLogger(CustomRNG.class.getName());
    private static Random random = new Random(1234);

    public int nextInt() {

       int val = random.nextInt();
       log(val);

       return val;
    }

    private void log(int value) {
        logger.log(Level.INFO, "value: " + value, new Throwable());
    }
}

This will log every call to nextInt, including value and a stacktrace (add call counting if you like). Try to run your app a few times and see at which point (stack trace) this diverges.

Answer 3

Possible causes of continued non-determinism (in decreasing order of likelihood):

• You haven't replaced all the PRNG calls with the same random instance. You probably want to check this first :-) A good IDE should help you track down all the references to the Random class.
• There are timing effects caused by concurrency (e.g. it matters which thread calls the PRNG first)
• You have some form of external input into the system (e.g. user input? actions taken based on the system timer?)
• Some library you are using has a non-deterministic element which is affecting teh behaviour of your program (for example, some sorting algorithms use random numbers which can affect the ordering of results they return)
• You are hitting some kind of environmental constraint (e.g. an OutOfMemoryError or IOException error which is happening sometimes but being caught and recovered from in different ways, or the GC deciding to clear some soft/weak references)
• Cosmic rays / hardware errors corrupting memory