views:

270

answers:

12

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?

+6  A: 

It could be:

  • Thread timing
  • Any kind of input (user, file, network, etc)
luke
+14  A: 

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 :-)

Péter Török
Yeah; we need code! Of course, all of these factors as well as decimal errors and pseudo-randomizations are technically deterministic as they run on a deterministic machine. They just appear non-deterministic to us when we can't track or understand the inputs and the millions of progressive states of our program on the backdrop of a less personally controlled time-sharing system. Its why theory and computer science are always important to teach alongside nuts-and-bolts programming skills.
Peter DeWeese
I should have made it clear that I only wanted a list of common possibilities, which is what I got. Thanks.
zoo
+3  A: 

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.

Andy_Vulhop
+7  A: 

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.

zr
Good catch. Heap/stack address randomization is a pretty standard feature nowadays. That would have an effect if pointers are used as keys somewhere. I used that on couple of occasions to make the sort stable (if keys are equal, compare the pointers).
Dummy00001
Though, you'd have to be pretty unlucky/run on very low memory to have an allocation failure.
zneak
The output would depend on an address allocated on the heap if heap allocated objects are sorted by their address, for example if pointers to them are stored in an ordered container like a set.
Richard
+2  A: 

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

Hugh Brackett
+3  A: 

Besides a stray call to rand()

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

FredOverflow
A: 

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

sdg
A: 
  • Inputs from network / internet.
  • date / time
tenfour
+1  A: 

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.

AndreyT
A: 

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.

T.E.D.
A: 

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.

Longpoke
A: 

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

Sylvain Defresne