Hello,
On a multi-core machine, am I guaranteed to have my code executed in the precise order it was written?
Cheers,
BJW
Printable View
Hello,
On a multi-core machine, am I guaranteed to have my code executed in the precise order it was written?
Cheers,
BJW
Yes, unless you make active use of multithreading language constructs there will only be one thread of execution also on a multicore computer.
No, you never are. The computer doesn't execute your code, it executes binary instructions. Your code is translated into these instructions by the compiler and linker. The C++ standard only mandates that the observable behavior of the program corresponds with your code. The compiler is free to make optimizations as long as the observable behavior remains the same. This is particularly the case for return value optimization and copy elision, which implies that you are never guaranteed that a certain exact number of copies of an object is made.Quote:
Originally Posted by sockman
The C++ standard implicitly assumes single-threaded execution, so if you use multiple threads in your program, you will need to provide synchronization between variables that are shared by multiple threads, where at least one thread writes to the variable.
Whether the program is executed on a single or multi-core machine makes no difference.
You can't rely on that even on a single core.Quote:
Originally Posted by sockman
For example, say you were to set a flag in a function to indicate to another thread that you had completed some action. Without a memory barrier, the compiler would be free to move the flag setting code to anywhere within the function, if moving it has no effect on the outcome of that function. Even marking the variable 'volatile' cannot guarantee this.
e.g.
The compiler may look at the code above and decide it is more optimal to set the flag at the beginning of the function.Code:bool done = false;
void Function()
{
// Do some processing.
...
// Flag as 'done'
done = true; // You cannot guarantee that this will happen last, after optimisation.
}
That's bullshit. The execution order is defined by the programming language alone. A program will run as written. Multicore hardware or not has no influence on that.Quote:
Originally Posted by D_Drmmr
That's bullshit. The execution order is defined by the programming language alone. A program will run as written. Multicore hardware or not has no influence on that.Quote:
Originally Posted by JohnW@Wessex
If it's defined by the programming language, then please quote the section of the standard that states this.Quote:
Originally Posted by nuzzle
Here's a quote from Herb Sutter about reordering of reads and writes.
Quote:
Second, what about nearby ordinary reads and writes -- can those still be reordered around unoptimizable reads and writes? Today, there is no practical portable answer because C/C++ compiler implementations vary widely and aren't likely to converge anytime soon. For example, one interpretation of the C++ Standard holds that ordinary reads can move freely in either direction across a C/C++ volatile read or write, but that an ordinary write cannot move at all across a C/C++ volatile read or write -- which would make C/C++ volatile both less restrictive and more restrictive, respectively, than an ordered atomic. Some compiler vendors support that interpretation; others don't optimize across volatile reads or writes at all; and still others have their own preferred semantics.
Quote:
Originally Posted by nuzzle
Are you really saying that you believe a, b & c are guaranteed to be initialised in that order? Everything I've read about compiler optimisations and CPU instruction reordering imply otherwise.Code:int a;
int b;
int c;
void Function()
{
a = 0;
b = 1;
c = 2;
// Some other stuff.
}
What a silly request.Quote:
Originally Posted by D_Drmmr
A programming language defines an abstract computer and how it behaves is defined by the standard as a whole. But if you need a place to start you can have a look at 1.9 Program execution.
http://www.open-std.org/jtc1/sc22/wg...2010/n3092.pdf
You're confusing the language with implementations of the language.Quote:
Originally Posted by JohnW@Wessex
The language defines an abstract computer and it will execute a program written in that language exactly as the standard specifies.
Physical implementations of the abstract computer, such as compilers, interpreters and various hardware cannot change that. If they do they're not conformant with the language standard.
The OP askedQuote:
You're confusing the language with implementations of the language.
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'.Quote:
On a multi-core machine, am I guaranteed to have my code executed in the precise order it was written?
If you don't take this into account when writing multi-threaded / multi-core applications then you are heading for big trouble.
Here, section 1.9.1Quote:
Originally Posted by nuzzle
Next time, please take one minute to investigate before calling something bullshit or otherwise, provide some well-funded arguments.Quote:
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.
Let's consider a practical example that just popped up in another thread. We know the double check locking pattern for the implementation of a singleton is broken. However, this cannot be explained in terms of the code itself, only in terms of the hardware. So following your logic, this would mean that modern PC's are not conformant with C++ (whatever that should mean, I never heard of such a notion and don't think it makes any sense). That makes your point moot, because you cannot execute a program on an abstract machine.Quote:
Originally Posted by nuzzle
That is a pretty strong language for such a weak statement...Quote:
Originally Posted by nuzzle
Well, this IS correct, as regardless of the number of cores the order is not guaranteed :)Quote:
Originally Posted by nuzzle
Also, refer to:Quote:
Originally Posted by D_Drmmr
Quote:
Originally Posted by C++11 Clause 1.9 Note 5
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.Quote:
Originally Posted by sockman
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.
That's very wrong. I could see this coming and that's why I used strong words.Quote:
Originally Posted by sockman
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 !!!
Implementations of C++ can do as they please as long as they conform with the standard. And that includes the execution order of programs.Quote:
Originally Posted by JohnW@Wessex
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.
That's right and that's what I'm saying. The standard rules and the implementations comply.Quote:
Originally Posted by D_Drmmr
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.
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.
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 ...
@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.
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.Quote:
But "code executed" could also mean the execution of the machine code after compilation,
More words from Herb Sutter.
An excerpt from Lock-Free Code: A False Sense of Security.
(my highlighting)
Quote:
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.
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.Quote:
Originally Posted by nuzzle
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.Quote:
Originally Posted by nuzzle
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.Quote:
Originally Posted by JohnW@Wessex
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.
Well appearantly it's not a given to all.Quote:
Originally Posted by laserlight
And note that it's the standard that decides what has unspecified order, not 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.Quote:
Originally Posted by nuzzle
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.Quote:
Originally Posted by nuzzle
An extremely important caveat that, if ignored, can cause huge problems.Quote:
...with the caveat that in some cases the order of evaluation is unspecified by the standard.
Well, we don't all have the luxury of using compilers compliant to that standard.Quote:
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.
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.Quote:
Originally Posted by JohnW@Wessex
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.
Quote:
Originally Posted by nuzzle
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.Quote:
Originally Posted by nuzzle
Yes, when writing multi-threaded/multi-core applications I claim (with third party citations) that the observed behaviour of one thread from the point of view of another is not defined. The compiler and CPU can rearrange the order of execution (allowed by the C++ standard). The observed order of execution within the thread is defined (by the C++ standard); not so from the point of view of a second thread (not defined by the C++ standard that most people still use.).Quote:
You claim that the execution order of a C++ program is not defined.
Exactly the point I've been trying to make all along! :rolleyes:Quote:
The old C++ standard didn't cover concurrent usage....
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
I don't consider the C++ standard "purely academic".Quote:
Originally Posted by laserlight
The C++ standard defines a nondeterministic (as opposed to a deterministic) abstract machine and the reason is the fact you keep coming back to namely that some orders are unspecified and left to the implementations.
Neither do I ;)Quote:
Originally Posted by nuzzle
It doesn't matter how many time you make this point, it's still wrong as I explained in #29.Quote:
Originally Posted by JohnW@Wessex
Err... so you are saying that your statement below is wrong?Quote:
Originally Posted by nuzzle
It sounds reasonable to me.Quote:
Originally Posted by nuzzle
Sure it's reasonable because I wrote it. :)Quote:
Originally Posted by laserlight
And not only reasonable, it's a fact I think everyone can agree on. The old C++ standard didn't cover concurrent usage very well if at all. But this doesn't give people carte blance to claim that execution order is not defined by the C++ standard (see my post#29). The standard rules and the implementations comply is an important principle especially for newbies and the OP to understand (see my post #23).
That's it for me unless someone has something new to add. Thank you for this discussion.
But I was agreeing with you. :confused:Quote:
Originally Posted by nuzzle