Sources of non-determinism

Question

My supposedly deterministic program produces one of a few slightly different outputs on different runs. The input, compiler and computer are unchanging. I'm not sure which output is right because it always looks reasonable.

Besides a stray call to rand(), how could this be possible?

Answer 1

It could be:

• Thread timing
• Any kind of input (user, file, network, etc)

Answer 2

In several ways:

• using multiple threads in a way that involves a data race,
• using the current system time as input,
• using uninitialized variables,
• ...

We can surely make more guesses, but if you want to get meaningful help, maybe it would be good for you to publish the relevant parts of your code :-)

Answer 3

Without seeing some code (HINT HINT), the best I can think of would be looking for a pattern. Maybe something date-time specific.

Also, try looking for race conditions. That can look non-deterministic.

Answer 4

If your output depends on an address allocated on the heap:

int main(int argc, char* argv[])
{
   printf("%p", malloc(42));
   return 0;
}

For each run, the malloc() may return a different virtual address - not to mention NULL in case the allocation failed.

Answer 5

Using the value of a pointer instead of what it points to always produces interesting results.

Answer 6

Besides a stray call to rand()

rand() is entirely deterministic as long as you feed it the same initial seed.

Answer 7

Obviously a new instance of the Phase of the Moon bug.

Answer 8

• Inputs from network / internet.
• date / time

Answer 9

In the programs that don't interact much with the "outside world" the popular source of non-determinism is the reliance on pointer comparison. From time to time you might see it in the code: when a lexicographical comparison function runs out of things to compare (everything is equal) it compares the addresses of objects as the last resort. This can produce different orderings if the objects are allocated in the dynamic memory, since the actual allocation locations can differ from platform to platform and from run to run.

Answer 10

You didn't give a lot of info. However, as someone who does real-time programming for a living the most likely culprits I look for when such things happen is:

• Using uninitialized memory.
• A race condition.
• Some obscure combination of the above.

For instance, one such trouble I had once came down to shared library not being as "shared" as I thought, and trying to use a handle from one process to index a table that was as yet uninitialized in a second process. Depending on how things started up that may or may not have caused important data in yet a third process to get trashed.

Answer 11

Any undefined behavior. i.e: it will take hundreds of pages to explain every possible source of alteration of the output. Try debugging to find where alteration occurs, or reading some C++ spec.

Answer 12

If you program use float / double, there may be difference in the result if there are context switch on some architecture.

On x86, the FPU use extended precision for intermediary result, but when saved in memory (which happens when there is a context switch either process or thread), such precision is lost. That could cause some small divergence of the result (we've detected such problem in our program). One way to avoid this issue is to ask the compiler not to use FPU but SSE for floating point operations.

http://www.network-theory.co.uk/docs/gccintro/gccintro_70.html