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
  • 7
    We would need to see some code before we make wild speculations. Aug 31, 2010 at 13:31
  • 2
    Does your code contain anything that strays into the land of undefined behavior? Aug 31, 2010 at 13:33
  • 1
    Who said compilers are deterministic? Aug 31, 2010 at 13:35
  • @AshleysBrain - See this question stackoverflow.com/questions/3053904/…
    – KeithB
    Aug 31, 2010 at 14:55
  • @Andy_Vulhop - It's never stopped anyone before, but I agree we would be more productive looking at the code. Aug 31, 2010 at 15:31

12 Answers 12

19

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

3
  • 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. Aug 31, 2010 at 17:56
  • I should have made it clear that I only wanted a list of common possibilities, which is what I got. Thanks.
    – zoo
    Sep 2, 2010 at 15:13
  • BTW, uninitialized variables are effectively deterministic unless you attach a debugger; however they're deterministic in the same way single threaded heap corruption is deterministic, which is not the deterministic you want.
    – Joshua
    Aug 17, 2019 at 18:22
8

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.

3
  • 3
    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
    Aug 31, 2010 at 14:10
  • Though, you'd have to be pretty unlucky/run on very low memory to have an allocation failure.
    – zneak
    Aug 31, 2010 at 17:26
  • 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
    Sep 2, 2010 at 11:06
7

It could be:

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

If your 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

4

Besides a stray call to rand()

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

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.

2

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

1

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.

0

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

0
  • Inputs from network / internet.
  • date / time
0

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.

0

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.