1

The question is directed to the topics of C++ or Java memory model, which defines the behaviors a program is allowed to exhibit. A simple way of looking at the memory model is to consider it as a "filter", that defines a set of rules to dismiss executions (traces of actions) with illegal behaviors, the remaining set of executions are legal.

The question is: For a single thread program, given a fixed initial condition (e.g. input parameters, initial values of variables) and no interaction with external processes, is there a unique legal execution (i.e. only one execution satisfies the memory model)?

Follow up question: If there are more than one legal execution, what causes the non-determinism?

Remark: For C++, lets consider the sequenced-before order to be total.

Edit: As suggested in the comment by juanchopanza, the dynamic allocation address is one source for non-determinism for single-thread program.

314314314
  • 249
  • 1
  • 10
  • 8
    It's not 100% clear what you're asking - the memory model is irrelevant in the conditions you describe - there is nothing to be influenced by possible reorderings. So ignoring obvious edge cases (e.g. code exhibiting undefined behaviour), it sounds like you are asking whether a single-threaded program is deterministic? – Oliver Charlesworth May 28 '17 at 11:31
  • 1
    @OliverCharlesworth You are right, I am asking whether a single-threaded program is deterministic. In fact I am trying to understand all the factors that causes non-deterministic behaviors in a multi-thread program. – 314314314 May 28 '17 at 11:38
  • 3
    @314314314 It depends on the context in which the program runs. For example, a BST (e.g `std::map`) where the keys are object addresses. The ordering of the elements may depend on the addresses of dynamically allocated objects. These may appear to be non-deterministic because they depend on things outside of the scope of the program. – juanchopanza May 28 '17 at 11:41
  • @juanchopanza Thanks that's right, I was thinking too much in Java and missed this obvious source of non-determinism. Are there other sources that causes non-determinism? – 314314314 May 28 '17 at 11:51
  • I think non determinism in a multi-threaded program comes from being unable to predict the order of completion of execution between threads. For example that can lead to data being placed in sequential storage in an undetermined order. Or you may not know what thread will call a given function first. – Galik May 28 '17 at 11:51
  • 2
    C++ is **not** Java. –  May 28 '17 at 12:00
  • 1
    the question is, who cares about memory model on a single threaded application? the entire question is irrelevant. – David Haim May 28 '17 at 12:01
  • 1
    The answer is that there is an 'as-if' rule, and any execution that satisifies it is legal, so, in a word, 'no'. – user207421 May 28 '17 at 12:14
  • @user207421 What is that "'as-if' rule"? – curiousguy Dec 12 '19 at 10:33
  • Do you have floating point operations in your program? – curiousguy Dec 12 '19 at 12:13

2 Answers2

1

No, there is no unique execution path, nor a single end-state guaranteed for C++.

Even if there are sequenced-before guarantees, one of the most frequent causes are side effets in the evaluation of different arguments: the sequence of the argument evaluation is not defined by the standard and is implementation dependent. The following code can give several valid outputs for example, depending on the compiler used: 

int display (int i, int j) {
    std::cout << i << " " << j << std::endl; 
    return i<j ? i:j; 
}
void my_funny_func (int a, int b, int c) {
    std::cout << a << " " << " " << b << " " c << std::endl;
}
...
   int i=1, j=1; 
   my_funny_func(display(i,j), display(++i, j), display(i, ++j));

The standard limits the guarantees on execution path to observable behavior (i.e. file operations, operations on volatile variables and so on):

1.9/1: Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.

1.9/5: A conforming implementation executing a well-formed program shall produce the same observable behavior as one of the possible executions of the corresponding instance of the abstract machine with the same program and the same input. However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).

This is done on purpose: it is meant to maximize freedom for the optimizer to reorder non-observable events. But this leaves several possible outcomes (especially for non-volatile variables, which may be cached without being stored immediately to memory at every single change).

For java, I think the order of evaluation is determined more precisely (see this other answer). This will reduce significantly the number of valid execution paths.

Christophe
  • 68,716
  • 7
  • 72
  • 138
  • Thank you! A follow up question: other than the "indeterminate order of argument evaluation", is there any other causes for non-deterministic behaviors in C++? – 314314314 May 29 '17 at 05:38
  • 1
    Yes, you have for example the order in which static constructors are invoked. An there are a couple of nice things which are implementation defined and may therefore give different results on different compilers (example: sizeof, or object layout or whether a char is signed or not) or CPU architectures (example: alignment, or endianness). This is why writing really portable C++ code requires some discipline. – Christophe May 29 '17 at 06:33
0

In C++ there is a multiple path, both of which are legal.

 char * a = new char[2000];
 char * b = new char[2000];


 if( ((uintptr_t)a) < ((uintptr_t)b) ) {
      // even on the same operating system ALSR may cause different runs to execute in here.
 }

So there is not a single path in C++ which is legal - there are multiple paths.

mksteve
  • 12,614
  • 3
  • 28
  • 50