Order of operation on multi core hardware

[sockman]

OK thanks everyone for your replies. I think it is pretty much as I expected - order of execution is not guaranteed. Again, thanks for taking the time to answer.
Cheers,
BJW

[Lindley]

OK thanks everyone for your replies. I think it is pretty much as I expected - order of execution is not guaranteed. Again, thanks for taking the time to answer.
Cheers,
BJW

Make sure you understand why. It has nothing to do with being on a multi-core machine.

There are two separate issues here. First, if you write a multi-threaded program, you will need to synchronize data between threads no matter how many cores you run it on. That's the whole point of threads.

Second, regardless of whether your program is multi-threaded or not, compiler optimizations can affect the exact order in which instructions are carried out, so long as the end result is consistent with the program you wrote.

[nuzzle]

I think it is pretty much as I expected - order of execution is not guaranteed.

That's very wrong. I could see this coming and that's why I used strong words.

The fact is that the order of execution is defined by the C++ language and is independent of any (conformant) implementation of the language, be it compilers, interpretators or hardware.

Appearantly the inability to grasp this fundamental fact is widespread and so deeply rooted that people who should be expected to know better fail to do so even when presented with the relevant sections in the standard. Shocking !!!

[nuzzle]

The OP asked
He is talking about a real implementation of C++ code on a real machine. Real compilers can re-order reads and writes. Real CPUs can execute 'out of order'.
If you don't take this into account when writing multi-threaded / multi-core applications then you are heading for big trouble.

Implementations of C++ can do as they please as long as they conform with the standard. And that includes the execution order of programs.

So the exact opposite of what you say is true. You're in trouble if you rely on the peculiarities of a certain C++ implementation.

[nuzzle]

Here, section 1.9.1

"This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below."

Next time, please take one minute to investigate before calling something bullshit or otherwise, provide some well-funded arguments.

That's right and that's what I'm saying. The standard rules and the implementations comply.

How an implementation works is of no concern to the C++ standard. The implementation can execute anything it wishes in any order it wishes as long as the observed behaviour conforms with the standard. That is the execution order of a C++ program is exactly as defined by the standard regardless of how it's accomplished by a conformat implementation.

That's is a fundamental principle layed down in the standard (in the very section you quote) and since you claim it's not true you're talking bullshit. Next time please take a minute and try to understand what you quote.

[laserlight]

I think that the disagreement arises from different interpretations of the phrase "code executed in the precise order it was written".

I think we can agree that "precise order it was written" refers to the flow of control in the C++ code, rather than say, the order of authorship of the code

Now, "code executed" could mean the execution of the C++ code according to the abstract machine. If so, then clearly the code will be executed as specified, as long as it has well defined behaviour. But "code executed" could also mean the execution of the machine code after compilation, in which case it might not be executed as specified in the C++ code, but the result should be indistinguishable (other than in terms of efficiency) from it being executed as specified in the C++ code.

[superbonzo]

EDIT: oh, I missed laserlight reply, sorry ...

nuzzle, I don't think people is unaware of the meaning of "observable" as defined by the standard; but that's not the only meaning of the word "observable".

now, there are two possibilities:

1) the OP referred to the observable behavior of his code as defined by the standard ( that is, essentially, as viewed by the code itself and as viewed by the user relative to the execution environment and its API ). If this is the case, then you're right and everybody here would agree with you ... well, actually, even in this case it depends on:

1.1) if "is code executed in the precise order it was written ?" is meant as "given a well formed piece of code made of a sequence of full expressions, does the language guarantee that their observable side-effects are sequenced in the order in which they appear ?" then the answer is yes

1.2) if "is code executed in the precise order it was written ?" is meant as "given a well formed piece of code are all expressions guaranteed by the language to have an observable side-effect and to be sequenced in some specified fixed order?" then the answer is no, because order of execution can be unspecified or even undefined for some sub expressions ...

but is this interpretation of the OP words reasonable ? I think not, because it would be just silly even supposing the possibility of a language not specifing somehow its order of execution ...

2) the OP referred to the observable behavior of his code in a "physical" sense, that is, relative to any measure of the effects of code execution by any means provided by the execution environment. If this is the case, then you're wrong, as it's just a matter of debugging an optimized build to see those compiler reorderings taking place during execution ...

[nuzzle]

@laserlight & superbonzo

I think it's important to be crystal clear on this because it's of fundamental importance:

The execution order of a C++ program is determined by the standard and not by some implementation. An implementation of the C++ standard may do what it wants but if it does something observable it must conform with the standard. And with that guarantee the OP can rest assured his C++ code will be executed in the same order both on a singlecore and on a multicore computer.

If everyone agrees with this it's fine but judged by the many replies to the contrary I wouldn't bet on it. And the OP certainly walked away ill adviced with a big fat misconception.

[JohnW@Wessex]

But "code executed" could also mean the execution of the machine code after compilation,

Software is ultimately of no use to anyone until it's compiled and run, so I can't see any real point in interpeting "code executed" in any other way.

More words from Herb Sutter.
An excerpt from Lock-Free Code: A False Sense of Security.
(my highlighting)

Ordering Problems in Produce

Second, reads and writes of a lock-free variable must occur in an expected order, which is nearly always the exact order they appear in the program source code. But compilers, processors, and caches love to optimize reads and writes, and will helpfully reorder, invent, and remove memory reads and writes unless you prevent it from happening. The right prevention happens implicitly when you use mutex locks or ordered atomic variables (C++0x std::atomic, Java/.NET volatile); you can also do it explicitly, but with considerably more effort, using ordered API calls (e.g., Win32 InterlockedExchange) or memory fences/barriers (e.g., Linux mb). Trying to write lock-free code without using any of these tools can't possibly work.

Consider again this code from Produce, and ignore that the assignment iTail isn't atomic as we look for other problems:

list.push_back(t); // A: add the new item
iTail = list.end(); // B: publish it

This is a classic publication race because lines A and B can be (partly or entirely) reordered. For example, let's say that some of the writes to the T object's members are delayed until after the write to iTail, which publishes that the new object is available; then the consumer thread can see a partly assigned T object.

[laserlight]

I think it's important to be crystal clear on this because it's of fundamental importance:

The execution order of a C++ program is determined by the standard and not by some implementation. An implementation of the C++ standard may do what it wants but if it does something observable it must conform with the standard.

I think that that is so fundamental that it is a given, with the caveat that in some cases the order of evaluation is unspecified by the standard.

And with that guarantee the OP can rest assured his C++ code will be executed in the same order both on a singlecore and on a multicore computer.

Well, most likely the OP's C++ code will not be executed (unless you count template metaprogramming). Rather, it will be translated at compile time, with the result executed at run time.

[nuzzle]

Software is ultimately of no use to anyone until it's compiled and run, so I can't see any real point in interpeting "code executed" in any other way.

More words from Herb Sutter.
An excerpt from Lock-Free Code: A False Sense of Security.
(my highlighting)

It doesn't matter how many Sutter quotes you post, you're still wrong. The order of execution is defined by the standard and not by the implementations.

It's common knowledge that the C++ standard has been lacking when it comes to concurrency. Extreme care had to be taken to get it right (as Sutter notes). But this has been addressed in the new C++ 11 standard. It has a new memory model which regulates concurrent accesses to memory, and a new threading support library. The standard isn't perfect, but it keeps getting better.

Of course software is made to be run but it better be written by programmers who understand the fundamentals of computing.

[nuzzle]

I think that that is so fundamental that it is a given, with the caveat that in some cases the order of evaluation is unspecified by the standard.

Well appearantly it's not a given to all.

And note that it's the standard that decides what has unspecified order, not the implementations.

[JohnW@Wessex]

It doesn't matter how many Sutter quotes you post, you're still wrong. The order of execution is defined by the standard and not by the implementations.

So Sutter's quote 'This is a classic publication race because lines A and B can be (partly or entirely) reordered' is complete nonsense? Or the compiler he is postulating using is playing fast and loose with the standard? No offence, but when it comes to chosing between you or Sutter as an authoritative reference to designing multi-threaded/multi-cored software, I'll stick with Sutter.

An implementation of the C++ standard may do what it wants but if it does something observable it must conform with the standard.

As Sutter shows, it depends on who the observer is. In a single threaded context, all is hunkydory. But there are no guarentees made for observed behaviour between threads, otherwise designing lock free code would be easypeasy.

...with the caveat that in some cases the order of evaluation is unspecified by the standard.

An extremely important caveat that, if ignored, can cause huge problems.

It's common knowledge that the C++ standard has been lacking when it comes to concurrency. ... But this has been addressed in the new C++ 11 standard.

Well, we don't all have the luxury of using compilers compliant to that standard.

[nuzzle]

So Sutter's quote 'This is a classic publication race because lines A and B can be (partly or entirely) reordered' is complete nonsense? Or the compiler he is postulating using is playing fast and loose with the standard? No offence, but when it comes to chosing between you or Sutter as an authoritative reference to designing multi-threaded/multi-cored software, I'll stick with Sutter.

As Sutter shows, it depends on who the observer is. In a single threaded context, all is hunkydory. But there are no guarentees made for observed behaviour between threads, otherwise designing lock free code would be easypeasy.

An extremely important caveat that, if ignored, can cause huge problems.

Well, we don't all have the luxury of using compilers compliant to that standard.

This is complete non-sense on all accounts. You claim that the execution order of a C++ program is not defined. It is, by the C++ standard in outmost detail. Even unspecified order is carefully defined.

The old C++ standard didn't cover concurrent usage. This is a well-known shortcoming and every "authority" agrees on the solution; Never make concurrent accesses to shared memory and if you do be damned sure you know what you're doing because you're in uncharted territory not covered by the standard; If you're not a masochist use a concurrency library that's been written by experts and that's been certified to work with the code your compiler produces.

The new C++ standard does cover concurrency. The new memory model avoids, if not all but hopefully most, problems discussed in the Sutter quotes and elsewhere. In addition it has standard library support for multithreaded programming. Even so I strongly recommend the use of a concurrency library. Multithreading is hard even without the glitches of the old standard.

All compilers I know of are non-compliant in some respect. Usually it's restricted to more esoteric parts of the language. But I dare claim that no compiler can afford to be non-compliant when it comes to something of such paramount importance as execution order.

So the situation is crystal clear. It's the C++ standard alone that defines the execution order of a C++ program, not the implementations of the C++ standard. If the standard is unclear or inandequate it should be improved but this doesn't change anything in principle. The standard rules and the implementations comply.

[laserlight]

It is, by the C++ standard in outmost detail. Even unspecified order is carefully defined.

So the situation is crystal clear. It's the C++ standard alone that defines the execution order of a C++ program, not the implementations of the C++ standard.

Actually, if a C++ program contains an expression for which the order of evaluation is unspecified by the standard, then the order of evaluation is implementation defined. In this sense, implementations of the C++ standard do define the execution order of certain C++ programs. Of course, "implementation defined" means that the behaviour is within the parameters set out by the standard, but it is still implementation defined as to what the order of evaluation ultimately is, so any argument that "it's the C++ standard alone that defines the execution order of a C++ program" is purely academic.