C++ Threads, what's the status quo?
pon...@gmail.com
bunch of proposals and ideas which make me feel that threads in C++
will have a bright future, I did come across an article that seemingly
said that there was something wrong with the way people did the whole
thing.
While I'm certainly not qualified to judge the thing, I'd like to put
the post to the forefront, and let people who can to comment on this.
http://enfranchisedmind.com/blog/archive/2006/10/21/163
To quote a few lines(please redirect to the blog to see the details,
coz I haven't asked the one if I could put the entire post(which is
pretty long) here):
I'm reading this post on the C++ committee's dealings on threading,
and, I am pleased to announce, there is absolutely no chance what so
ever of anything sane, workable, or sensible accidentally arising from
these precedings...
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Gianni Mariani
...
> http://enfranchisedmind.com/blog/archive/2006/10/21/163
...
It appears the major gripe is the simplification to use fully
synchronized atomic access and the effect on performance.
While for some code this may be a major factor, in most cases it is not.
Threading is a complex beast to most people, and so is C++. If the
default model was to make things so complex that most people who are
already familiar with threaded code become alienated by complexity, then
we're not looking at a winning formula.
The few users with performance critical applications that need the
control of load/store visibility can continue to experiment and there is
nothing stopping them from using these "optimal" primitives in their
applications - like they are today.
Personally, I think it's a sound compromise.
Mathias Gaunard
> While people as brilliant as Hans have already come up with the whole
> bunch of proposals and ideas which make me feel that threads in C++
> will have a bright future, I did come across an article that seemingly
> said that there was something wrong with the way people did the whole
> thing.
> While I'm certainly not qualified to judge the thing, I'd like to put
> the post to the forefront, and let people who can to comment on this.
>
> http://enfranchisedmind.com/blog/archive/2006/10/21/163
He's basically only saying he doesn't like atomics because they disable
optimizations.
Given that it is simply their *goal*, this remark is just stupid.
He's also saying that a high-level language proposal was refused and the
same proposal as a library was considered.
It's simply because it was decided not to add needless elements to the
language. Only low-level ones are added.
> I'm reading this post on the C++ committee's dealings on threading,
> and, I am pleased to announce, there is absolutely no chance what so
> ever of anything sane, workable, or sensible accidentally arising from
> these precedings...
That guy clearly says he doesn't like C++. He probably doesn't even
realize how C++ code should be.
For example, he says he doesn't understand why so much attention was
given to the design rather than the behaviour.
Francis Glassborow
pon...@gmail.com writes
>While people as brilliant as Hans have already come up with the whole
>bunch of proposals and ideas which make me feel that threads in C++
>will have a bright future, I did come across an article that seemingly
>said that there was something wrong with the way people did the whole
>thing.
>While I'm certainly not qualified to judge the thing, I'd like to put
>the post to the forefront, and let people who can to comment on this.
>
>http://enfranchisedmind.com/blog/archive/2006/10/21/163
>
>To quote a few lines(please redirect to the blog to see the details,
>coz I haven't asked the one if I could put the entire post(which is
>pretty long) here):
>
>I'm reading this post on the C++ committee's dealings on threading,
>and, I am pleased to announce, there is absolutely no chance what so
>ever of anything sane, workable, or sensible accidentally arising from
>these precedings...
I am greatly saddened by the tone of that article. He chooses to quote
private discussions (and I am certain that he did so without the consent
of the person quoted and without the context)
The comments are arrogant and if he was just an observer the blogger is
unlikely to know as much as those who have been working on this solidly
for over a year.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' and "You Can Program in C++"
see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Howard Hinnant
pon...@gmail.com wrote:
> While people as brilliant as Hans have already come up with the whole
> bunch of proposals and ideas which make me feel that threads in C++
> will have a bright future, I did come across an article that seemingly
> said that there was something wrong with the way people did the whole
> thing.
> While I'm certainly not qualified to judge the thing, I'd like to put
> the post to the forefront, and let people who can to comment on this.
>
> http://enfranchisedmind.com/blog/archive/2006/10/21/163
>
> To quote a few lines(please redirect to the blog to see the details,
> coz I haven't asked the one if I could put the entire post(which is
> pretty long) here):
>
> I'm reading this post on the C++ committee's dealings on threading,
> and, I am pleased to announce, there is absolutely no chance what so
> ever of anything sane, workable, or sensible accidentally arising from
> these precedings...
It is so much easier to stand up, shout, point and ridicule, than it is
to actually help. People have been doing that since there were people.
Thank goodness there are some people who have the courage to put their
hide on the line and make concrete proposals for a better standard. You
can too. On the library side you can send proposals directly to me.
But check the attitude at the door. You may find out that you're not
the only smart person working towards a better C++ standard.
Howard Hinnant
Library Working Group Chair
Beman Dawes
> In article <1167139437....@79g2000cws.googlegroups.com>,
> pon...@gmail.com writes
>> While people as brilliant as Hans have already come up with the whole
>> bunch of proposals and ideas which make me feel that threads in C++
>> will have a bright future, I did come across an article that seemingly
>> said that there was something wrong with the way people did the whole
>> thing.
>> While I'm certainly not qualified to judge the thing, I'd like to put
>> the post to the forefront, and let people who can to comment on this.
>>
>> http://enfranchisedmind.com/blog/archive/2006/10/21/163
>>
>> To quote a few lines(please redirect to the blog to see the details,
>> coz I haven't asked the one if I could put the entire post(which is
>> pretty long) here):
>>
>> I'm reading this post on the C++ committee's dealings on threading,
>> and, I am pleased to announce, there is absolutely no chance what so
>> ever of anything sane, workable, or sensible accidentally arising from
>> these precedings...
>
> I am greatly saddened by the tone of that article. He chooses to quote
> private discussions (and I am certain that he did so without the consent
> of the person quoted and without the context)
Not to mention that it is almost certainly a mis-quote. I've said
several times that the committee would be bad shape without Hans'
encyclopedic knowledge of *garbage collection*. As for threading, the
committee has a number of people with both broad and deep knowledge and
experience.
--Beman
--
Bertrand Motuelle
> Francis Glassborow wrote:
> > I am greatly saddened by the tone of that article. He chooses to quote
> > private discussions (and I am certain that he did so without the consent
> > of the person quoted and without the context)
>
> Not to mention that it is almost certainly a mis-quote. I've said
> several times that the committee would be bad shape without Hans'
> encyclopedic knowledge of *garbage collection*. As for threading, the
> committee has a number of people with both broad and deep knowledge and
> experience.
>
> --Beman
To be fair with the blogger, the corresponding quotes can be found in a
public article of the C++ source:
http://www.artima.com/cppsource/threads_meeting.html
Bertrand.
Howard Hinnant
"Bertrand Motuelle" <tib.mo...@laposte.net> wrote:
> Beman Dawes wrote:
> > Francis Glassborow wrote:
> > > I am greatly saddened by the tone of that article. He chooses to quote
> > > private discussions (and I am certain that he did so without the consent
> > > of the person quoted and without the context)
> >
> > Not to mention that it is almost certainly a mis-quote. I've said
> > several times that the committee would be bad shape without Hans'
> > encyclopedic knowledge of *garbage collection*. As for threading, the
> > committee has a number of people with both broad and deep knowledge and
> > experience.
> >
> > --Beman
>
> To be fair with the blogger, the corresponding quotes can be found in a
> public article of the C++ source:
> http://www.artima.com/cppsource/threads_meeting.html
Yes, it would have been most helpful if the blogger had referenced where
he was getting his quotes from. I was familiar with the article and
thus easily able to locate it as well. But others might not be, or
might not go to the trouble to hunt the reference down.
-Howard
patrik...@googlemail.com
> > public article of the C++ source:
> > http://www.artima.com/cppsource/threads_meeting.html
I found a interesting follow up post called "The Solution to C++
Threading is Erlang":
http://radio.weblogs.com/0103955/categories/stupidHumanProgramming/2006/12/2
5.html
and a similar blog post about the erlang way..
http://codemines.blogspot.com/2006/09/hell-is-multi-threaded-c-program.html
They argue that multi threading is complicated and error prone, and
that the alternative of using shared memory stores between native OS
processes are to slow. But they say there is an alternative model. A
mix between the two. You could have threads that dont share any data
but only communicate thru messages. That kind of thread might sound
alot like a regular native OS process but i guess the difference is
that you have more control over them and they are more efficient
because they are supported directly by the language instead of by the
operating system.
Sounds simple and good to me. What do you guys think?
I guess the down side would be that to share any data you would be
sending a copy of it. The cost of getting simple value semantics might
just be worth it..
Regards Patrik
Sean Kelly
>
> They argue that multi threading is complicated and error prone, and
> that the alternative of using shared memory stores between native OS
> processes are to slow. But they say there is an alternative model. A
> mix between the two. You could have threads that dont share any data
> but only communicate thru messages. That kind of thread might sound
> alot like a regular native OS process but i guess the difference is
> that you have more control over them and they are more efficient
> because they are supported directly by the language instead of by the
> operating system.
>
> Sounds simple and good to me. What do you guys think?
This is already done informally in many multithreaded programs. The
producer-consumer model, for example, is message-oriented in nature.
But I do think it would be useful to formalize things further. Some
projects have attempted this in modern adaptions of Hoare's CSP, but
the designs I've seen aren't terrific from a semantic perspective.
Also, I think CSP itself isn't sufficient, because it doesn't apply
terribly well to distributed processing. And while the Pi calculus is
useful here, it isn't that great for in-process concurrency. An ideal
solution would adapt equally well to both low-latency and high-latency
communication channels, but while I've seen some projects in this area
(PEPA maybe? it's been a while since I looked), all were still in the
design phase.
> I guess the down side would be that to share any data you would be
> sending a copy of it. The cost of getting simple value semantics might
> just be worth it..
For in-process concurrency, data doesn't necessarily have to be copied,
it just can't be shared between threads. So I think the actual cost of
messaging is generally quite acceptable.
Sean
Thant Tessman
[...]
> It is so much easier to stand up, shout, point and ridicule, than it
> is to actually help. [...] Thank goodness there are some people who
> have the courage to put their hide on the line and make concrete
> proposals for a better standard. [...]
Threading is basically a solved problem and has been for a while.
Someone mentioned Erlang. I'll mention Concurrent ML. I'll also mention
first-class continuations which are supported by several languages and
with which you can construct your own threading mechanism that looks
like anything you want. Shoehorning threading into C++ just seems like a
misallocation of talent and effort--counterproductive even. Is it
"ridicule" to point this out?
-thant
Francis Glassborow
<a...@standarddeviance.com> writes
>Threading is basically a solved problem and has been for a while.
>Someone mentioned Erlang. I'll mention Concurrent ML. I'll also mention
>first-class continuations which are supported by several languages and
>with which you can construct your own threading mechanism that looks
>like anything you want. Shoehorning threading into C++ just seems like
>a misallocation of talent and effort--counterproductive even. Is it
>"ridicule" to point this out?
The only deduction I can make from this is that you believe C++ should
be dead and buried. C++ without threading will be tantamount to useless
by the end of this decade. Even mobile phones us multi-core processors
these days. And my point is that multi-threading is in the process of
becoming equivalent to concurrent programming and C++ needs to address
that issue.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' and "You Can Program in C++"
see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects
Mathias Gaunard
> You could have threads that dont share any data
> but only communicate thru messages.
> I guess the down side would be that to share any data you would be
> sending a copy of it.
Unfortunetely, SMP architectures are more popular.
So sharing is more efficient.
Le Chaud Lapin
Francis Glassborow wrote:
> The only deduction I can make from this is that you believe C++ should
> be dead and buried. C++ without threading will be tantamount to useless
> by the end of this decade. Even mobile phones us multi-core processors
> these days. And my point is that multi-threading is in the process of
> becoming equivalent to concurrent programming and C++ needs to address
> that issue.
I have a threading library in C++ that is portable to Windows & Linux,
and probably another other OS's where the kernel-mode people did their
part and provided the minimum set of synchronization primitives. It is
not a full-featured library. There are some questions that I did not
try to answer. There are also some areas that could be cleaner. But
the key point is that the interface is mostly clean, the interface is
portable, the model does not leave you wrestling with your own brain as
you use it, something I would imagine other people who have tried to
make "thread objects" have discovered (I learned the hard way that it
is not good to regard a thread as an object).
The point is that C++ and threading are alive and well. People use
them together. Some people use the native API of their OS, which is
not always pleasant to use. Some people wrap these API's.
But I do not think it is fair to say that we do not understand the
importance of multi-threading programming by C++ programmers. We do.
What we are saying is that the fundamentals of multi-threading, barring
some massive break through in the state-of-the -art, are
well-understood, and it is our opinion that those who think that the
language itself is somehow deficient in this regard are mistaken.
Anything that the C++ community does with regard to "adding threading
to the language" is going to eventually lead right to the primitives
that actually implement synchronization, primitives that are 40 years
old.
After all, when we talk about "threading", we are talking about
synchronization.
-Le Chaud Lapin-
--
Thant Tessman
I (Thant Tessman) wrote:
>> [...] Shoehorning threading
>> into C++ just seems like a misallocation of talent and
>> effort--counterproductive even. [...]
Francis Glassborow replied:
> The only deduction I can make from this is that you believe C++ should
> be dead and buried.
Yes. And I say this as someone who's made an admittedly comfortable
living programming with C++ since cfront.
> C++ without threading will be tantamount to useless
> by the end of this decade. Even mobile phones us multi-core processors
> these days.
My first-hand experience is that mobile phones in practice are
programmed usually with C, and/or a six, no, seven-year-out-of-date C++
compiler, and/or--just shoot me now--Java.
My guess is that future phones will be running either Linux, in which
case one's options could go far beyond C++ for multi-threaded
programming, or something from Microsoft, in which case they'll be
pushing their CLR.
> And my point is that multi-threading is in the process of
> becoming equivalent to concurrent programming and C++ needs to address
> that issue.
Why? (Yes, that was rhetorical.)
-thant
--
James Kanze
> Francis Glassborow wrote:
> > The only deduction I can make from this is that you believe C++ should
> > be dead and buried. C++ without threading will be tantamount to useless
> > by the end of this decade. Even mobile phones us multi-core processors
> > these days. And my point is that multi-threading is in the process of
> > becoming equivalent to concurrent programming and C++ needs to address
> > that issue.
> I have a threading library in C++ that is portable to Windows & Linux,
> and probably another other OS's where the kernel-mode people did their
> part and provided the minimum set of synchronization primitives. It is
> not a full-featured library. There are some questions that I did not
> try to answer. There are also some areas that could be cleaner. But
> the key point is that the interface is mostly clean, the interface is
> portable, the model does not leave you wrestling with your own brain as
> you use it, something I would imagine other people who have tried to
> make "thread objects" have discovered (I learned the hard way that it
> is not good to regard a thread as an object).
> The point is that C++ and threading are alive and well. People use
> them together. Some people use the native API of their OS, which is
> not always pleasant to use. Some people wrap these API's.
The point is that you don't know that it works, and that it
works only by chance (and may actually fail once you start using
a multi-core processor). The point is that you don't have any
guarantees with regards to what the language or the compiler
provides.
Maybe your happen with a definition of "working" as "it hasn't
crashed yet", but my customers generally aren't.
> But I do not think it is fair to say that we do not understand the
> importance of multi-threading programming by C++ programmers. We do.
> What we are saying is that the fundamentals of multi-threading, barring
> some massive break through in the state-of-the -art, are
> well-understood,
Which explains why so many programmers get it wrong. (The
people who implemented std::basic_string in g++ are not idiots;
they're some of the more gifted programmers I know. Never the
less, there is a threading error in the code.)
> and it is our opinion that those who think that the language
> itself is somehow deficient in this regard are mistaken.
You can think what you like, but you can't argue with hard
facts. It is impossible, today, to write a multi-threaded
program with defined behavior.
> Anything that the C++ community does with regard to "adding threading
> to the language" is going to eventually lead right to the primitives
> that actually implement synchronization, primitives that are 40 years
> old.
For the moment, I think the committee has only begun to scratch
the surface with regards to primitives. Before defining the
primitives, it is necessary to define a basic memory model; what
it means to read or wite to memory.
> After all, when we talk about "threading", we are talking about
> synchronization.
Hardly. There's a lot more to it than that.
--
James Kanze (Gabi Software) email: james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Le Chaud Lapin
> Le Chaud Lapin wrote:
> > The point is that C++ and threading are alive and well. People use
> > them together. Some people use the native API of their OS, which is
> > not always pleasant to use. Some people wrap these API's.
>
> The point is that you don't know that it works, and that it
> works only by chance (and may actually fail once you start using
> a multi-core processor). The point is that you don't have any
> guarantees with regards to what the language or the compiler
> provides.
I never asked the compiler for any guarantees. What did you study in
university? I do not mean to attack you personally, but frankly, these
concepts are as old as multi-threading itself. I am appalled that so
many people seem not to understand multi-threading.
> Maybe your happen with a definition of "working" as "it hasn't
> crashed yet", but my customers generally aren't.
One of my multi-threaded application has 11 threads in it at minimum,
rising to 35 if necessary. This application will never crash "because
of threading."
> > But I do not think it is fair to say that we do not understand the
> > importance of multi-threading programming by C++ programmers. We do.
> > What we are saying is that the fundamentals of multi-threading, barring
> > some massive break through in the state-of-the -art, are
> > well-understood,
>
> Which explains why so many programmers get it wrong. (The
> people who implemented std::basic_string in g++ are not idiots;
> they're some of the more gifted programmers I know. Never the
> less, there is a threading error in the code.)
There is no "threading" error in the code. If I write
int x == 10;
int thread1 ();
int thread2 ();
...and let those two threads fiddle with x without the protection of
mutual-exclusion, there will be contention. Are you saying that the
people who designed std:basic_string designed it expecting there would
be no contention?
> > and it is our opinion that those who think that the language
> > itself is somehow deficient in this regard are mistaken.
>
> You can think what you like, but you can't argue with hard
> facts. It is impossible, today, to write a multi-threaded
> program with defined behavior.
I do it every day. I know how to write multi-threaded applications.
There are probably 10,000's of programmers who do. One should not
assume that others are unable to do that which he cannot.
> For the moment, I think the committee has only begun to scratch
> the surface with regards to primitives. Before defining the
> primitives, it is necessary to define a basic memory model; what
> it means to read or wite to memory.
I am going to give the committee the benefit of the doubt and assume
that at least some of them understand the basics of synchronization and
OS design. But the more I read this thread (no pun intended), the more
I get the feeling is that real problem is simply that there
C++-is-lacking-thread support crowd is primarily composed of people who
have very little or no experience with multi-threading.
I wish someone who writes operating system books for a living were
reading this. I cannot stop laughing as I am reading this post. The
examples presented so far, two threads modifying a global
variable....leaves me...speechless.
In all fairness, I know that there are probably a few lurking
16-year-olds who, though bright, having gotten around to mutual
exclusion, and are so not sure who has more insight, so I offer this
link to get you started so you can plainly see that this is a very old
concept:
http://en.wikipedia.org/wiki/Mutual_exclusion
I did not study computer sciencel, but if you are reading this, and you
studied computer science, and you do not understand the basics of
mutual exclusion, or equivalently,
if you are in anyway, even _one iota_, surprised that a global static
variable used by std::string cannot be accessed read/write by multiple
threads without a mutex, I am sorry, there is simply no excuse - you
should be ashamed of yourself! ?????? What do you expect??!!
See the following link: http://bardavid.com/mead/
"The mutual exclusion problem was formally defined by Edsger Dijkstra
in 1965."
These concepts are more than 40 years old, and multi-threaded
applications are written all the time, not just in C/C++, but in *many*
languages.
I am so perplexed by this discussion, I am going to over to the threads
group to see what they have to say.
-Le Chaud Lapin-
Peter Dimov
[...]
> Shoehorning threading into C++ just seems like a
> misallocation of talent and effort--counterproductive even.
Threading (concurrency + shared address space) is already in C++, and
has been for years. The primary goal of the current standardization
effort is to provide a formal specification backing that, to describe
the behavior of the various library components under real-life MT
conditions, and to provide a portable and standard way to get to the
functionality that is already available, not to invent or to shoehorn.
Dilip
> James Kanze wrote:
> > You can think what you like, but you can't argue with hard
> > facts. It is impossible, today, to write a multi-threaded
> > program with defined behavior.
>
> I do it every day. I know how to write multi-threaded applications.
> There are probably 10,000's of programmers who do. One should not
> assume that others are unable to do that which he cannot.
Ooh! Bold assertion. Exactly the opposite of my experience. I am yet
to meet a guy who knows a synchronization primitive from his backside
and this is after he wrote an application that spawned 45 threads to do
some activity.
> > For the moment, I think the committee has only begun to scratch
> > the surface with regards to primitives. Before defining the
> > primitives, it is necessary to define a basic memory model; what
> > it means to read or wite to memory.
>
> I am going to give the committee the benefit of the doubt and assume
> that at least some of them understand the basics of synchronization and
> OS design. But the more I read this thread (no pun intended), the more
> I get the feeling is that real problem is simply that there
> C++-is-lacking-thread support crowd is primarily composed of people who
> have very little or no experience with multi-threading.
Good heavens! How did a statement like that pass the moderators? This
guy is giving the benefit of doubt to Hans Boehm? This kind of dual
standards is very confusing. In another thread (subject: "Threads -
When?") I tried to correct James Kanze's unfair (and uninformed)
characterization of Jeffrey Richter as someone who has "no clue what
multithreading is all about" and it never showed up even after 4 days
and some thing like the above breezes right past in?
Anyway, to the OP -- can you please read this:
http://www.artima.com/cppsource/threads_meeting.html
before adopting that elitist attitude.
Mirek Fidler
Le Chaud Lapin wrote:
> James Kanze wrote:
> > Le Chaud Lapin wrote:
> > > The point is that C++ and threading are alive and well. People use
> > > them together. Some people use the native API of their OS, which is
> > > not always pleasant to use. Some people wrap these API's.
> >
> > The point is that you don't know that it works, and that it
> > works only by chance (and may actually fail once you start using
> > a multi-core processor). The point is that you don't have any
> > guarantees with regards to what the language or the compiler
> > provides.
>
> I never asked the compiler for any guarantees. What did you study in
> university? I do not mean to attack you personally, but frankly, these
> concepts are as old as multi-threading itself. I am appalled that so
> many people seem not to understand multi-threading.
Ahh... I guess you should seriously reconsider the issue.
Recommended reading is e.g. google: "why double checked guard does not
work".
Just for starters, if you have
Shared y;
Mutex y_lock;
void fn() {
y_lock.Lock();
y = 10;
y_lock.Unlock();
}
nothing in C++ standard prevents C++ compiler to generate machine code
equivalent to
void fn() {
y = 10;
y_lock.Lock();
y_lock.Unlock();
}
(and now I recommend you to get some C++ reeducation before your
threads start to fail with new compiler version ;)
Mirek
Simon Farnsworth
> James Kanze wrote:
>> Le Chaud Lapin wrote:
>> > The point is that C++ and threading are alive and well. People use
>> > them together. Some people use the native API of their OS, which is
>> > not always pleasant to use. Some people wrap these API's.
>>
>> The point is that you don't know that it works, and that it
>> works only by chance (and may actually fail once you start using
>> a multi-core processor). The point is that you don't have any
>> guarantees with regards to what the language or the compiler
>> provides.
>
> I never asked the compiler for any guarantees. What did you study in
> university? I do not mean to attack you personally, but frankly, these
> concepts are as old as multi-threading itself. I am appalled that so
> many people seem not to understand multi-threading.
>
There are *important* threading related guarantees that the standard has
nothing to say about. For example, there's no way to ensure that cached
memory is consistent between two CPUs running two threads; you have no way
to tell if a particular operation represents a synchronisation operation.
Further, the standard is silent on whether you can assume strict
consistency, weak consistency, sequential consistency, causual consistency,
or another consistency model.
These are both important if you want to guarantee that an operation between
two threads working in parallel on the same block of memory does what you
expect. In a weak consistency model, it's impossible to implement a working
mutex without knowing which operations are synchronisation operations; your
environment typically handles this by arbitrarily declaring that some
library calls are synchronisation operations.
On top of this, in a weak consistency model, you need to know which
operations are synchronisation operations to be certain that two processors
have the same view of memory; without that knowledge, two different
processors reading from the same bit of memory are entitled to return
different values.
--
Simon Farnsworth
Chris Thomason
news:1168188975....@38g2000cwa.googlegroups.com...
>
> Le Chaud Lapin wrote:
>> James Kanze wrote:
>> I never asked the compiler for any guarantees. What did you study in
>> university? I do not mean to attack you personally, but frankly, these
>> concepts are as old as multi-threading itself. I am appalled that so
>> many people seem not to understand multi-threading.
>
> Ahh... I guess you should seriously reconsider the issue.
>
> Recommended reading is e.g. google: "why double checked guard does not
> work".
DCL works perfectly fine:
Le Chaud Lapin
> Le Chaud Lapin wrote:
> > There are probably 10,000's of programmers who do. One should not
> > assume that others are unable to do that which he cannot.
>
> Ooh! Bold assertion. Exactly the opposite of my experience. I am yet
> to meet a guy who knows a synchronization primitive from his backside
> and this is after he wrote an application that spawned 45 threads to do
> some activity.
That's why I wrote ten's of thousands instead of millions. I could take
the computer science students from the top computer science schools
around the world. I think I would be able to find 10,000's of people
in that group who understand the basics of synchronization.
> > I am going to give the committee the benefit of the doubt and assume
> > that at least some of them understand the basics of synchronization and
> > OS design. But the more I read this thread (no pun intended), the more
> > I get the feeling is that real problem is simply that there
> > C++-is-lacking-thread support crowd is primarily composed of people who
> > have very little or no experience with multi-threading.
>
> Good heavens! How did a statement like that pass the moderators? This
> guy is giving the benefit of doubt to Hans Boehm? This kind of dual
> standards is very confusing. In another thread (subject: "Threads -
> When?") I tried to correct James Kanze's unfair (and uninformed)
> characterization of Jeffrey Richter as someone who has "no clue what
> multithreading is all about" and it never showed up even after 4 days
> and some thing like the above breezes right past in?
It is not a dual standard. The moderators let it pass probably because
I was not the one who originally hinted that. And let's face it -
there are lurkers in this group (trust me) reading this thread, and
there is a strong polarization going on here. I can assure you that I
am not the only one who feels that there is a disconnect regarding the
difficulty to which multi-threading is done.
> Anyway, to the OP -- can you please read this:
> http://www.artima.com/cppsource/threads_meeting.html
> before adopting that elitist attitude.
Hmm....reading this link gave me the same feeling I get when we were
talking about whether C++ should be "migrated" to CLI, whether we
should add GC to the language, whether the type system of C++ was
fundamental or should be integrated with Microsoft's .NET CTS...
...basically, everything that involved changing C++ in such a way that
it would be more like languages that are not like C++.
There is a pattern that seems to be going on. I will post more in a
separate when I think I have figured out what that pattern is.
-Le Chaud Lapin-
Le Chaud Lapin
> Ahh... I guess you should seriously reconsider the issue.
>
> Recommended reading is e.g. google: "why double checked guard does not
> work".
>
> Just for starters, if you have
>
> Shared y;
> Mutex y_lock;
>
> void fn() {
> y_lock.Lock();
> y = 10;
> y_lock.Unlock();
> }
>
> nothing in C++ standard prevents C++ compiler to generate machine code
> equivalent to
>
> void fn() {
> y = 10;
> y_lock.Lock();
> y_lock.Unlock();
> }
>
Are you saying that the C++ standard does not prescribe sequential
execution of statements in a single-threaded program?
If that is the case, then I could write a single-threaded application
that would not behave as a programmer would expect using an example
very similar to the one you gave.
Also, do you have a link regarding the quote above for Google? I
looked, and did not find what I think you were suggesting.
-Le Chaud Lapin-
Chris Thomason
http://groups.google.com/group/comp.lang.c++.moderated/msg/e161a53de7c2290e
Sorry for any confusion!
;^(...
Le Chaud Lapin
> Ahh... I guess you should seriously reconsider the issue.
>
> Recommended reading is e.g. google: "why double checked guard does not
> work".
>
> Just for starters, if you have
>
> Shared y;
> Mutex y_lock;
>
> void fn() {
> y_lock.Lock();
> y = 10;
> y_lock.Unlock();
> }
>
> nothing in C++ standard prevents C++ compiler to generate machine code
> equivalent to
>
> void fn() {
> y = 10;
> y_lock.Lock();
> y_lock.Unlock();
> }
>
> (and now I recommend you to get some C++ reeducation before your
> threads start to fail with new compiler version ;)
First, I need to be really clear here. :) I did *NOT* write the code
above. You did. :D This could easily turn into a situation where people
start arguing that "my code does not work as expected." That is not my
code. And there is no place anywhere in any of my synchronization code
that uses double-checked locking. In fact, I did not even know what it
double-checked locking was (by name) until 15 minutes ago, after
finding a paper, per your suggestion. I did think about the concept
briefly, a few years ago, and soon realized that you get no free lunch
- that, if you want mutual exclusion, do not goof around. Ask for it,
have it, do your business, then let it go.
>From this paper...
http://www.cs.wustl.edu/~schmidt/editorial-3.html
it should have been obvious that, barring the volatile keyword,
double-checked locking will not work, because the compiler could easily
out-wit the double-check lock programmer by not honouring the
"redundant" read of the "inexpensive" pseudo-semaphore (state
variable). I did not look further, but it is my suspicion that, even
with volatile, it could still be circumvented.
Again, I did *not* write the code above, nor does my code use
double-checked locking. And if it is also true that sequence points
are honored by the C++ Standard after a semi-colon, then my
multi-threading framework still works, with the optimizer enabled, and
is portable.
In fact, part of the reason I took the talk-to-the-kernel-mode-people
position early on in this thread is that I am afraid that there will be
many attempts to find "tricks" like this in hopes of accomplishing
inherently needs to be done by the OS and hardware, and perhaps due to
lack of experience, big parts of the C++ Community will be lead down a
fruitless path hoping for that which simply cannot be attained within
the context of the language alone.
I use real mutual exclusion, always, either as a
spin-lock-with-mutex-failorver or mutex-only. I do not engage in
non-portable tricks that might be broken by turning on the optimizer.
-Le Chaud Lapin-
Le Chaud Lapin
> Further, the standard is silent on whether you can assume strict
> consistency, weak consistency, sequential consistency, causual consistency,
> or another consistency model.
>
> These are both important if you want to guarantee that an operation between
> two threads working in parallel on the same block of memory does what you
> expect. In a weak consistency model, it's impossible to implement a working
> mutex without knowing which operations are synchronisation operations; your
> environment typically handles this by arbitrarily declaring that some
> library calls are synchronisation operations.
I am happy to admit, I have no idea what these terms mean, but I will
look them up in about 10 minutes.
However, I see something missing in your post: atomic operations. This
is the essence of my thesis. I keep saying there will not be any
guarantees in any language if you do not have:
1. Harwdware-based atomic operations.
2. OS Support of synchronization.
People keep responding by demonstrating or alluding to C++ code that is
bound to not behave the way the programmer expected it to.
If that is the case, then I have said that a 1000 times:
No programmer in the world who is going to "implement safe threading in
C++" by writing generic C++ code without regard for 1 & 2 above.
*That* is where the guarantees come from.
-Le Chaud Lapin-
--
Le Chaud Lapin
> ACK! I forgot the darn link:
>
> http://groups.google.com/group/comp.lang.c++.moderated/msg/e161a53de7c2290e
>
> Sorry for any confusion!
>
>
> ;^(...
Hi Chris. I took a look at this link. I also wrote a post recently
essentially saying that DCL does not work, so a bit of clarification:
DCL will work easily if one goes to hardware. It appears from this
link that assembly language instructions are being used. That
Microsoft appears to have provided "support" for atomic operations at a
higher-level is obviously not portable.
There is a large group of people that is hell-bent on finding some way
to do DCL and other tricks purely in C++ and expecting it to be
portable, and it is impossible, as I keep stating.
But, if you allow for the possibility of a few assembly language atomic
operations, you have the entire world of synchronization at your
disposal, and that will work very well.
We must qualify the statement DCL works - it works when one is allowed
to exit the realm of portability. Otherwise it does not work (in
general).
-Le Chaud Lapin-
Mirek Fidler
Le Chaud Lapin wrote:
> Mirek Fidler wrote:
> > Ahh... I guess you should seriously reconsider the issue.
> >
> > Recommended reading is e.g. google: "why double checked guard does not
> > work".
> >
> > Just for starters, if you have
> >
> > Shared y;
> > Mutex y_lock;
> >
> > void fn() {
> > y_lock.Lock();
> > y = 10;
> > y_lock.Unlock();
> > }
> >
> > nothing in C++ standard prevents C++ compiler to generate machine code
> > equivalent to
> >
> > void fn() {
> > y = 10;
> > y_lock.Lock();
> > y_lock.Unlock();
> > }
> >
>
> Are you saying that the C++ standard does not prescribe sequential
> execution of statements in a single-threaded program?
Yes. It just prescribes that observable behavior is the same as if
statements were executed in sequential order. In this case, if compiler
is able to detect that Lock and Unlock do not touch y, it can produce
the code above.
> If that is the case, then I could write a single-threaded application
> that would not behave as a programmer would expect using an example
> very similar to the one you gave.
No, see above.
> Also, do you have a link regarding the quote above for Google? I
> looked, and did not find what I think you were suggesting.
Well, I suggested that quote not because of particular pattern, but
because discussion of problems nicely introduces you to associated
troubles.
--
Mirek Fidler
U++ team leader. http://www.ultimatepp.org
Mirek Fidler
Le Chaud Lapin wrote:
> We must qualify the statement DCL works - it works when one is allowed
> to exit the realm of portability. Otherwise it does not work (in
> general).
Great, I see my suggestion to study DCL was right.
Now just note that the same holds true for the whole threading issue.
And the whole purpose of C++ standard to achieve greater level of
portability...
--
Mirek Fidler
U++ team leader. http://www.ultimatepp.org
Mirek Fidler
Le Chaud Lapin wrote:
> Mirek Fidler wrote:
> > Ahh... I guess you should seriously reconsider the issue.
> >
> > Recommended reading is e.g. google: "why double checked guard does not
> > work".
> code. And there is no place anywhere in any of my synchronization code
> that uses double-checked locking. In fact, I did not even know what it
> double-checked locking was (by name) until 15 minutes ago, after
> double-checked locking will not work, because the compiler could easily
> out-wit the double-check lock programmer by not honouring the
> "redundant" read of the "inexpensive" pseudo-semaphore (state
You miss the point. In fact, I am using this pattern in my code
(because it simply is the most optimal way how to lazy-initialize
global structures), but I do not expect it to work across all platforms
/ compilers. In fact, on most implementations, you can make it work by
breaking it to more modules so that compiler has no way to expect
non-referencing control variable in calls to lock/unlock.
Anyway, AFAIK the real point of adding MT support to C++ is not about
adding synchronization primitives to the language or standard library,
but somehow adding guarantees that compiler does not make bad things
with your code while optimizing, while preserving compilers ability to
optimize well.
--
Mirek Fidler
U++ team leader. http://www.ultimatepp.org
James Kanze
> James Kanze wrote:
> > Le Chaud Lapin wrote:
> > > The point is that C++ and threading are alive and well. People use
> > > them together. Some people use the native API of their OS, which is
> > > not always pleasant to use. Some people wrap these API's.
> > The point is that you don't know that it works, and that it
> > works only by chance (and may actually fail once you start using
> > a multi-core processor). The point is that you don't have any
> > guarantees with regards to what the language or the compiler
> > provides.
> I never asked the compiler for any guarantees. What did you study in
> university? I do not mean to attack you personally, but frankly, these
> concepts are as old as multi-threading itself. I am appalled that so
> many people seem not to understand multi-threading.
What does my university training (or lack thereof---I never
studied at a university) have to do with it. I do know
something about multi-threading, and what I don't know, I know
people who I can ask. And I've something more than thirty years
experience, including having written an real time operating
system and a compiler, and having developed threading concepts
in several different projects. I've worked on multi-processor
systems as well, and know some of the issues involved there as
well.
What appalls me is that you don't read the postings you answer.
Rather than attacking people as incompetent, you should read
what they are saying. You critize arguments that were never
made, and proposals which no one in their right mind would
suggest, but you don't comment on the real problems being
exposed.
I've written compilers, and I know that the option exists to use
static memory. I've used compilers (g++ pre-3.0) which actually
did so. Unless the compiler gives you some explicit guarantee,
you don't know when it will do so, and you cannot use that
compiler in multi-threaded code. That's all there is to it. If
you don't know when it might use static data, you have no means
of knowing what you need to protect.
I also know how optimizers work, in particular, the importance
of moving loads forward. Even accross function boundaries, if
the function doesn't modify the variable being loaded. (Note
that if you read the Sparc specifications, you'll see that even
the hardware can do this, independantly of the compiler.)
> > Maybe your happen with a definition of "working" as "it hasn't
> > crashed yet", but my customers generally aren't.
> One of my multi-threaded application has 11 threads in it at minimum,
> rising to 35 if necessary. This application will never crash "because
> of threading."
Will never crash, or has never crashed? Will never crash means
that you've proved it correct, and to do that, you need some
guarantees from the compiler (and the standard library). How do
you know that when you write y = a * x + b, the compiler doesn't
store the intermediate result a*x in static memory, even if all
of the variables are local?
> > > But I do not think it is fair to say that we do not understand the
> > > importance of multi-threading programming by C++ programmers. We do.
> > > What we are saying is that the fundamentals of multi-threading,
barring
> > > some massive break through in the state-of-the -art, are
> > > well-understood,
> > Which explains why so many programmers get it wrong. (The
> > people who implemented std::basic_string in g++ are not idiots;
> > they're some of the more gifted programmers I know. Never the
> > less, there is a threading error in the code.)
> There is no "threading" error in the code. If I write
> int x == 10;
(I'll suppose you mean "int x = 10".)
> int thread1 ();
> int thread2 ();
> ...and let those two threads fiddle with x without the protection of
> mutual-exclusion, there will be contention. Are you saying that the
> people who designed std:basic_string designed it expecting there would
> be no contention?
I'm not sure what your point is. std::basic_string almost
certainly uses some static variables, if only to allocate
memory. The standard doesn't forbid it, and in fact, you can't
implement a memory allocator without it. The implementations I
currently use are guaranteed thread safe (or almost), and the
implementations of the allocators use locks or other
synchronization primitives to provide thread safety. And
explicitly document this fact. In the case of malloc, it's
required by Posix. But std::basic_string isn't required to use
malloc directly, and some implementations, including g++ and
Rogue Wave, use COW, which can also cause threading problems.
That's a fact of life. Whether you like it or not.
> > > and it is our opinion that those who think that the language
> > > itself is somehow deficient in this regard are mistaken.
> > You can think what you like, but you can't argue with hard
> > facts. It is impossible, today, to write a multi-threaded
> > program with defined behavior.
> I do it every day. I know how to write multi-threaded applications.
Apparently not. At least, you refuse to answer the problems
which are presented to you.
> There are probably 10,000's of programmers who do. One should not
> assume that others are unable to do that which he cannot.
I doubt that there are currently 10,000's of programmers who
write correct multi-threaded code. It can be extremely
difficult, and even the experts make mistakes at times: I found
an error in the implementation of basic_string in g++, and
several in ACE.
> > For the moment, I think the committee has only begun to scratch
> > the surface with regards to primitives. Before defining the
> > primitives, it is necessary to define a basic memory model; what
> > it means to read or wite to memory.
> I am going to give the committee the benefit of the doubt and assume
> that at least some of them understand the basics of synchronization and
> OS design.
That's nice of you. Given that the person currently doing the
most work on the threading issues is also one of the world's
experts on threading issues.
> But the more I read this thread (no pun intended), the more
> I get the feeling is that real problem is simply that there
> C++-is-lacking-thread support crowd is primarily composed of people who
> have very little or no experience with multi-threading.
I think the problem is that you aren't reading it. Because the
responses I've seen have consistently shown more threading
expertise than you have shown.
> I wish someone who writes operating system books for a living were
> reading this. I cannot stop laughing as I am reading this post. The
> examples presented so far, two threads modifying a global
> variable....leaves me...speechless.
Again, I can't find what your point is. It's well known that
two threads cannot modify shared data without synchronization.
The point that I've been making is that without compiler
support, you, the programmer, cannot provide that
synchronization because you don't know when shared data is being
modified.
> In all fairness, I know that there are probably a few lurking
> 16-year-olds who, though bright, having gotten around to mutual
> exclusion, and are so not sure who has more insight, so I offer this
> link to get you started so you can plainly see that this is a very old
> concept:
> http://en.wikipedia.org/wiki/Mutual_exclusion
> I did not study computer science, but if you are reading this, and you
> studied computer science, and you do not understand the basics of
> mutual exclusion, or equivalently,
> if you are in anyway, even _one iota_, surprised that a global static
> variable used by std::string cannot be accessed read/write by multiple
> threads without a mutex, I am sorry, there is simply no excuse - you
> should be ashamed of yourself! ?????? What do you expect??!!
Again, it would help if you'd read the posts you are replying
to. Where did anyone (but you) says anything so silly. What
everyone else in this thread is saying is that without explicit
guarantees, you don't know who uses shared variables, where.
That without explicit guarantees, the compiler can generate code
which uses them. That without explicit guarantees, the compiler
can move your code across synchronization primitives, so that it
is no longer protected.
> See the following link: http://bardavid.com/mead/
The link doesn't seem to be working for me at the moment.
> "The mutual exclusion problem was formally defined by Edsger Dijkstra
> in 1965."
Actually, it goes back to before that. Dijkstra formalized
certain aspects; Hoare as well.
> These concepts are more than 40 years old, and multi-threaded
> applications are written all the time, not just in C/C++, but in *many*
> languages.
> I am so perplexed by this discussion, I am going to over to the threads
> group to see what they have to say.
Doubtlessly what I've been saying, since I'm mostly quoting
things I learned from discussions there.
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
James Kanze
> "Mirek Fidler" <c...@ntllib.org> wrote in message
> news:1168188975....@38g2000cwa.googlegroups.com...
> > Le Chaud Lapin wrote:
> >> James Kanze wrote:
> [...]
> >> I never asked the compiler for any guarantees. What did you study in
> >> university? I do not mean to attack you personally, but frankly, these
> >> concepts are as old as multi-threading itself. I am appalled that so
> >> many people seem not to understand multi-threading.
> > Ahh... I guess you should seriously reconsider the issue.
> > Recommended reading is e.g. google: "why double checked guard does not
> > work".
> DCL works perfectly fine:
Except when it doesn't. In it's simplest instantiation, it
doesn't work at all in C++ (nor in Java). It's possible to
write a version which does work, but doing so requires using
special primitives---with Sun CC, under Solaris, on a Sparc, it
actually requires some inline assembler (and the guarantees that
the compiler doesn't reorder code around the assembler).
(Given that your posting ended with colon, and not a period, I
suspect that there is something which got lost. The problems
with DCL are well known and documented, and I can't imagine
anyone claiming it works today without presenting some arguments
as to why the documented problems aren't problems, or what you
have to modify in the basic instantiation in order to make it
work.)
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
James Kanze
> Le Chaud Lapin wrote:
[...]
> > I am going to give the committee the benefit of the doubt and assume
> > that at least some of them understand the basics of synchronization and
> > OS design. But the more I read this thread (no pun intended), the more
> > I get the feeling is that real problem is simply that there
> > C++-is-lacking-thread support crowd is primarily composed of people who
> > have very little or no experience with multi-threading.
> Good heavens! How did a statement like that pass the moderators?
Nobody's perfect. Try moderating awhile, and you'll see that
some things inevitably slip through.
> This
> guy is giving the benefit of doubt to Hans Boehm?
Rather amazing, isn't it.
> This kind of dual
> standards is very confusing. In another thread (subject: "Threads -
> When?") I tried to correct James Kanze's unfair (and uninformed)
> characterization of Jeffrey Richter as someone who has "no clue what
> multithreading is all about" and it never showed up even after 4 days
> and some thing like the above breezes right past in?
Don't quote me out of context. I said that one particular
statement Jeffrey Richter made gave the impression that... My
criticism was of the statement (and more generally, of the
article which contained it). The guy may actually be an expert,
but if so, he had an off day when he wrote the article. (Or
more likely, he had to produce an article, and didn't have any
good topic handy, so he invented one and tried to make it sound
interesting, even if it had no practical interest.)
> Anyway, to the OP -- can you please read this:
> http://www.artima.com/cppsource/threads_meeting.html
> before adopting that elitist attitude.
For example.
I participate in the standardization activities myself, when I
can. One of my motivations is that I know of no other group
with so much combined expertise; I learn something in almost
every discussion I participate in.
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
James Kanze
> Mirek Fidler wrote:
> > Ahh... I guess you should seriously reconsider the issue.
> > Recommended reading is e.g. google: "why double checked guard does not
> > work".
> > Just for starters, if you have
> > Shared y;
> > Mutex y_lock;
> > void fn() {
> > y_lock.Lock();
> > y = 10;
> > y_lock.Unlock();
> > }
> > nothing in C++ standard prevents C++ compiler to generate machine code
> > equivalent to
> > void fn() {
> > y = 10;
> > y_lock.Lock();
> > y_lock.Unlock();
> > }
> Are you saying that the C++ standard does not prescribe sequential
> execution of statements in a single-threaded program?
It most certainly doesn't. Doing so simply wouldn't be
acceptable because of the performance cost. All C++ compilers,
and all C compilers I used before, have done code movement in
some cases. It's a standard optimization technique.
> If that is the case, then I could write a single-threaded application
> that would not behave as a programmer would expect using an example
> very similar to the one you gave.
The standard defines the semantics of a program, in terms of its
observable behavior. A compiler can do anything it wishes, as
long as those semantics are respected. And those semantics are
only defined in the context of a single thread.
Note too that the reordering can also be done by hardware, even
if the compiler respects the semantics exactly. To prevent
this, you have to use special instructions. And compilers don't
introduce these instructions everywhere, simply because that
would slow things down too much.
In practice, this is nothing new, and nothing particular to C++.
IBM's Fortran H was reordering accesses way back in the late
1960's.
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
James Kanze
> Mirek Fidler wrote:
> > Ahh... I guess you should seriously reconsider the issue.
> > Recommended reading is e.g. google: "why double checked guard does not
> > work".
> > Just for starters, if you have
> > Shared y;
> > Mutex y_lock;
> > void fn() {
> > y_lock.Lock();
> > y = 10;
> > y_lock.Unlock();
> > }
> > nothing in C++ standard prevents C++ compiler to generate machine code
> > equivalent to
> > void fn() {
> > y = 10;
> > y_lock.Lock();
> > y_lock.Unlock();
> > }
> > (and now I recommend you to get some C++ reeducation before your
> > threads start to fail with new compiler version ;)
> First, I need to be really clear here. :) I did *NOT* write the code
> above. You did. :D This could easily turn into a situation where people
> start arguing that "my code does not work as expected." That is not my
> code.
That's clear. But the question remains, what do you do to
guarantee that the compiler doesn't do something like this
behind your back?
> And there is no place anywhere in any of my synchronization code
> that uses double-checked locking. In fact, I did not even know what it
> double-checked locking was (by name) until 15 minutes ago, after
> finding a paper, per your suggestion. I did think about the concept
> briefly, a few years ago, and soon realized that you get no free lunch
> - that, if you want mutual exclusion, do not goof around. Ask for it,
> have it, do your business, then let it go.
I don't think anyone was accusing you of using double checked
locking. Much discussion about what can and cannot happen,
however, has centered around this problem.
> >From this paper...
> http://www.cs.wustl.edu/~schmidt/editorial-3.html
> it should have been obvious that, barring the volatile keyword,
> double-checked locking will not work, because the compiler could easily
> out-wit the double-check lock programmer by not honouring the
> "redundant" read of the "inexpensive" pseudo-semaphore (state
> variable).
Using volatile doesn't change anything. And the problem
normally isn't that the compiler won't do the second read; if
the compiler is Posix conform, it knows that it will have to
resync its images of memory after a pthread_mutex_lock. (Of
course, since Posix doesn't define a C++ binding, strictly
speaking, there's no such thing as a Posix conform C++
compiler.) The immediate problem is that the compiler might
reorder the writes in the constructor with regards to the write
of the pointer. And making the pointer volatile doesn't change
that (except with the extension that Microsoft has proposed).
Even if one adds additional synchronization to guarantee the
order of the writes, it is still possible for the hardware to
reorder the reads in the branch which doesn't do any
synchronization; i.e. to read a non-null value for the pointer,
and then read older, uninitialized values in the object itself.
(I don't think the current Intel 32 bit architecture allows
this. Other architectures, including the IA-64 architecture and
Sparc, do.)
> I did not look further, but it is my suspicion that, even
> with volatile, it could still be circumvented.
Volatile doesn't change the problem an iota.
> Again, I did *not* write the code above, nor does my code use
> double-checked locking.
But of course, you count on the guarantee that the compiler and
the standard library doesn't do anything similar. From where do
you get that guarantee.
> And if it is also true that sequence points are honored by the
> C++ Standard after a semi-colon, then my multi-threading
> framework still works, with the optimizer enabled, and is
> portable.
Sequence points only define order between "observable behavior",
i.e. IO and accesses to volatile variables. A compiler can do
anything it wishes, as long as the observable behavior is
respected. And the observable behavior is not defined for
multi-threading.
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
Gerhard Menzl
> I never asked the compiler for any guarantees. What did you study in
> university? I do not mean to attack you personally, but frankly,
> these concepts are as old as multi-threading itself. I am appalled
> that so many people seem not to understand multi-threading.
[...]
> I am going to give the committee the benefit of the doubt and assume
> that at least some of them understand the basics of synchronization
> and OS design. But the more I read this thread (no pun intended), the
> more I get the feeling is that real problem is simply that there
> C++-is-lacking-thread support crowd is primarily composed of people
> who have very little or no experience with multi-threading.
>
> I wish someone who writes operating system books for a living were
> reading this. I cannot stop laughing as I am reading this post. The
> examples presented so far, two threads modifying a global
> variable....leaves me...speechless.
In the GC thread, I have presented you with a very simple example that
shows there is at least one language construct that cannot be made
thread-safe without the C++ standard acknowledging the existence of
concurrent paths of execution, using OS primitives alone. You replied,
essentially, with "then don't do this". In light of this, and in
knowledge of the credentials of some of the participants you are
effectively denigrating as threading hobbyists, the tone of your posting
leaves me, well, speechless.
--
Gerhard Menzl
Non-spammers may respond to my email address, which is composed of my
full name, separated by a dot, followed by at, followed by "fwz",
followed by a dot, followed by "aero".
James Kanze
> Thant Tessman wrote:
> [...]
> > Shoehorning threading into C++ just seems like a
> > misallocation of talent and effort--counterproductive even.
> Threading (concurrency + shared address space) is already in C++, and
> has been for years.
Yes and no. There has been ad hoc solutions which more or less
worked, for a given architecture, OS and compiler, but nothing
formal which the programmer could count on. Thus, for example,
I know that VC++ spills registers to stack, and not to static
memory, but I know it because I've looked at the generated code,
not because I've seen any written guarantee by the compiler.
And I have to do this analysis for each compiler I use.
> The primary goal of the current standardization
> effort is to provide a formal specification backing that, to describe
> the behavior of the various library components under real-life MT
> conditions, and to provide a portable and standard way to get to the
> functionality that is already available, not to invent or to shoehorn.
Correct. The goal is (or should be) always to standardize
existing practice. In this case, however, we also have to deal
with the fact that the existing practice often isn't even
documented---I know what the current releases of Sun CC and g++
do, but I can't be 100% sure that they will behave the same in
the next release (and of course, they behave differently). The
goal is, I think, a written guarantee which is portable.
(I guess I should also mention that the existing practice for
multi-threaded programs is largely one of subtle intermittent
crashes:-). But I doubt that the standard will be able to fix
that. You can lead a horse to water, but you can't make it
drink, and there's no guarantee that programmers will use
whatever the standard provides correctly.)
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
Thant Tessman
> Thant Tessman wrote:
>
> [...]
>
>> Shoehorning threading into C++ just seems like a
>> misallocation of talent and effort--counterproductive even.
>
> Threading (concurrency + shared address space) is already in C++, and
> has been for years.
Well, technically it's in the OS (if you're lucky). But yes, I should
have said "shoehorning threading into the C++ standard."
> The primary goal of the current standardization
> effort is to provide a formal specification backing that, to describe
> the behavior of the various library components under real-life MT
> conditions, and to provide a portable and standard way to get to the
> functionality that is already available, not to invent or to shoehorn.
I'll keep my fingers crossed.
For what it's worth, my experiences with threading were in persuit of
two different goals: The first was to take advantage of multiple CPUs.
The second was to allow a program to effectively do more than one thing
at a time. The first requires OS-level threading. However, for the
second, I have in the past successfully avoided the need for OS-level
threading (and all the headaches that that involves) even in C++ by
building a "task threader" on top of the UNIX/Linux 'select' or 'poll'
mechanism, where "tasks" were home-brew closures-as-function-objects.
Worked surprisingly well, but it really was just a poor-man's
continuations, which I've already mentioned.
-thant
Le Chaud Lapin
I use real locking. The above, if it is using DCL is not "real"
locking. This is why I so emphatically disclaimed that code. I did
that precisely to keep this from turning into a "But what do you do
about situation X.." conversation.
I have been saying all along. We should stop doing X and hoping that
things will work out magically. To do mutual exclusion, you need
low-level support. This is perhaps the 20th time I have said this in
the past 5 days. The above is not real synchronization. The above is
an attempt to gain a performance boost by avoiding real synchronization
"just for a little while."
> > I don't think anyone was accusing you of using double checked
> locking. Much discussion about what can and cannot happen,
> however, has centered around this problem.
Not my foot. I am glad that the truth is coming out - that the problem
is not so much synchronization, but that programmers are attempting to
play tricks with code without respect for the necessity of true
synchronization.
> Using volatile doesn't change anything. And the problem
> normally isn't that the compiler won't do the second read; if
> the compiler is Posix conform, it knows that it will have to
> resync its images of memory after a pthread_mutex_lock. (Of
> course, since Posix doesn't define a C++ binding, strictly
> speaking, there's no such thing as a Posix conform C++
> compiler.) The immediate problem is that the compiler might
> reorder the writes in the constructor with regards to the write
> of the pointer. And making the pointer volatile doesn't change
> that (except with the extension that Microsoft has proposed).
Again, I do not mind discussing synchronization, but I feel like I am
being drawn into a conversation to discuss that which I do not
recognized now. When I see that code above, and I know that there is
some DCL attempt in it that is not based on hardware-support, as far as
I am concerned, the conversation is over.
> Even if one adds additional synchronization to guarantee the
> order of the writes, it is still possible for the hardware to
> reorder the reads in the branch which doesn't do any
> synchronization; i.e. to read a non-null value for the pointer,
> and then read older, uninitialized values in the object itself.
> (I don't think the current Intel 32 bit architecture allows
> this. Other architectures, including the IA-64 architecture and
> Sparc, do.)
Again, you are talking about order of writes, and I am talking about
spin-locks and mutexes. Different conversation.
> But of course, you count on the guarantee that the compiler and
> the standard library doesn't do anything similar. From where do
> you get that guarantee.
You tell the library writes to do their part. As I stated before, if
it is true that the standard library breaks in a multi-threaded
application, and the standard library was meant to be used in a
multi-threaded application, then that is the standard library authors'
fault. If it is true that the standard library breaks in a
multi-threaded application, and the standard library was not meant to
run in a multi-threaded application, then that is the programmer's
fault.
If the standard library writer makes a library that depends on the
hope-this-works kind of DCL, that is the library writer's fault.
> > And if it is also true that sequence points are honored by the
> > C++ Standard after a semi-colon, then my multi-threading
> > framework still works, with the optimizer enabled, and is
> > portable.
>
> Sequence points only define order between "observable behavior",
> i.e. IO and accesses to volatile variables. A compiler can do
> anything it wishes, as long as the observable behavior is
> respected. And the observable behavior is not defined for
> multi-threading.
That is why it is so important to use synchronization.
-Le Chaud Lapin-
Simon Farnsworth
> Simon Farnsworth wrote:
>> Further, the standard is silent on whether you can assume strict
>> consistency, weak consistency, sequential consistency, causual
>> consistency, or another consistency model.
>>
> I am happy to admit, I have no idea what these terms mean, but I will
> look them up in about 10 minutes.
>
> However, I see something missing in your post: atomic operations. This
> is the essence of my thesis. I keep saying there will not be any
> guarantees in any language if you do not have:
>
Even with atomic operations, in consistency models weaker than strict
consistency, you cannot guarantee that threading will work properly when
you access a data structure from two different threads, unless you've got
some way of imposing cache synchronisation between two CPUs. For example,
in a weak model, the following pseudocode can produce "1, 1, 1" even if
thread_1 gets the lock first, although it's guaranteed to return 2:
int x = 1;
lock x_lock; // Atomic operations used to implement the lock.
int main()
{
x_lock.acquire();
start thread_2() on other CPU;
cout << x << ", ";
x = 2;
x_lock.release();
return x;
}
void thread_2()
{
x_lock.acquire();
cout << x << ", ";
x = 1;
cout << x << ", ";
x_lock.release();
}
The reason for this is that unless the caches are fully synchronised between
CPUs when the lock is released, the first CPU (running main) is entitled to
not write the change to x to memory until an arbitrarily later point. The
CPU running thread_2 will thus pick up the original value of x.
Fixing this requires the C++ standard to think about what operations should
act as consistency barriers; for example, one fix would be to add a special
operation that guarantees inter-CPU consistency for the variable it's
called on. Then, after writing x (but before releasing the lock), main
could make x's value consistent between CPUs.
An alternative fix might make the compiler guarantee that some operations
are cache synchronisation points; then (at the expense of less efficient
code for weakly consistent systems), the code would work as you'd expect.
At the moment, the standard is completely silent on what guarantees do and
do not exist; most small computer systems (less than 256 CPUs) guarantee at
least causal consistency, but there are serious hardware design advantages
to weaker models (like release consistency). If C++ wants to be the
language of choice on systems of all sizes, it needs to cope with this.
--
Simon Farnsworth
Peter Dimov
> James Kanze wrote:
> > Which explains why so many programmers get it wrong. (The
> > people who implemented std::basic_string in g++ are not idiots;
> > they're some of the more gifted programmers I know. Never the
> > less, there is a threading error in the code.)
>
> There is no "threading" error in the code. If I write
>
> int x == 10;
>
> int thread1 ();
> int thread2 ();
>
> ...and let those two threads fiddle with x without the protection of
> mutual-exclusion, there will be contention. Are you saying that the
> people who designed std:basic_string designed it expecting there would
> be no contention?
It's subtler than that. If you let the two threads read x without
changing it, do you expect problems?
Consider the similar example:
char x[] = "Test";
void thread1()
{
char a = x[0];
}
void thread2()
{
char b = x[0];
}
Do you expect problems here?
Now replace the definition of x with:
std::string x( "Test" );
James Kanze argues that the code remains correct, and that g++ is in
error to not work. Before jumping to conclusions about his
understanding of the threading issues, you first need to understand
what he's saying. (I happen to disagree with him that the code is
correct. Either way, one of the goals of the future C++ standard is to
resolve these issues by specifying the thread safety level of the
standard library components.)
Le Chaud Lapin
In this case, this is a problem that would be a serious issue, whether
we are talking about threading or not. If the compiler does not
guarantee order of execution, then it is very possible that Lock()
could depend on y being a certain value (not 10 for example).
So this is a serious issue in generally, and not necessarily related to
threading.
I am surprised that the compiler allows this.
-Le Chaud Lapin-
Pete Becker
>
> I have been saying all along. We should stop doing X and hoping that
> things will work out magically. To do mutual exclusion, you need
> low-level support.
And nobody has disagreed with you. But let's get down to the nub of the
matter:
static long counter;
Please write a function that increments the value of this static
variable and can be called safely from multiple threads. Use whatever
low level support you need, but state explicitly what that support is.
--
-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)
Mirek Fidler
Le Chaud Lapin wrote:
> > If the compiler does not
> > guarantee order of execution, then it is very possible that Lock()
> > could depend on y being a certain value (not 10 for example).
Well, compiler can know by knowing the content of Lock/Unlock. However,
example was a little bit stretched to show the point, so let me modify
it to be more realistic:
static Shared y;
Mutex y_lock;
void fn() {
y_lock.Lock();
y = 10;
y_lock.Unlock();
}
(and y is not used in call to any function not defined in the same
compilation unit).
The problem is that MT code is full of similar but less apparent
snippets. And C++ standard does not say a damn thing about the issue.
--
Mirek Fidler
U++ team leader. http://www.ultimatepp.org
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Edward Rosten
Mirek Fidler wrote:
> Shared y;
> Mutex y_lock;
>
> void fn() {
> y_lock.Lock();
> y = 10;
> y_lock.Unlock();
> }
>
> nothing in C++ standard prevents C++ compiler to generate machine code
> equivalent to
[snip reordering]
It looks like from this that y is global. If Lock() and Unlock() depend
on y, then the compiler couldn't reorder the bits of Lock() an Unlock()
depending on y. If the code for Lock() and Unlock() is not visible (eg
in a different translational unit), then how can the compiler reorder
the function calls?
Note, I'm not claiming that threading is defined. I'm just disputing
this one particular example.
You could probably construct it more carefully, eg by saying that y not
visible outside the translational unit, and &y is never assigned to a
pointer of Shared* which is visible outside the translational unit.
-Ed
--
Thant Tessman
> James Kanze wrote:
>> Le Chaud Lapin wrote:
>>> Mirek Fidler wrote:
[...]
>>> Are you saying that the C++ standard does not prescribe sequential
>>> execution of statements in a single-threaded program?
>> It most certainly doesn't. Doing so simply wouldn't be
>> acceptable because of the performance cost. All C++ compilers,
>> and all C compilers I used before, have done code movement in
>> some cases. It's a standard optimization technique.
> In this case, this is a problem that would be a serious issue, whether
> we are talking about threading or not. If the compiler does not
> guarantee order of execution, then it is very possible that Lock()
> could depend on y being a certain value (not 10 for example).
No, the compiler would only reorder these things when it could prove to
itself that there should be no dependency on the order of execution. The
problem is that the compiler makes assumptions that aren't necessarily
true under multi-threaded conditions.
-thant
James Kanze
[...]
> > That's clear. But the question remains, what do you do to
> > guarantee that the compiler doesn't do something like this
> > behind your back?
> I use real locking. The above, if it is using DCL is not "real"
> locking. This is why I so emphatically disclaimed that code. I did
> that precisely to keep this from turning into a "But what do you do
> about situation X.." conversation.
I fully understand what YOU do. What I'm asking is how you know
what the compiler and the library does? How do you know that
the compiler doesn't use something like this in its
implementation of exceptions, for example?
> I have been saying all along. We should stop doing X and hoping that
> things will work out magically.
And I keep repeating myself: X, in this case, is using the
compiler. I'm not willing to stop using the compiler, and I'm
not willing to write all my code in assembler. But this means
that I need some assurance concerning what the compiler does.
> To do mutual exclusion, you need
> low-level support. This is perhaps the 20th time I have said this in
> the past 5 days.
Yes. You seem to prefer repeating it, rather that addressing
the problems. You seem to recognize that synchronization is
necessary, but accept the fact that you don't know whether the
compiler and the library do it or not, or whether they define
exactly when it is necessary, and when not. And this, despite
repeated examples of cases where compilers have defined their
guarantees differently.
> The above is not real synchronization. The above is
> an attempt to gain a performance boost by avoiding real synchronization
> "just for a little while."
> > > I don't think anyone was accusing you of using double checked
> > locking. Much discussion about what can and cannot happen,
> > however, has centered around this problem.
> Not my foot. I am glad that the truth is coming out - that the problem
> is not so much synchronization, but that programmers are attempting to
> play tricks with code without respect for the necessity of true
> synchronization.
You mean, that the programmer is using a compiler, and doesn't
have any real guarantees with regards to what it does.
Except if one of the writes migrates across a spin-lock.
(Spin-locks are only guaranteed if special hardware instructions
are used on a Sparc---or a PC. Hardware instructions that are
never generated by Sun CC or by g++---or by the current version
of VC++.)
> > But of course, you count on the guarantee that the compiler and
> > the standard library doesn't do anything similar. From where do
> > you get that guarantee.
> You tell the library writes to do their part.
First you have to define what that part is. Suppose that the
library writer says that you need to manually acquire a lock
before calling malloc (or operator new)?
> As I stated before, if
> it is true that the standard library breaks in a multi-threaded
> application, and the standard library was meant to be used in a
> multi-threaded application, then that is the standard library authors'
> fault.
What does "meant to be used in a multi-threaded application"
mean? For, say, tmpnam, or localtime? Or operator new, or
std::allocator?
If the library implementation doesn't fulfil the contract, then
it is the library implementors fault. But for that to be the
case, you first need the contract.
> > > And if it is also true that sequence points are honored by the
> > > C++ Standard after a semi-colon, then my multi-threading
> > > framework still works, with the optimizer enabled, and is
> > > portable.
> > Sequence points only define order between "observable behavior",
> > i.e. IO and accesses to volatile variables. A compiler can do
> > anything it wishes, as long as the observable behavior is
> > respected. And the observable behavior is not defined for
> > multi-threading.
> That is why it is so important to use synchronization.
Agreed. But the issues are a lot more complicated than you seem
to think. I know, from experience.
--
James Kanze (Gabi Software) email: james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Chris Thomason
> (Given that your posting ended with colon, and not a period, I
> suspect that there is something which got lost.
Yup, it go lost. So, here it is:
http://groups.google.com/group/comp.lang.c++.moderated/msg/e161a53de7c2290e
Sorry for any confusion!
--
Le Chaud Lapin
> Le Chaud Lapin wrote:
> >
> > I have been saying all along. We should stop doing X and hoping that
> > things will work out magically. To do mutual exclusion, you need
> > low-level support.
>
> And nobody has disagreed with you. But let's get down to the nub of the
> matter:
>
> static long counter;
>
> Please write a function that increments the value of this static
> variable and can be called safely from multiple threads. Use whatever
> low level support you need, but state explicitly what that support is.
There are two ways to do this: one using a mutex, the other using a
critical section. Assuming the underlying OS is Windows:
The mutex is simpler but slower:
Mutex counter_mutex; // global
void increment_counter ()
{
counter_mutex.acquire();
++count;
counter_mutex.release();
}
The class Mutex would be a wrapper that contains a Windows handle to a
kernel-mode mutex. The constructor would call CreateMutex with no
name. acquire() and release() would be calls to WaitForSingleObject and
ReleaseMutex respectively.
The other method would be to use a critical section. It is
stochastically faster than a mutex because it uses a user-mode
spin-lock to make quick attempt to grab exclusivity before going into
kernel-mode, but then you must surrender strict portability of the
header file, which might have been possible with a mutex.
void increment_count()
{
Critical_Section cs; // constructor calls
InitializeCriticalSection();
cs.enter(); // EnterCriticalSection();
++count;
cs.leave(); // LeaveCriticalSection();
// ~cs calls DeleteCriticalSection();
}
would be the function set used.
The assumptions I would make about the operating system is that it:
1. Provides a kernel-mode mutex
2. Provides atomic test and set, swap, or other operation to implement
the user-mode spin-lock inside the critical section.
The most important statement I can make about this example is that I
would not regard the global variable counter as being "special" simply
because it is a scalar. If it is to be operated upon by multiple
threads simultaneously, it will require the same treatment as say, a
POD object that consumes 8192 bytes, and protect it with a critical
section or mutex.
-Le Chaud Lapin-
--
Le Chaud Lapin
> Le Chaud Lapin wrote:
> >
> > int thread1 ();
> > int thread2 ();
> It's subtler than that. If you let the two threads read x without
> changing it, do you expect problems?
If there is any potential for x to be written to in the program, yes,
otherwise, no.
> Consider the similar example:
>
> char x[] = "Test";
>
> void thread1()
> {
> char a = x[0];
> }
>
> void thread2()
> {
> char b = x[0];
> }
>
> Do you expect problems here?
No.
> Now replace the definition of x with:
>
> std::string x( "Test" );
> James Kanze argues that the code remains correct, and that g++ is in
> error to not work. Before jumping to conclusions about his
> understanding of the threading issues, you first need to understand
> what he's saying. (I happen to disagree with him that the code is
> correct. Either way, one of the goals of the future C++ standard is to
> resolve these issues by specifying the thread safety level of the
> standard library components.)
I see what you are saying here. And I know what James is saying. And
I think there is a disconnect in reasoning.
To take your example further, I could make a const global variable that
has a mutable member and still have the same problem:
struct Vending_Machine
{
mutable unsigned long int quaters_deposited;
///
} ;
const Vending_Machine out_of_order;
This example would not fool me. Anytime I see a global object, in a
multi-threading application, I know the implications of making
assumptions, and I do not mess around. I use a mutex.
It is my opinion that people who write multi-threaded applications on a
daily basis are in tune with the fact that global really does mean
global. This is why I was so puzzled before. It seems contradictory
(to me) that one could have so much experience with threading yet be
bother by these examples. In all fairness, another poster mentioned
CPU cache synchronization, which is valid, on some high-end systems,
but I did not broach that subject because I did not want this thread to
turn into an esoteric discussion on bus-locking, contention resolution,
etc. [There are some nice tricks that involve randomization that
helps, but are very boring to the programming community in general].
In any case, I certainly agree that
1. C++ programmers want to write multi-threading applications
2. Some _libraries_ are not thread-safe
3. I would be nice to have thread-safe libraries for C++
I made a distinction between the language proper and the libraries. I
was trying to emphasize that I see very little wrong with C++, the
language proper. I stated that, much of what the average programmer
wants by way of threading and synchronization can be implemented within
the context of the existing language, meaning, that part of the
language that is not the libraries. Obviously, I do not expect anyone
to use single-threaded libraries in a multi-threaded application and
have no problems.
-Le Chaud Lapin-
Le Chaud Lapin
> You mean, that the programmer is using a compiler, and doesn't
> have any real guarantees with regards to what it does.
Yes I do. The compiler manual says, "This library is for
single-threaded applications. That library is for multi-threaded
applications." I use the library for single-threaded applications in
single-threaded code. I use the library for multi-threaded
applications in multi-threaded code.
> Except if one of the writes migrates across a spin-lock.
> (Spin-locks are only guaranteed if special hardware instructions
> are used on a Sparc---or a PC. Hardware instructions that are
> never generated by Sun CC or by g++---or by the current version
> of VC++.)
Uh, yes they are. People who write device drivers using them all the
time. In fact, they are used so often, Microsoft make special library
functions just for spin-locks. Microsoft uses spin-locks in its own
implementation of what they call critical sections.
> First you have to define what that part is. Suppose that the
> library writer says that you need to manually acquire a lock
> before calling malloc (or operator new)?
I would ask the library writer why he did that when it does not make
sense. It is better to have a thread-safe new() which I use in all my
multi-threaded code.
> What does "meant to be used in a multi-threaded application"
> mean? For, say, tmpnam, or localtime? Or operator new, or
> std::allocator?
When a person sits down to write a library, and it is after the year,
say, 1985, he should be thinking about whether that library will
operate in a single-threaded environment, a multi-threaded environment,
or both. And especially someone who writes a function that read/writes
static global state. There is nothing inherently wrong with that, but
the library writer should not go around peddling it as being
thread-safe. Obviously it is not.
And since you mention new(), what do you think all of us Windows people
do when we need to call new() in a multi-threaded application? Invoke
and hope that race condition does not manifest? No, we go to the IDE
options and change the drop-down menu from "Single Threaded Library" to
"Multi-Threaded Library". Recompile. All are happy.
> If the library implementation doesn't fulfil the contract, then
> it is the library implementors fault. But for that to be the
> case, you first need the contract.
>
> Agreed. But the issues are a lot more complicated than you seem
> to think. I know, from experience.
The problems you put forth seem to indicate otherwise. No offense, but
the cache synchronization issue, which I was well-aware of and
purposely avoided broaching so as not to let this thread degenerate
into a discussion on computer hardware, is one of the few legitimate
realms of uncertainty.
Saying that a C++ class is not thread safe because objects of the class
all operate on a global variable...that's obvious.
Now if you are saying that the C++ committee needs to structure there
libraries so that that they can be single-threaded and multi-threaded,
I agree with that, but that is the library, not the language proper.
And I have always said that this is a library issue more than anything.
-Le Chaud Lapin-
--
Mirek Fidler
Edward Rosten wrote:
> Mirek Fidler wrote:
> > Shared y;
> > Mutex y_lock;
> >
> > void fn() {
> > y_lock.Lock();
> > y = 10;
> > y_lock.Unlock();
> > }
> >
> It looks like from this that y is global. If Lock() and Unlock() depend
> on y, then the compiler couldn't reorder the bits of Lock() an Unlock()
> depending on y. If the code for Lock() and Unlock() is not visible (eg
> in a different translational unit), then how can the compiler reorder
> the function calls?
I have not said a damn thing where and how Lock and Unlock are
defined;)
> You could probably construct it more carefully, eg by saying that y not
Well, in another reply I did.
--
Mirek Fidler
U++ team leader. http://www.ultimatepp.org
Chris Thomasson
has been removed from the article. Well, thanks! -mod/aps }
"Thant Tessman" <a...@standarddeviance.com> wrote in message
news:enuh9o$bda$1...@news.xmission.com...
[...]
>>> Le Chaud Lapin wrote:
>>>> Mirek Fidler wrote:
> [...]
>>>> Are you saying that the C++ standard does not prescribe sequential
>>>> execution of statements in a single-threaded program?
>>> It most certainly doesn't.
[...]
> No, the compiler would only reorder these things when it could prove to
> itself that there should be no dependency on the order of execution. T
That's a "fairly 'big' gamble/assumption for a compiler to make"...
IMHO of course!
:O
Man, the compiler can get very tricky, but it might be very hard for it to
understand that the code its currently "dissembling" and executing its
analytical algorithms against might be more finely tuned than the resulting
information that is analyses will eventually spit out...
> The problem is that the compiler makes assumptions that aren't necessarily
> true under multi-threaded conditions.
Well, yes your 100% correct... FWIW, you, or others, who frequent this
group
might want to go ahead and take some time to read through 'Section 2' of
the
following paper:
http://appcore.home.comcast.net/vzdoc/atomic/static-init/
Please, be on the lookout for those so-called "link-time" optimizations...
Also, this goes out to ALL of the compiler writers out there:
"Please, I completely beg of you... Please, if you are going to incorporate
'link-time" optimizations in your compilers, at least give the us users a
chance to turn it on of off with a #pragma, or something... Please, my
expertise in developing stable synchronization techniques and creating
portable C/C++ interfaces for them depends on it!"
Well, that request may sound a bit selfish; it should make it through the
mods though... Really, I mean the only types of programmers that link-time
optimizations are going to effect are those that are currently, and
'successfully', making use fairly heavy use of advanced multi-threading,
and
other technologies, that are in a category which simply demands
high-performance and scalability... So, IMO, they are in widespread
experimental use in many types of applications... Experimentally, though
these lock-free algorithms have been around for God knows how long... Very
early 80's is conservative thinking at the very least!
;^)
Well, I am not a compiler writer, so I may exist in my own work of personal
and, of course, blissful ignorance cloud but... Well, here is some of my
thoughts on this issue:
http://groups.google.com/group/comp.programming.threads/msg/0afc1109d18c2991
http://groups.google.com/group/comp.programming.threads/msg/fd3b4b5a5cd7841e
Any thoughts on this issue? Or, am I just living in my own personal pipe
dream here!
;^)
Thomas Richter
>>Shared y;
>>Mutex y_lock;
>>
>>void fn() {
>> y_lock.Lock();
>> y = 10;
>> y_lock.Unlock();
>>}
>>
>>nothing in C++ standard prevents C++ compiler to generate machine code
>>equivalent to
>
>
> [snip reordering]
>
> It looks like from this that y is global. If Lock() and Unlock() depend
> on y, then the compiler couldn't reorder the bits of Lock() an Unlock()
> depending on y. If the code for Lock() and Unlock() is not visible (eg
> in a different translational unit), then how can the compiler reorder
> the function calls?
Global optimizers are not so uncommon today. Just consider that
y_lock.Lock() is a short function in "lock.c" which is not visible in
the above code, it still might be visible to the global optimizer. It
could still inline the code, and still change the order.
The next question would be "what if y_lock is part of a binary library
that is linked to the code", but I don't think that C++ really defines
what this is and forbids "global optimization" in this area.
The problem is really what James already said above: There is not yet
a contract a C++ compiler has to fulfill you could depend on.
Still, in practical applications, you can write multithreaded code that
works on a set of "well-behaived" compilers, just that this type of
well-ness (uhm) is not covered by any standard. That is the problem, you
need to check yourself.
So long,
Thomas
peter koch larsen
Edward Rosten skrev:
> Mirek Fidler wrote:
>
> > Shared y;
> > Mutex y_lock;
> >
> > void fn() {
> > y_lock.Lock();
> > y = 10;
> > y_lock.Unlock();
> > }
> >
> > nothing in C++ standard prevents C++ compiler to generate machine code
> > equivalent to
>
> [snip reordering]
>
> It looks like from this that y is global. If Lock() and Unlock() depend
> on y, then the compiler couldn't reorder the bits of Lock() an Unlock()
> depending on y. If the code for Lock() and Unlock() is not visible (eg
> in a different translational unit), then how can the compiler reorder
> the function calls?
Whether it is in a different translation unit or not does not really
matter. Global optimisation is possible, so assume that the compiler
can see what happens inside Lock and Unlock.
If Lock and Unlock are "external" function (e.g. calls to the operating
system), the compiler has every right to assume the function knows
nothing about y - at least if the adress of y is never given to the OS.
>
> Note, I'm not claiming that threading is defined. I'm just disputing
> this one particular example.
>
> You could probably construct it more carefully, eg by saying that y not
> visible outside the translational unit, and &y is never assigned to a
> pointer of Shared* which is visible outside the translational unit.
I agree that there are lots of situations where the compiler could not
legally do the reordering.
/Peter
James Kanze
> Mirek Fidler wrote:
> > Shared y;
> > Mutex y_lock;
> > void fn() {
> > y_lock.Lock();
> > y = 10;
> > y_lock.Unlock();
> > }
> > nothing in C++ standard prevents C++ compiler to generate machine code
> > equivalent to
> [snip reordering]
> It looks like from this that y is global. If Lock() and Unlock() depend
> on y, then the compiler couldn't reorder the bits of Lock() an Unlock()
> depending on y.
But since they don't, the reordering is legal.
> If the code for Lock() and Unlock() is not visible (eg
> in a different translational unit), then how can the compiler reorder
> the function calls?
What do you mean by "not visible"? The compiler is allowed to
analyse code in any way it wants. There's no such thing as "not
visible" code.
In practice, of course, the compiler will eventually get down to
a system request, and it will NOT be able to analyse the object
code of the OS to determine what it does. But such functions
make up a closed, finite set, with "well known" semantics, and
all of the necessary knowledge can be built into the compiler.
(I once used a compiler where this was the case; it regularly
kept updated global data in registers accross calls to library
functions.)
> Note, I'm not claiming that threading is defined. I'm just disputing
> this one particular example.
It's rather stretched, in that any compiler intelligent enough
to be able to know that Mutex::Lock() (and ultimately,
pthread_mutex_lock or its equivalent) didn't depend on nor
modify y would also be intelligent enough to know that
pthread_mutex_lock is a special function, which ensures
synchronization. So it would either complain (if compiling
single threaded code) or do the right thing (if compiling
multi-threaded code). The point remains that you are counting
on specific guarantees from the compiler.
> You could probably construct it more carefully, eg by saying
> that y not visible outside the translational unit, and &y is
> never assigned to a pointer of Shared* which is visible
> outside the translational unit.
Of course, that does make the example more realistic:
int fn()
{
// The two initializations are static, so
// no synchronization problems can occur.
static pthread_mutex_t
m = PTHREAD_MUTEX_INIT ;
static int i = 0 ;
pthread_mutex_lock( &m ) ;
++ i ;
int result = i ;
pthread_mutex_unlock( &m ) ;
return result ;
}
It doesn't take much intelligence on the part of the compiler to
determine that neither pthread_mutex_lock nor
pthread_mutex_unlock can depend on nor modify i; a reasonable
compiler might easily recognize that if it moves the ++i into
the return statement (and thus after the call to
pthread_mutex_unlock), it can do away with the intermediate
variable result completely.
I think you've found a case that is not only theoretically
possible, but actually likely to occur in practice. (In fact,
the above is fully conformant Posix C, and the Posix standard
makes the necessary guarantees for it to work. In C, on a Posix
based machine.)
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
Gennaro Prota
>Peter Dimov wrote:
>> Thant Tessman wrote:
>
>> [...]
>
>> > Shoehorning threading into C++ just seems like a
>> > misallocation of talent and effort--counterproductive even.
>
>> Threading (concurrency + shared address space) is already in C++, and
>> has been for years.
>
>Yes and no. There has been ad hoc solutions which more or less
>worked, for a given architecture, OS and compiler, but nothing
>formal which the programmer could count on.
Exactly. I guess where the main misunderstanding lies: some people
just don't realize how many guarantees they are assuming which
actually are not. Francis Glassborow already summarized this nicely,
by saying that we need to redesign the C++ virtual machine. I haven't
seen any meaningful objection to his statement.
___
\|||/ Gennaro Prota - For hire
(o o) https://sourceforge.net/projects/breeze/
--ooO-(_)-Ooo----- (to mail: name _ surname / yaho ! com)
James Kanze
> >> DCL works perfectly fine:
> > (Given that your posting ended with colon, and not a period, I
> > suspect that there is something which got lost.
> Yup, it go lost. So, here it is:
> http://groups.google.com/group/comp.lang.c++.moderated/msg/e161a53de7c2290e
Yes. And given that, I think that your statement should be
modified to read "DCL can be made to work perfectly fine, at
least on most processors, provided you're willing to use
non-portable assembler code." A statement with which I have no
problems. (I've implemented it to work on a Sparc. Also using
inline assembler.)
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Pete Becker
> Pete Becker wrote:
>> Le Chaud Lapin wrote:
>>> I have been saying all along. We should stop doing X and hoping that
>>> things will work out magically. To do mutual exclusion, you need
>>> low-level support.
>> And nobody has disagreed with you. But let's get down to the nub of the
>> matter:
>>
>> static long counter;
>>
>> Please write a function that increments the value of this static
>> variable and can be called safely from multiple threads. Use whatever
>> low level support you need, but state explicitly what that support is.
>
> There are two ways to do this: one using a mutex, the other using a
> critical section. Assuming the underlying OS is Windows:
>
> The mutex is simpler but slower:
>
> Mutex counter_mutex; // global
>
> void increment_counter ()
> {
> counter_mutex.acquire();
> ++count;
> counter_mutex.release();
> }
>
The increment has no visible side effects, so the compiler is not
obliged to sandwich it between the acquire and the release. How do you
ensure that the compiler won't do either of those?
>
> The other method would be to use a critical section. It is
> stochastically faster than a mutex because it uses a user-mode
> spin-lock to make quick attempt to grab exclusivity before going into
> kernel-mode, but then you must surrender strict portability of the
> header file, which might have been possible with a mutex.
>
> void increment_count()
> {
> Critical_Section cs; // constructor calls
> InitializeCriticalSection();
>
> cs.enter(); // EnterCriticalSection();
> ++count;
> cs.leave(); // LeaveCriticalSection();
> // ~cs calls DeleteCriticalSection();
> }
>
> would be the function set used.
>
> The assumptions I would make about the operating system is that it:
>
> 1. Provides a kernel-mode mutex
> 2. Provides atomic test and set, swap, or other operation to implement
> the user-mode spin-lock inside the critical section.
>
And, again, how do you ensure that the compiler won't do the increment
before the call to enter or after the call to leave?
--
-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Peter Dimov
> In any case, I certainly agree that
>
> 1. C++ programmers want to write multi-threading applications
> 2. Some _libraries_ are not thread-safe
> 3. I would be nice to have thread-safe libraries for C++
You use "thread safe" without explaining it. There are various levels
of thread safety. One extreme is "no thread safety", when you
absolutely can't use the component from more than one thread at a time.
Some std::maps in the old days had that feature due to hidden shared
globals.
The next step is that separate instances are usable without
synchronization, but a single instance is not, even when not modified.
Your containers sit at this level because of their embedded iterators.
Next up, we have the modern STL, where it's possible to read the same
instance from multiple threads. This is also the thread safety level
for all basic types, both de facto and as specified by the POSIX
standard. ("Basic" thread safety, the most useful level in general;
should be the default for all sensible C++ code.)
Higher up the chain is the "strong" thread safety, where instances are
writable from multiple threads without external synchronization.
> I made a distinction between the language proper and the libraries. I
> was trying to emphasize that I see very little wrong with C++, the
> language proper.
There is nothing wrong with the language. The standard just doesn't
guarantee any specific behavior for multithreaded code. (Keep in mind
that some compiler optimizations are undetectable in single-threaded
code but not in MT.) The language itself will not change. The new
standard will simply specify its MT behavior.
Thomas Richter
> Yes I do. The compiler manual says, "This library is for
> single-threaded applications. That library is for multi-threaded
> applications." I use the library for single-threaded applications in
> single-threaded code. I use the library for multi-threaded
> applications in multi-threaded code.
All that's of course understood, but beside the point. I don't
think that anyone claims that it is impossible to write multithreaded
code in C++ (hey, I'm doing that as well), the problem is to
write "standard-conforming multithreaded code", for the very simple
reason that there is nothing in the C++ standard that says a word
about multithreading. It is an extension provided by your compiler
vendor, by several vendors indeed, that works to a certain degree
and has certain quirks in other degrees you may or may not know about,
and that are - given a good knowledge of your toolchain - easily
or hardly avoided.
I personally feel custom enough with my compiler to feel certain
enough that the code works well, but I'm also using a very restricted
subset of C++ to avoid a lot of "uncertain" areas. Exceptions are,
for example, a no-no, as some compilers simply break it for
multithreaded code.
>>Except if one of the writes migrates across a spin-lock.
>>(Spin-locks are only guaranteed if special hardware instructions
>>are used on a Sparc---or a PC. Hardware instructions that are
>>never generated by Sun CC or by g++---or by the current version
>>of VC++.)
>
>
> Uh, yes they are. People who write device drivers using them all the
> time. In fact, they are used so often, Microsoft make special library
> functions just for spin-locks. Microsoft uses spin-locks in its own
> implementation of what they call critical sections.
If they are generated by C++ compilers, they are generated by
extensions provided by your favorite compiler vendor. There's no
such thing in C++. And yes, synchronization primitives are required.
> Saying that a C++ class is not thread safe because objects of the class
> all operate on a global variable...that's obvious.
Well, in understanding what's wrong - yes. If throwing an exception
touches a global variable somewhere hidden in the runtime library, is
this a fault of the library? It *fails* to be multi-threading safe, but
it is *still* conforming to the C++ standard, and here we have trouble.
A compiler failing to provide thread-safe exceptions might be "broken"
by your understanding, at least hard to use in my understanding, but
still fine by C++ standards. What does this mean? Of course that the
standard is broken. (-: And hence, some work waits to be done.
> Now if you are saying that the C++ committee needs to structure there
> libraries so that that they can be single-threaded and multi-threaded,
> I agree with that, but that is the library, not the language proper.
> And I have always said that this is a library issue more than anything.
Unfortunately, it doesn't end in the library. See just the example
above: A compiler is allowed to re-order function calls provided it can
prove that the calling order is irrelevant for the virtual machine
defined by the C++ standard. And this is single-threaded.
Consider a plain-simple mutex lock around a variable as in the above
example. Would a compiler reorder calls to pthread_mutex_lock() and
pthread_mutex_unlock()? There's no today's compiler that could, at least
I'm not aware of one. Would that mean that this reordering is invalid by
today's standards? No, it wouldn't.
See, the problem is not that anyone claims that it is *impossible* to
write correct code (at least, I'm not) by making "reasonable"
assumptions of what my compilers do or don't do. The point is that
all these assumptions aren't covered by anything. Updating the C++
standard means finding a good common denominator of all those
implications you make while coding, and *require* them for compilers.
One of those assumptions might be that a compiler isn't allowed to
re-order certain function calls. One might think that it is reasonable
to disallow this for functions whose definitions aren't visible in
the translation unit where the call is made, but this might again
defeat certain global optimizer techniques. It's something that has
to be considered a bit more carefully than just handwaving around
techniques that "work now by pure chance".
So long,
Thomas
Sergey P. Derevyago
> The mutex is simpler but slower:
>
> Mutex counter_mutex; // global
>
> void increment_counter ()
> {
> counter_mutex.acquire();
> ++count;
> counter_mutex.release();
> }
>
increment_counter() get called.
> void increment_count()
> {
> Critical_Section cs; // constructor calls
> InitializeCriticalSection();
>
> cs.enter(); // EnterCriticalSection();
> ++count;
> cs.leave(); // LeaveCriticalSection();
> // ~cs calls DeleteCriticalSection();
> }
>
2. Local cs object won't help you to synchronize the access.
--
With all respect, Sergey. http://ders.stml.net/
mailto : ders at skeptik.net
Le Chaud Lapin
> Le Chaud Lapin wrote:
> > The mutex is simpler but slower:
> >
> > Mutex counter_mutex; // global
> >
> > void increment_counter ()
> > {
> > counter_mutex.acquire();
> > ++count;
> > counter_mutex.release();
> > }
> >
>
> The increment has no visible side effects, so the compiler is not
> obliged to sandwich it between the acquire and the release. How do you
> ensure that the compiler won't do either of those?
I would take whatever recourse is available in all situations like
these. If I may answer with an example...
Consider a single-threaded program that has a function that aims a
missile at an adjacent country and launches it. Aiming is achieved by
incrementing an memory-mapped register. Launching is achieved by
setting a different memory mapped register to "true":
static unsigned int ®ister_azimuth = *reinterpret_cast<unsigned int
*>(0x12345678);
static bool ®ister_launch = *reinterpret_cast<bool *>(0x12345680);
void aim_and_launch_missile ()
{
register_azimuth += 75; // degrees
register_launch = true;
}
Technically, IIUC, the compiler has the right to reorder these two
statements, since they are visibly independent, thus launching the
missile at a potentially friendly neighboring country and subsequently
pointing the launch pad at the enemy.
So even in a single-threaded program, the programmer would be faced
with a dilemma of what to do about the optimizer. Certainly, one could
argue from this example that, if preventing such transpositions is
desirable for threading, then it would be something desirable in
general.
Another example where a programmer has written a piece of code that he
thought was portable that gives a rough idea of how fast 1,000,000
global memory references can be performed by the CPU:
static int x;
int main ()
{
Instant before = now();
unsigned int count = 1000000;
while (count--)
x = 0;
Instant after = now();
cout << count << " memory references in " << (after-before) << "
seconds." << endl;
return 0;
}
On some compilers, he finds that the while loop is not performed until
just before the "return" 0. On other compilers, he finds that the
while loop has been completely omitted, as it is obviously superfluous,
resulting in that machine counting to a 1,000,000 is almost 0 seconds.
-Le Chaud Lapin-
--
Hans
Le Chaud Lapin wrote:
> In any case, I certainly agree that
>
> 1. C++ programmers want to write multi-threading applications
> 2. Some _libraries_ are not thread-safe
> 3. I would be nice to have thread-safe libraries for C++
>
> I made a distinction between the language proper and the libraries. I
> was trying to emphasize that I see very little wrong with C++, the
> language proper. I stated that, much of what the average programmer
> wants by way of threading and synchronization can be implemented within
> the context of the existing language, meaning, that part of the
> language that is not the libraries. Obviously, I do not expect anyone
> to use single-threaded libraries in a multi-threaded application and
> have no problems.
>
The reasons this cannot be handled just in the library are outlined in
my paper,
"Threads cannot be implemented in a library", PLDI 2005,
http://portal.acm.org/citation.cfm?doid=1065010.1065042 or (the TR
version) http://www.hpl.hp.com/techreports/2004/HPL-2004-209.html .
One short, and not very new, example that might clarify the issue is
the following:
Assume I have a struct s containing fields x and y, both of which are
initially zero. Assume I have two threads executing
Thread 1: s.x = 1;
Thread 2: s.y = 1;
After I wait for both threads to complete (using your favorite threads
API), can I conclude that both s.x and s.y are one?
In real life, this corresponds to the question of whether x and y can
be protected by separate locks, which is important.
The empirical answer currently is something like:
Yes, unless either
- x or y is a bit-field (in which case things get complicated)
- you are using default options to compile for an architecture like
Alpha which in prehistory did not have byte store instructions, and
either x or y is a byte in size, and they are "too close together"
- this is embedded in more complicated code, and your compiler decided
to combine multiple field updates in order to generate faster code
- your compiler was just being perverse, because the combined C, C++
and pthreads specs clearly don't require both fields to be one at the
end of this, even if they are both long integers.
I claim this is the wrong answer if you are trying to teach someone how
to write multithreaded code. This is the sort of problem we're trying
to fix.
Note that this is purely a compiler issue and language specification
issue: This goes "wrong" because the compiler generates code to update
one field that also reads and rewrites the other one. I haven't even
mentioned a thread library routine. The issue arises even if you are
trying to lock protect all shared accesses; the question is whether
there are any shared accesses.
Trying to resolve this sort of issue in a library specification seems
contrived to me. This has to do with semantics of the base language in
the presence of concurrency.
The paper contains more interesting and obscure examples; this isn't
the only way in which compilers are allowed to "break" perfectly
synchronized code. That's really what I want to fix.
This probably accounts for a smallish fraction of real bugs in
multithreaded code. But it does account for a number of them. And to
me they're the most dangerous ones, since they're not really visible in
the source code. And for some variants it is really hard to give rules
for avoiding the problems.
Hans
Greg Herlihy
Pete Becker wrote:
> Le Chaud Lapin wrote:
> > The mutex is simpler but slower:
> >
> > Mutex counter_mutex; // global
> >
> > void increment_counter ()
> > {
> > counter_mutex.acquire();
> > ++count;
> > counter_mutex.release();
> > }
> >
>
> The increment has no visible side effects, so the compiler is not
> obliged to sandwich it between the acquire and the release. How do you
> ensure that the compiler won't do either of those?
By having a stack-based object release and acquire the lock:
#include <pthread.h>
typedef pthread_mutex_t mutex;
struct StMutex
{
StMutex( mutex * m )
: mMutex( m )
{
pthread_mutex_lock( mMutex);
}
~StMutex()
{
pthread_mutex_unlock( mMutex);
}
private:
mutex * mMutex;
};
int main()
{
StMutex lockMe( &gMutex);
count++;
}
Although, any solution that uses a lock, critical section or other form
of blocking synchonization is inferior to one that does not. So,
assuming that an atomic compare-and-swap routine is available, the
lock-free solution beats the others, hands-down:
static int count;
// returns true if value was updated
bool CompareAndSwap( long oldValue, long newValue, long *address);
int main()
{
while (true)
{
long n = count;
if ( CompareAndSwap( n, n+1, &count))
break;
}
...
}
Greg
--
Mirek Fidler
Peter Dimov wrote:
> Next up, we have the modern STL, where it's possible to read the same
> instance from multiple threads. This is also the thread safety level
> for all basic types, both de facto and as specified by the POSIX
> standard. ("Basic" thread safety, the most useful level in general;
> should be the default for all sensible C++ code.)
Well, I am not sure. Consider internal caches implemented using mutable
members (or, heavens forbid, const_cast ;). In that case, your "basic"
requirement would mean that ALL mutable members must have serialization
(locking) around them. That is IMO not a very good idea.
Also, in practice, I believe that in most situations you will have at
least one writer thread, therefore you will have to lock reads access
anyway, so by this "basic" requirement you are pessimising quite useful
case for no gain.
Maybe "basic" thread safety should rather mean that you can use
instance from multiple threads if you serialize *ALL* access to it.
"Unlocked concurrent reads" is higher level.
--
Mirek Fidler
U++ team leader. http://www.ultimatepp.org
peter koch larsen
Le Chaud Lapin skrev:
> James Kanze wrote:
> > Except if one of the writes migrates across a spin-lock.
> > (Spin-locks are only guaranteed if special hardware instructions
> > are used on a Sparc---or a PC. Hardware instructions that are
> > never generated by Sun CC or by g++---or by the current version
> > of VC++.)
>
> Uh, yes they are. People who write device drivers using them all the
> time. In fact, they are used so often, Microsoft make special library
> functions just for spin-locks. Microsoft uses spin-locks in its own
> implementation of what they call critical sections.
Right. But this is not code generated by the compiler but rather
(assembly) code used by the compićer-
>
> > First you have to define what that part is. Suppose that the
> > library writer says that you need to manually acquire a lock
> > before calling malloc (or operator new)?
>
> I would ask the library writer why he did that when it does not make
> sense. It is better to have a thread-safe new() which I use in all my
> multi-threaded code.
Okay! But this is one of the areas where the C++ standard is going to
change. It will say something in the direction of that new must be
reentrant. Another thing it will say is that the compiler is not
allowed to reorder code across certain function calls (e.g. calls to
mutexes), and that it must allow two threads to simultaneously throw an
exception.
I believe that most of the work on the standard will use their effort
on this subject and the C++ memory model in order to assure that
"newer" lock-free techniques can be used from C++.
This is not obvious at all. On the contrary, many would expect that two
threads would be able to simultaneously read data and also call some
constant functions such as e.g. std::vector<>.begin(),
std::vector<>.end() and std::vector<>operator[]. The standard does not
give us such promises yet, and we will have to revert to the compiler
documentation in order to verify the behavior of our program.
>
> Now if you are saying that the C++ committee needs to structure there
> libraries so that that they can be single-threaded and multi-threaded,
> I agree with that, but that is the library, not the language proper.
> And I have always said that this is a library issue more than anything.
>
Those libraries are part of the standard, and it is not just a library
issue. The "difficult" part is IMHO the memory model and the new
thread-related libraries (if they are to appear).
/Peter
James Kanze
> Pete Becker wrote:
> > Le Chaud Lapin wrote:
> > > I have been saying all along. We should stop doing X and
> > > hoping that things will work out magically. To do mutual
> > > exclusion, you need low-level support.
> > And nobody has disagreed with you. But let's get down to the
> > nub of the matter:
> > static long counter;
> > Please write a function that increments the value of this
> > static variable and can be called safely from multiple
> > threads. Use whatever low level support you need, but state
> > explicitly what that support is.
> There are two ways to do this: one using a mutex, the other
> using a critical section.
Both come down to the same thing here, since Pete has only asked
for a single function. But I don't think that that was all of
Pete's question. You haven't defined "mutex", for example, so I
will suppose that you are referring to an abstract mutex: a
semaphore with a count of 1.
> Assuming the underlying OS is Windows:
> The mutex is simpler but slower:
And Windows doesn't have critical sections, you don't have an
alterative. (On the other hand, Windows has two different mutex
types, one for very simple use, and one for more general use,
and the simple one can be quite fast. In fact, I've never found
any performance problems with uncontended mutex locking.)
> Mutex counter_mutex; // global
> void increment_counter ()
> {
> counter_mutex.acquire();
> ++count;
> counter_mutex.release();
> }
> The class Mutex would be a wrapper that contains a Windows handle to a
> kernel-mode mutex.
But what is guaranteed by the Windows kernel-mode mutex lock? I
know what Posix guarantees here for C programs, and the
equivalent code, written in C, is guaranteed to work on a Posix
compliant C compiler. But of course, that is because the Posix
specification goes well beyond just specifying primitives; Posix
also places significant restrictions on the compiler, and just
linking in the "library" doesn't make a C compiler Posix
compliant.
As far as the C and the C++ standards are concerned, there's
nothing to prevent the compiler from moving the incrementation
in front of the acquire, or behind the release. All the
compiler has to do is prove that e.g. acquire does not access
counter for it to move the increment before the call to acquire.
Realistically, if their is no code which takes the address of
(or creates a reference to) counter, then the compiler
automatically knows that no function not defined in the current
translation unit can possibly access them; since your acquire
and release functions are not defined in the current translation
unit, the compiler knows that where count is modified, relative
to them, is irrelevant.
If we replace the code with its C equivalent, and use Posix (and
Posix guarantees), it is guaranteed to work. The low level
hardware support Pete asked about is:
-- At most one thread can acquire the mutex at a time; any
other thread attempting to acquire it will block. (That's
really the definition of a mutex.)
-- Acquiring or releasing the mutex assures full hardware
synchronization: all previous writes are fully completed to
main memory before leaving the function, and no following
read has been started.
-- The compiler does not move writes and reads across calls to
acquire and release.
-- Accesses to a single long do not touch any other object.
(This is almost always the case for a long, but could easily
be a problem with char: some architectures write a char by
reading a word, replacing the char in it, then writing the
word back. In such cases, the compiler must ensure that
individual char's are in different words, or you there's no
way to implement anything that is thread safe.)
All of these are necessary requirements. (I can't find anything
but the first in the Windows documentation, but it's quite
possible that I don't know where to look. It's not in any
obvious place in the Posix specification either. It's also
probably safe to assem that the second condition above is met,
for the simple reason that it's probably impossible to implement
a mutex at the system level without meeting it.)
A Posix version would be simply:
void
increment_counter()
{
static pthread_mutex_t
m = PTHREAD_MUTEX_INITIALIZER ;
pthread_mutex_lock( &m ) ;
++ cout ;
pthread_mutex_unlock( &m ) ;
}
The low-level guarantees required are that the OS be Posix
compliant, and that the C++ compiler behave like a Posix
compliant C compiler for the parts of the language which are
compatible with C.
Note that in all cases, I need some guarantees (beyond those
given in the C++ standard) from the compiler. It's not just a
case of linking in a library with the right primitives.
> The constructor would call CreateMutex with no
> name. acquire() and release() would be calls to WaitForSingleObject and
> ReleaseMutex respectively.
Fine. And what do these functions do? In particular, do they
guarantee any necessary memory synchronization.
> The other method would be to use a critical section.
Not under Windows. Windows doesn't have critical sections.
(What Windows calls a CRITICAL_SECTION is simply an alternative
implementation of a mutex.)
> It is
> stochastically faster than a mutex because it uses a user-mode
> spin-lock to make quick attempt to grab exclusivity before going into
> kernel-mode,
If it really uses a spin-lock, it is almost certainly slower.
The usual implementation of a Mutex (under Posix) is to grab
exclusivity in user-mode code IF possible, and go immediately to
kernel code otherwise. (This is, at least, what Solaris does.)
You don't spin.
> but then you must surrender strict portability of the
> header file, which might have been possible with a mutex.
Have you looked at boost threads? They work with both Posix and
Windows, using CriticalSection under Windows when appropriate.
> void increment_count()
> {
> Critical_Section cs; // constructor calls
> InitializeCriticalSection();
Presumably, you meant for this variable to be static.
Otherwise, it doesn't protect anything. (Of course, that's
because it's really a mutex, and not a critical section.) Even
then, you need a guarantee (from the compiler) that you can make
unsynchronized calls to a function which contains a static local
variable---to the best of my knowledge, g++ is the only compiler
which gives this.
> cs.enter(); // EnterCriticalSection();
> ++count;
> cs.leave(); // LeaveCriticalSection();
> // ~cs calls DeleteCriticalSection();
> }
> would be the function set used.
> The assumptions I would make about the operating system is that it:
> 1. Provides a kernel-mode mutex
With necessary memory synchronization, etc.
> 2. Provides atomic test and set, swap, or other operation to implement
> the user-mode spin-lock inside the critical section.
I don't understand this: I though you were using the Windows
type CRITICAL_SECTION. If so, it's a Windows primitive. It
provides a certain set of guarantees. How it achieves them
really isn't your problem, and what it needs to achieve them in
a particular implementation isn't part of the guarantees you
nee.
> The most important statement I can make about this example is that I
> would not regard the global variable counter as being "special" simply
> because it is a scalar.
Nobody said you have to. (With long, it can be tricky anyway,
since reads and writes to long aren't always atomic.) I could
write a function which didn't use any system synchronizations
primitives for a Sparc, but I doubt that it would really be
significantly faster than the Posix portable version I wrote
above---it would definitly be faster in the case of contention,
but not necessarily in the uncontended case (which is,
hopefully, by far the most frequent).
> If it is to be operated upon by multiple threads
> simultaneously, it will require the same treatment as say, a
> POD object that consumes 8192 bytes, and protect it with a
> critical section or mutex.
Once you start dealing with agglomerates, you need extra
guarantees, e.g. concerning layout, etc.
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
James Kanze
> On 8 Jan 2007 12:43:24 -0500, James Kanze wrote:
> >Peter Dimov wrote:
> >> Thant Tessman wrote:
> >> [...]
> >> > Shoehorning threading into C++ just seems like a
> >> > misallocation of talent and effort--counterproductive even.
> >> Threading (concurrency + shared address space) is already in C++, and
> >> has been for years.
> >Yes and no. There has been ad hoc solutions which more or less
> >worked, for a given architecture, OS and compiler, but nothing
> >formal which the programmer could count on.
> Exactly. I guess where the main misunderstanding lies: some people
> just don't realize how many guarantees they are assuming which
> actually are not. Francis Glassborow already summarized this nicely,
> by saying that we need to redesign the C++ virtual machine. I haven't
> seen any meaningful objection to his statement.
Yes. I especially liked Thomas Richter's characterization of
the current situation: "[Multithreading] is an extension
provided by your compiler vendor, by several vendors indeed,
that works to a certain degree and has certain quirks in other
degrees you may or may not know about, and that are - given a
good knowledge of your toolchain - easily or hardly avoided."
(By "hardly", I think he means "with difficultly", although the
usual meaning would also fit. But the contrast in "einfach oder
schwierig zu vermeiden" seems more natural.)
Perhaps I'm more sensibilized than most to this problem, since
I've actually had to deal with thread safe code which stopped
being thread safe when we changed compilers.
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
Jeff Koftinoff
Greg Herlihy wrote:
> Pete Becker wrote:
> > The increment has no visible side effects, so the compiler is not
> > obliged to sandwich it between the acquire and the release. How do you
> > ensure that the compiler won't do either of those?
>
> By having a stack-based object release and acquire the lock:
>
> #include <pthread.h>
>
> typedef pthread_mutex_t mutex;
>
> struct StMutex
> {
> StMutex( mutex * m )
> : mMutex( m )
> {
> pthread_mutex_lock( mMutex);
> }
>
> ~StMutex()
> {
> pthread_mutex_unlock( mMutex);
> }
>
> private:
> mutex * mMutex;
> };
>
> int main()
> {
> StMutex lockMe( &gMutex);
>
> count++;
> }
With that code, the compiler is STILL permitted to re-order main() to
be:
int main()
{
count++;
StMutex lockMe( &gMutex );
}
There are no guarantees, since the compiler knows that StMutex does not
modify count. Even if you try to 'hide' the definition of StMutex, even
if it involves a kernel trap/syscall/etc - there is nothing in the c++
standard that forbids this optimization - and yes, this kind of
optimization is important to be able to have for non-mutex classes. So
how does the compiler know that this class is very special and is a
'multi-threaded sequence point'?
Any solutions require compiler language extensions to force the
optimizer to not be so tricky. These compiler language extensions are
not portable. To properly support threads in C++, the C++ language
definition must standardize these kinds of things. It is not trivial,
and it is discouraging to see how much code is multi-threaded 'hanging
by a thread, working by accident' because the compiler did not do a
specific optimization - yet...
--jeffk++
www.jdkoftinoff.com
Pete Becker
This doesn't meet the requirement, which you snipped. The requirement
was was to write a function that increments the value of the static
variable and can be called safely from multiple threads. main can't be
called from multiple threads.
Assuming that this was written as a callable function, how does this
force the compiler to sandwich the increment between the lock and the
unlock? To the compiler this looks just like the earlier version: a
function call, an unrelated increment, and another function call. The
unrelated increment can be moved without affecting the meaning of a
conforming C++ program.
> Although, any solution that uses a lock, critical section or other form
> of blocking synchonization is inferior to one that does not. So,
> assuming that an atomic compare-and-swap routine is available, the
> lock-free solution beats the others, hands-down:
>
> static int count;
>
> // returns true if value was updated
>
> bool CompareAndSwap( long oldValue, long newValue, long *address);
>
> int main()
> {
> while (true)
> {
> long n = count;
>
> if ( CompareAndSwap( n, n+1, &count))
> break;
> }
> ...
> }
>
There is no guarantee that the compiler won't optimize away 'n' and
simply pick up count's value twice to compute the arguments to
CompareAndSwap, leaving open the possibility that another thread will
modify count between the two accesses.
--
-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Pete Becker
> Pete Becker wrote:
>> Le Chaud Lapin wrote:
>>> The mutex is simpler but slower:
>>>
>>> Mutex counter_mutex; // global
>>>
>>> void increment_counter ()
>>> {
>>> counter_mutex.acquire();
>>> ++count;
>>> counter_mutex.release();
>>> }
>>>
>> The increment has no visible side effects, so the compiler is not
>> obliged to sandwich it between the acquire and the release. How do you
>> ensure that the compiler won't do either of those?
>
> I would take whatever recourse is available in all situations like
> these. If I may answer with an example...
>
No, you may not answer with an example. Answer with code whose meaning
is well-defined under the C++ standard as it exists today. Otherwise
you're just engaging in meaningless handwaving.
[sample code illustrating similar problem omitted]
> Technically, IIUC, the compiler has the right to reorder these two
> statements, since they are visibly independent, thus launching the
> missile at a potentially friendly neighboring country and subsequently
> pointing the launch pad at the enemy.
Yup. And embedded programmers have to be very careful about what the
compiler does in order to make that sort of code work right. In
particular, you'd test that the code actually executed in the required
order. Do you propose doing that for every lock and unlock in a
multi-threaded program?
--
-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Pete Becker
>
> All that's of course understood, but beside the point. I don't
> think that anyone claims that it is impossible to write multithreaded
> code in C++ (hey, I'm doing that as well), the problem is to
> write "standard-conforming multithreaded code", for the very simple
> reason that there is nothing in the C++ standard that says a word
> about multithreading.
I generally put this more strongly. The goal is to be able to write
fast, robust multi-threaded programs. Library-only solutions can,
perhaps, be robust, but you have to lock everything in sight, and that
kills performance. So you need more guarantees, so that you know when
you can leave locks out.
--
-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
James Kanze
> Le Chaud Lapin wrote:
> > In any case, I certainly agree that
> > 1. C++ programmers want to write multi-threading applications
> > 2. Some _libraries_ are not thread-safe
> > 3. I would be nice to have thread-safe libraries for C++
> You use "thread safe" without explaining it. There are various levels
> of thread safety.
I agree with the point you are making, but I disagree with the
idea of "levels of thread safety". In the end, there are only
two: a component specifies its contracts with regards to
threads, or it doesn't. If it doesn't, a program which uses
that component is not thread safe. Period. If it does, a
program which uses the component is thread safe if and only if
it fulfills its end of the contract.
Obviously, of course, the contract can shift more or less of the
work off to the client code. But a compiler which requires
external synchronization for adding two int's is thread safe, if
that is the documented contract. (It's not very usable, of of
course, but that's a different issue.)
> One extreme is "no thread safety", when you absolutely can't
> use the component from more than one thread at a time. Some
> std::maps in the old days had that feature due to hidden
> shared globals.
Typical implementations, at least on Unix platforms, of
functions like localtime and strtok still have this
characteristic.
> The next step is that separate instances are usable without
> synchronization, but a single instance is not, even when not modified.
> Your containers sit at this level because of their embedded iterators.
This is also the official guarantee of components in libstdc++,
used with g++. (In practice, most components give the SGI
guarantee.)
> Next up, we have the modern STL, where it's possible to read the same
> instance from multiple threads. This is also the thread safety level
> for all basic types, both de facto and as specified by the POSIX
> standard.
De facto is very uncertain. I can think of a few cases where it
might not be automatic (e.g.: objects in a shared object, when
accessed from a thread other than the one that loaded it). De
facto isn't a contract, and you don't know when it applies, and
when not.
And the Posix guarantee isn't limited to basic types; it applies
to any time that is accessed in a single operation. (Formally,
Posix speaks of "a memory location", without defining what is
meant by "memory location". Intuitively, given:
struct S1
{
int b1 : 1 ;
int b2 : 1 ;
} ;
struct S2 { S1 x; S1 y ; } s ;
I would expect that s.x and s.y correspond to different memory
locations, but x.b1 and x.b2 don't. The last time I talked with
anyone on the committee, too, it seemed that this was the
direction C++ was going. But it does introduce added
constraints on the compiler, at least on some hardware.
> ("Basic" thread safety, the most useful level in general;
> should be the default for all sensible C++ code.)
That is, of course, a personal opinion (which I happen to
share). At least at one time, the authors of the g++ library
felt differently, and made a weaker guarantee.
> Higher up the chain is the "strong" thread safety, where instances are
> writable from multiple threads without external synchronization.
Which is rarely useful. And not always even possible. How
could you provide this guarantee with std::vector, for example,
so that I wouldn't need a lock for:
std::vector< int > v ; // Shared instance....
v[ 0 ] = 42 ;
> > I made a distinction between the language proper and the libraries. I
> > was trying to emphasize that I see very little wrong with C++, the
> > language proper.
> There is nothing wrong with the language. The standard just doesn't
> guarantee any specific behavior for multithreaded code. (Keep in mind
> that some compiler optimizations are undetectable in single-threaded
> code but not in MT.) The language itself will not change. The new
> standard will simply specify its MT behavior.
The language probably will have a few minor extensions as well.
I wouldn't be surprised if there were support for thread local
variables, for example, and the obvious way to implement that is
a new storage class. But by far the greatest impact will be
things like replacing sequence points with a concept which works
for multiple threads, and defining when you need
synchronization, and when you don't (things like modifying two
different bit fields, or two different char's from the same
array or struct, from different threads).
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
James Kanze
> James Kanze wrote:
> > You mean, that the programmer is using a compiler, and doesn't
> > have any real guarantees with regards to what it does.
> Yes I do. The compiler manual says, "This library is for
> single-threaded applications. That library is for multi-threaded
> applications." I use the library for single-threaded applications in
> single-threaded code. I use the library for multi-threaded
> applications in multi-threaded code.
And what about the compiler, and the code it generates? (And of
course, just saying that the library is for multi-threaded
applications doesn't say anything. But I assume you are using
this as a shorthand way of saying that the library defines a
contract for a multithreaded environment.)
But that's just my point: you need these guarantees: from the
hardware, from the OS, from the compiler, and from all of the
libraries you use. If any one is missing, you can't write
multithreaded code and be sure that it is correct.
The current situation, of course, is that you often do have a
set of guarantees. But the exact guarantees differ from one
combination of hardware, OS, compiler and libraries to the next,
so any multithreaded code is unportable. And it's often
difficult to find what exactly is guaranteed anyway: in the
Posix standard, the guarantees concerning memory synchronization
are buried away in some secondary text, and I've yet to find
them at all for Windows (but I haven't looked that hard, since
it's not a relevant platform for the type of things I develop).
> > Except if one of the writes migrates across a spin-lock.
> > (Spin-locks are only guaranteed if special hardware instructions
> > are used on a Sparc---or a PC. Hardware instructions that are
> > never generated by Sun CC or by g++---or by the current version
> > of VC++.)
> Uh, yes they are.
Only using __asm__ under g++, or something similar with VC++.
> People who write device drivers using them all the
> time.
People who write device drivers use assembler or very special
compiler extensions, at least for parts of their code.
(Also, I would hope that very few, if any, device drivers today
use spin-locks. Blocking the entire system until your IO
finished may have been acceptable under CP/M, but it certainly
isn't under Windows or Unix.)
> In fact, they are used so often, Microsoft make special library
> functions just for spin-locks. Microsoft uses spin-locks in its own
> implementation of what they call critical sections.
So that a critical section will be slower than a mutex?
I just looked at the documentation. It spins (which isn't quite
the same thing as using a spin lock), and then, only in very
special cases. The documentation explicitly says that it will
NOT spin on a single processor machine, ever.
And of course, this sort of code is written (at least partially)
in assembler, so the fact that the compiler cannot generate the
necessary instructions is irrelevant.
> > First you have to define what that part is. Suppose that the
> > library writer says that you need to manually acquire a lock
> > before calling malloc (or operator new)?
> I would ask the library writer why he did that when it does not make
> sense. It is better to have a thread-safe new() which I use in all my
> multi-threaded code.
Certainly. So in fact, you just "assume" that the library (and
the compiler) gives you the guarantees you want. Whereas I've
actual experienced the fact that different compilers and
libraries give different guarantees, and that there have been
compilers (not so long ago) with which you really couldn't use
for multithreaded applications.
Don't forget that multithreading on mainstream machines is very
recent. (Of course, in many ways, it resembles what
multiprocessing was back when I started programming, when we
didn't have MMU's, virtual memory or even protection.)
> > What does "meant to be used in a multi-threaded application"
> > mean? For, say, tmpnam, or localtime? Or operator new, or
> > std::allocator?
> When a person sits down to write a library, and it is after the year,
> say, 1985, he should be thinking about whether that library will
> operate in a single-threaded environment, a multi-threaded environment,
> or both.
[Just a nit, but I'd disagree about the year. In 1985, the
Microsoft OS was MS-DOS, and you certainly didn't have to
worry about multithreading there. G++ didn't support
threading in its generated code until at least 3.0, which
only appeared in mid-2001, and there's no point---nor any
way---to make a library thread safe if the code the compiler
generates isn't thread safe.]
> And especially someone who writes a function that read/writes
> static global state. There is nothing inherently wrong with that, but
> the library writer should not go around peddling it as being
> thread-safe. Obviously it is not.
You're missing the point again. You need guarantees, from the
library and from the compiler. Obviously, most compilers today,
at least for mainstream Unix and Windows, do support
multithreading, and their libraries do as well. That is to say,
they define a contract with you with regards to multithreading:
you meet your end of the contract, and they will ensure that
your code will work.
The problem is that the exact terms of the contract vary from
one compiler to the next, even when the set of supported
system-level primitives is identical. I've had to fix programs
that worked with Sun CC, and failed with g++; had the original
programmer used g++, and its set of guarantees, the situation
would be the reverse.
The point of standardization is to give a common set of
guarantees, that you know to be available everywhere.
Individual compilers will probably still give additional
guarantees. If you're developping for a single
platform/compiler, you can take advantage of these guarantees
(in the same way a lot of programmers write code that assumes
that an int is 32 bits). If you want portable code, however,
you have a predefined set of guarantees that you know will work
everywhere.
The functions I cited weren't chosen at random. In the case of
the first two (tmpnam, localtime), Posix (and Sun CC and
g++---and, I'm almost sure, VC++ under Windows) says that you
cannot use them in a multithreaded program. They may be
standard C/C++, but the Posix contract doesn't extend to them.
And while the C++ standards committee hasn't gotten that far
yet, I rather suspect that it will follow existing practice, and
ban them as well. The functions may be part of the standard
library, but the usual guarantees for multithreading don't
extend to them.
The other two were chosen because the standard I normally use
for multithreading guarantees (Posix) doesn't mention them. At
present, I need a guarantee from the library, and in the case of
operator new, from the language as well. Guarantees I'd like to
see in the standard.
> And since you mention new(), what do you think all of us Windows people
> do when we need to call new() in a multi-threaded application?
You probably count on guarantees given by the compiler. Just
like us Unix people do.
That's my whole point. Just having a set of OS level primitives
is not sufficient. You need guarantees from the compiler (and
from all of the libraries you use).
> Invoke
> and hope that race condition does not manifest? No, we go to the IDE
> options and change the drop-down menu from "Single Threaded Library" to
> "Multi-Threaded Library". Recompile. All are happy.
[Just another nit, but normally, the individual programmer
doesn't make the decision as to how his programs are
compiled. For better or worse, changing compiler options
can result in incompatible binaries, so all of the compiler
options are normally fixed once and for all by the
integration team. I don't know the exact mechanisms for
doing this under Windows (other than by making everyone use
a Unix like environment like UWin or MSys), but it certainly
doesn't involve individual programmers choosing in a menu.]
> > If the library implementation doesn't fulfil the contract, then
> > it is the library implementors fault. But for that to be the
> > case, you first need the contract.
> > Agreed. But the issues are a lot more complicated than you seem
> > to think. I know, from experience.
> The problems you put forth seem to indicate otherwise. No offense, but
> the cache synchronization issue, which I was well-aware of and
> purposely avoided broaching so as not to let this thread degenerate
> into a discussion on computer hardware, is one of the few legitimate
> realms of uncertainty.
> Saying that a C++ class is not thread safe because objects of the class
> all operate on a global variable...that's obvious.
> Now if you are saying that the C++ committee needs to structure there
> libraries so that that they can be single-threaded and multi-threaded,
> I agree with that, but that is the library, not the language proper.
> And I have always said that this is a library issue more than anything.
What you started by saying is that all you need is a good set of
OS primitives. Which is just false. Both the language proper
and all of the libraries use must offer a full set of
guarantees, and you must write your code to conform to your end
of the contract they define. Today, you simply cannot write
portable multi-threaded code, and the problem goes far beyond
wrapping the OS primitives in a portability layer. The set of
guarantees offered by the compiler differs from one compiler to
the next. Currently, most compilers (associated with their
standard libraries) do not allow the use of localtime in
multithreaded code, for example, even though it is a very widely
used function. Posix based compilers say to replace it with
localtime_r; Windows based with localtime_s (and doesn't
explicitly say that localtime is forbidden, so maybe it does
work). Currently, many compilers (but not all) require external
synchronization when first encountering a static local variable.
Currently, almost every compiler I know handles thread
cancellation differently. (OK, that's an easy one: everyone
does it differently, so don't use it.)
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Peter Dimov
> Peter Dimov wrote:
> > Next up, we have the modern STL, where it's possible to read the same
> > instance from multiple threads. This is also the thread safety level
> > for all basic types, both de facto and as specified by the POSIX
> > standard. ("Basic" thread safety, the most useful level in general;
> > should be the default for all sensible C++ code.)
>
> Well, I am not sure. Consider internal caches implemented using mutable
> members (or, heavens forbid, const_cast ;). In that case, your "basic"
> requirement would mean that ALL mutable members must have serialization
> (locking) around them. That is IMO not a very good idea.
You get to choose the thread safety level for your component. If you
want concurrent reads to not be allowed, then you document them to not
be. "Default is basic" only says what happens when you don't explicitly
state otherwise. Since most components provide "basic" without any
extra effort, it makes sense to have that as default.
> Also, in practice, I believe that in most situations you will have at
> least one writer thread, therefore you will have to lock reads access
> anyway,
Depending on the reader/writer ratio and frequency, you could be able
to use a non-broken reader-writer lock and increase the performance
tenfold or so on a sixteen core machine. :-)
> so by this "basic" requirement you are pessimising quite useful
> case for no gain.
Nope. It is you who decides to provide or not provide "basic", not me.
:-) To turn your example around, if another implementation of your
component interface has no internal cache, the user could be required
to lock around the read accesses for no reason.
Thomas Richter
>>The increment has no visible side effects, so the compiler is not
>>obliged to sandwich it between the acquire and the release. How do you
>>ensure that the compiler won't do either of those?
>
>
> I would take whatever recourse is available in all situations like
> these. If I may answer with an example...
>
> Consider a single-threaded program that has a function that aims a
> missile at an adjacent country and launches it. Aiming is achieved by
> incrementing an memory-mapped register. Launching is achieved by
> setting a different memory mapped register to "true":
>
> static unsigned int ®ister_azimuth = *reinterpret_cast<unsigned int
> *>(0x12345678);
> static bool ®ister_launch = *reinterpret_cast<bool *>(0x12345680);
>
> void aim_and_launch_missile ()
> {
> register_azimuth += 75; // degrees
> register_launch = true;
> }
>
> Technically, IIUC, the compiler has the right to reorder these two
> statements, since they are visibly independent, thus launching the
> missile at a potentially friendly neighboring country and subsequently
> pointing the launch pad at the enemy.
>
> So even in a single-threaded program, the programmer would be faced
> with a dilemma of what to do about the optimizer.
Yes, indeed. You are asking for a specific write-order and thus need a
memory barrier, or a vendor specific extension that guarantees this
write order. Some compilers will provide this with "volatile", though
this is again an extension. If the above is mission critical, you
better check with your compiler manual. And if the compiler manual
doesn't say, you better pick another vendor. And if that doesn't say,
you isolate the method in a tiny piece of assembly code.
The reason for the problem you face here is (again?) that you try to
solve a problem by C/C++ means in an area that is left open by the
specs, and remain undefined by the VM spec. A write to a variable that
is nowhere referenced is by that "invisible", and might be optimized out
completely. (-:
I might seem to remember that the Linux kernel folks have had trouble
with exactly this type of problem in the past. IIRC, GNU g++/gcc
provides a suitable extension to address this issue, though.
> Certainly, one could
> argue from this example that, if preventing such transpositions is
> desirable for threading, then it would be something desirable in
> general.
>
> Another example where a programmer has written a piece of code that he
> thought was portable that gives a rough idea of how fast 1,000,000
> global memory references can be performed by the CPU:
>
> static int x;
> int main ()
> {
> Instant before = now();
> unsigned int count = 1000000;
> while (count--)
> x = 0;
> Instant after = now();
> cout << count << " memory references in " << (after-before) << "
> seconds." << endl;
> return 0;
> }
>
> On some compilers, he finds that the while loop is not performed until
> just before the "return" 0. On other compilers, he finds that the
> while loop has been completely omitted, as it is obviously superfluous,
> resulting in that machine counting to a 1,000,000 is almost 0 seconds.
Which proves yet again that "observable behaivour" as defined by the C++
standard does not include "running time". It's a perfect example where
the definition of the virtual machine allows a specific optimization to
be performed, even though likely undesireable by the user. (In fact,
there's a section on empty loop optimization in the gcc manual that is
worth reading.)
And, yet this example shows that if you have certain expectations on
expectable behaivour (uhm), you need to encode these expectations into
the C++ standard somehow. There's nothing on threads in there right now,
even though there should. There's nothing on running time in there, and
there should not.
Thus, even something need to be done in the threading area, I do not
think that any action is required concerning the last example. Whether
in the first example some action is required is debatable. I would
believe that a compiler targetted at the embedded market should provide
a suitable extension to solve it, but it is potentially not a problem
for the majority of C++ programmers (I'm speculating!).
Threading, however, might become an issue for most folks in the near
future. Heck, I've already a dual core at home right now, and I want to
keep both cores busy. (-:
So long,
Thomas
Peter Dimov
> Peter Dimov wrote:
> > Higher up the chain is the "strong" thread safety, where instances are
> > writable from multiple threads without external synchronization.
>
> Which is rarely useful.
It's quite useful for mutexes. :-) More seriously, it's very useful if
the component is able to provide it in a lock-free manner.
> And not always even possible. How
> could you provide this guarantee with std::vector, for example,
> so that I wouldn't need a lock for:
>
> std::vector< int > v ; // Shared instance....
>
> v[ 0 ] = 42 ;
I won't even try. The interface of the component needs to be designed
with its thread safety level in mind. This was true for exception
safety, too - the famous Cargill stack example.
Le Chaud Lapin
> Le Chaud Lapin wrote:
> > Technically, IIUC, the compiler has the right to reorder these two
> > statements, since they are visibly independent, thus launching the
> > missile at a potentially friendly neighboring country and subsequently
> > pointing the launch pad at the enemy.
>
> Yup. And embedded programmers have to be very careful about what the
> compiler does in order to make that sort of code work right. In
> particular, you'd test that the code actually executed in the required
> order. Do you propose doing that for every lock and unlock in a
> multi-threaded program?
Well, I guess there are two options.
One, the whole issue of optimization (statement reordering in
particular) needs to be addressed (no pun intended), which is, in way,
separate from multi-threading, but definitely affects it. Not sure if
the people who like optimization will scream if someone says, "You need
to turn the optimizer off" if you want your code to execute correctly.
The other issue would be to add extra keywords to the language which
would be particular to threading that would prevent the compiler from
statement reordering. But then, I guess you would want to make those
keywords not thread-specific but useful in general.
For me, a lot of people are not going to like this, but if the compiler
did that with my code, I would turn off optimization for affected code,
which means not using macros for synchronization, etc. Not the best
solution.
-Le Chaud Lapin-
--
Greg Herlihy
> With that code, the compiler is STILL permitted to re-order main() to
> be:
>
> int main()
> {
> count++;
> StMutex lockMe( &gMutex );
> }
>
> There are no guarantees, since the compiler knows that StMutex does not
> modify count. Even if you try to 'hide' the definition of StMutex, even
> if it involves a kernel trap/syscall/etc - there is nothing in the c++
> standard that forbids this optimization - and yes, this kind of
> optimization is important to be able to have for non-mutex classes. So
> how does the compiler know that this class is very special and is a
> 'multi-threaded sequence point'?
No, the compiler may possibly eliminate count++ (in some cases), but it
is not allowed to execute it before StMutex's constructor executes.
After all, there is a sequence point between the two statements:
"At certain specified points in the execution sequence called sequence
points, all side effects of previous evaluations shall be complete and
no side effects of subsequent evaluations shall have taken
place."[§1.9/7]
The above rule applies only to "actual code generated." The compiler is
not obligiated to generate code for every statement - statements that
have no effect on the observable state of the program can be
eliminated. But otherwise, unless the statement is eliminated, then it
must execute as §1.9/7 requires - that is, in a specific order
relative to the program's other statements. Otherwise, if the compiler
could reorder sequence poitnts at will, it would not be possible to
write single-threaded C++ programs and be sure that they would run
correctly.
So either the program executes the statements in their current order or
it skips one or more of them. So for which ones does the compiler have
to generate code? The compiler is not allowed to optimize away StMutex.
Furthermore, since StMutex's constructor calls pthread_mutex_lock() - a
call which may or may not result in observable side effects, and its
destructor calls pthread_mutex_unlock() (which may or may not depend on
count's current value), the compiler must generate code for all three
statements that will execute in the order specified by the program.
> Any solutions require compiler language extensions to force the
> optimizer to not be so tricky. These compiler language extensions are
> not portable. To properly support threads in C++, the C++ language
> definition must standardize these kinds of things. It is not trivial,
> and it is discouraging to see how much code is multi-threaded 'hanging
> by a thread, working by accident' because the compiler did not do a
> specific optimization - yet...
The C++ Standard does make guarantees. Those guarantees may not have
been formulated with multi-threaded operation in mind, but that does
not mean that they are useless in a multi-threaded environment either.
Greg
Pete Becker
>
> I believe that most of the work on the standard will use their effort
> on this subject and the C++ memory model in order to assure that
> "newer" lock-free techniques can be used from C++.
>
"newer" as in forty years old. Lock-free techniques haven't proved
popular because they're brittle. Nothing in the current lock-free
infatuation changes that.
--
-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Edward Rosten
Mirek Fidler wrote:
> I have not said a damn thing where and how Lock and Unlock are
> defined;)
Precisely :-)
Though, in theory there is nothing stopping compilers doing magic
things like whole program (and library) optimization.
However, it appears that if you:
1) Hide the definitions of lock() and unlock() and make multi-thread
accessed data globally visible,
2) Avoid compilers that spill registers to static memory (not
difficult)
3) Initialize all static data before instantiating multiple threads
4) Use thread safe libraries
Then you will have gone a long way towards having well defined code.
I've probably missed a few things, though.
-Ed
--
Dave Steffen
"Le Chaud Lapin" <jaibu...@gmail.com> writes:
> Pete Becker wrote:
[...]
> > Yup. And embedded programmers have to be very careful about what the
> > compiler does in order to make that sort of code work right. In
> > particular, you'd test that the code actually executed in the required
> > order. Do you propose doing that for every lock and unlock in a
> > multi-threaded program?
>
> Well, I guess there are two options.
>
> One, the whole issue of optimization (statement reordering in
> particular) needs to be addressed (no pun intended), which is, in
> way, separate from multi-threading, but definitely affects it. Not
> sure if the people who like optimization will scream if someone
> says, "You need to turn the optimizer off" if you want your code to
> execute correctly.
>
> The other issue would be to add extra keywords to the language which
> would be particular to threading that would prevent the compiler
> from statement reordering. But then, I guess you would want to make
> those keywords not thread-specific but useful in general.
>
> For me, a lot of people are not going to like this, but if the
> compiler did that with my code, I would turn off optimization for
> affected code, which means not using macros for synchronization,
> etc. Not the best solution.
As one of the folks in the back of the room, who hasn't followed the
whole conversation, let me risk some redundancy and ask: have you (Le
Chaud Lapin, and others participating in the discussion) read Eric
Niebler's article at <http://www.artima.com/cppsource>?
I ask because I have been assuming, while (trying) to follow these
discussions, that the participants are aware of the article and, in
general, what the standardization committee is up to.
Since this article has an excellent discussion and summary of the
issues which in your post, quoted above, you seem to have rediscovered
for yourself, perhaps you're not aware of it, and perhaps it will save
some time and effort.
----------------------------------------------------------------------
Dave Steffen, Ph.D. Disobey this command!
Software Engineer IV - Douglas Hofstadter
Numerica Corporation
dg@steffen a@t numerica d@ot us (remove @'s to email me)
Pete Becker
Don't forget the "as if" rule: if a conforming program can't tell the
difference, the compiler is free to do anything, so long as the program
acts as if all the rules had been followed. Since, by assumption, the
lock is not affected by and does not affect the value of count, the
compiler is free to reorder the calls. A conforming program will have
exactly the same behavior both ways. It's only the non-comforming ones,
with a sneak path to modify count from another thread, that don't
necessarily act the same.
Incidentally, you should mention that your paraphrase "acual code
generated" is from a footnote, not from the normative text of the standard.
--
-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
Lourens Veen
However, the compiler also has blanket permission to change the
programme in any way it likes as long as the observable behaviour of
the programme is not affected. And the only things that are
observable is accessing volatile variables, and I/O functions. Thus,
it is allowed to reorder with impunity, as long as the outside world
can't figure out that it did so. And it is allowed to assume that the
programme is single-threaded, after all, there's nothing about having
more than one thread in the standard.
> So either the program executes the statements in their current order
> or it skips one or more of them. So for which ones does the compiler
> have to generate code? The compiler is not allowed to optimize away
> StMutex. Furthermore, since StMutex's constructor calls
> pthread_mutex_lock() - a call which may or may not result in
> observable side effects, and its destructor calls
> pthread_mutex_unlock() (which may or may not depend on count's
> current value), the compiler must generate code for all three
> statements that will execute in the order specified by the program.
Well, if both the constructor and the destructor cause observable side
effects, then the destructor must be exceuted after the constructor.
But the increment does not cause observable side effects, so it can
be moved to before the constructor call.
>> Any solutions require compiler language extensions to force the
>> optimizer to not be so tricky. These compiler language extensions
>> are
>> not portable. To properly support threads in C++, the C++ language
>> definition must standardize these kinds of things. It is not
>> trivial, and it is discouraging to see how much code is
>> multi-threaded 'hanging by a thread, working by accident' because
>> the compiler did not do a specific optimization - yet...
>
> The C++ Standard does make guarantees. Those guarantees may not have
> been formulated with multi-threaded operation in mind, but that does
> not mean that they are useless in a multi-threaded environment
> either.
Of course. But they're not enough.
Lourens
Thant Tessman
> peter koch larsen wrote:
>>
>> I believe that most of the work on the standard will use their effort
>> on this subject and the C++ memory model in order to assure that
>> "newer" lock-free techniques can be used from C++.
>>
>
> "newer" as in forty years old. Lock-free techniques haven't proved
> popular because they're brittle. Nothing in the current lock-free
> infatuation changes that.
This post (specifically the word "brittle") prompted me to finally look
up "lock-free" threading. When I said threading was basically a solved
problem, I was definitely *not* referring to this. I was referring to
language-level threading based on continuations (and signals if you got
'em). This kind of threading isn't brittle at all. It's also completely
impossible in a language like C++.
When are all you otherwise brilliant guys (I'm not being sarcastic)
gonna realize that C++ is intellectual flypaper? Its demand for
expertise and clever solutions traps programmers with the illusion of
progress.
-thant
--
Mirek Fidler
Peter Dimov wrote:
> Mirek Fidler wrote:
> > Well, I am not sure. Consider internal caches implemented using mutable
> > members (or, heavens forbid, const_cast ;). In that case, your "basic"
> > requirement would mean that ALL mutable members must have serialization
> > (locking) around them. That is IMO not a very good idea.
>
> You get to choose the thread safety level for your component. If you
> want concurrent reads to not be allowed, then you document them to not
> be. "Default is basic" only says what happens when you don't explicitly
> state otherwise.
Well, maybe it would be defined one more level between "basic" and "no"
to make me calm ;)
"Basic" sounds "minimal", but it is not minimal.
--
Mirek Fidler
U++ team leader. http://www.ultimatepp.org
Jeff Koftinoff
Greg Herlihy wrote:
>
> No, the compiler may possibly eliminate count++ (in some cases), but it
> is not allowed to execute it before StMutex's constructor executes.
> After all, there is a sequence point between the two statements:
>
> "At certain specified points in the execution sequence called sequence
> points, all side effects of previous evaluations shall be complete and
> no side effects of subsequent evaluations shall have taken
> place."[§1.9/7]
>
> The above rule applies only to "actual code generated." The compiler is
> not obligiated to generate code for every statement - statements that
> have no effect on the observable state of the program can be
> eliminated. But otherwise, unless the statement is eliminated, then it
> must execute as §1.9/7 requires - that is, in a specific order
> relative to the program's other statements. Otherwise, if the compiler
> could reorder sequence poitnts at will, it would not be possible to
> write single-threaded C++ programs and be sure that they would run
> correctly.
>
Thanks for the insight; This is fascinating to me... All of the CPU's
that I am writing code for has either vector processing or multiple
instruction units in parallel. The assembly code that the compilers
generate most definitely parallelize and re-order these kinds of
statements, especially if the objects that are created are small enough
to fit in a register and the compiler does dependency analysis of the
data.
Does this mean that these compilers that I am using are not compliant
to the c++ standard?
If so, does that mean that the c++ standard dictates that VLIW cpu's
with parallel execution units can not be effectively, efficiently
utilized without violating the standard?
> So either the program executes the statements in their current order or
> it skips one or more of them. So for which ones does the compiler have
> to generate code? The compiler is not allowed to optimize away StMutex.
> Furthermore, since StMutex's constructor calls pthread_mutex_lock() - a
> call which may or may not result in observable side effects, and its
> destructor calls pthread_mutex_unlock() (which may or may not depend on
> count's current value), the compiler must generate code for all three
> statements that will execute in the order specified by the program.
>
However the original code does not specify what StMutex's constructor
did call... And the compiler most definitely can deduce that both
pthread_mutex_lock() and pthread_mutex_unlock() are not given the
address of count and therefore can not read or write it.
--jeffk++
www.jdkoftinoff.com
Mirek Fidler
Edward Rosten wrote:
> Mirek Fidler wrote:
> > I have not said a damn thing where and how Lock and Unlock are
> > defined;)
>
> Precisely :-)
>
> Though, in theory there is nothing stopping compilers doing magic
> things like whole program (and library) optimization.
>
> However, it appears that if you:
>
> 1) Hide the definitions of lock() and unlock() and make multi-thread
> accessed data globally visible,
>
> 2) Avoid compilers that spill registers to static memory (not
> difficult)
>
> 3) Initialize all static data before instantiating multiple threads
>
> 4) Use thread safe libraries
>
> Then you will have gone a long way towards having well defined code.
> I've probably missed a few things, though.
Yes, I *HOPE* so. These are in fact rules that everybody doing MT code
depends on.
The problem is that this should not be the question of "HOPE", but
there should be standard definition of these issues.
--
Mirek Fidler
U++ team leader. http://www.ultimatepp.org
Chris Vine
[snip]
> If we replace the code with its C equivalent, and use Posix (and
> Posix guarantees), it is guaranteed to work. The low level
> hardware support Pete asked about is:
>
> -- At most one thread can acquire the mutex at a time; any
> other thread attempting to acquire it will block. (That's
> really the definition of a mutex.)
>
> -- Acquiring or releasing the mutex assures full hardware
> synchronization: all previous writes are fully completed to
> main memory before leaving the function, and no following
> read has been started.
>
> -- The compiler does not move writes and reads across calls to
> acquire and release.
>
> -- Accesses to a single long do not touch any other object.
> (This is almost always the case for a long, but could easily
> be a problem with char: some architectures write a char by
> reading a word, replacing the char in it, then writing the
> word back. In such cases, the compiler must ensure that
> individual char's are in different words, or you there's no
> way to implement anything that is thread safe.)
>
> All of these are necessary requirements. (I can't find anything
> but the first in the Windows documentation, but it's quite
> possible that I don't know where to look. It's not in any
> obvious place in the Posix specification either.
[snip]
It's in section 4.10, General Concepts, Memory Synchronization, out of the
main threading sections (probably out of embarrassment).
I do not think that any practical implementation can apply it literally, if
performance is wanted - it just cannot be that calling, say,
pthread_mutex_unlock() in a multi-multi-processor system will cause all
caches to synchronize memory, whatever the memory locations they happen to
access (or the memory locations which the releasing thread happened to
modify) and regards of whether they subsequently acquire the same mutex.
It is very difficult to come up with a standard for the virtual machine
which gets these things right (I wouldn't like to try to do so) and the C++
threading committee are to be commended for their work on this.
Chris
--
To reply by e-mail, remove the "--nospam--"
Sean Kelly
> Jeff Koftinoff wrote:
> > With that code, the compiler is STILL permitted to re-order main() to
> > be:
> >
> > int main()
> > {
> > count++;
> > StMutex lockMe( &gMutex );
> > }
> >
> > There are no guarantees, since the compiler knows that StMutex does not
> > modify count. Even if you try to 'hide' the definition of StMutex, even
> > if it involves a kernel trap/syscall/etc - there is nothing in the c++
> > standard that forbids this optimization - and yes, this kind of
> > optimization is important to be able to have for non-mutex classes. So
> > how does the compiler know that this class is very special and is a
> > 'multi-threaded sequence point'?
>
> No, the compiler may possibly eliminate count++ (in some cases), but it
> is not allowed to execute it before StMutex's constructor executes.
> After all, there is a sequence point between the two statements:
>
> "At certain specified points in the execution sequence called sequence
> points, all side effects of previous evaluations shall be complete and
> no side effects of subsequent evaluations shall have taken
> place."[§1.9/7]
Doesn't the "as if" rule apply here? In other words, if the compiler
can determine that such an operation would not violate program
consistency according to the C++ virtual machine, then isn't it allowed
to optimize regardless of the sequence point language above?
Sean
Le Chaud Lapin
Hans wrote:
> Assume I have a struct s containing fields x and y, both of which are
> initially zero. Assume I have two threads executing
>
> Thread 1: s.x = 1;
> Thread 2: s.y = 1;
>
> After I wait for both threads to complete (using your favorite threads
> API), can I conclude that both s.x and s.y are one?
>
> In real life, this corresponds to the question of whether x and y can
> be protected by separate locks, which is important.
[snippage]
> Yes, unless either
> - x or y is a bit-field (in which case things get complicated)
> - you are using default options to compile for an architecture like
> Alpha which in prehistory did not have byte store instructions, and
> either x or y is a byte in size, and they are "too close together"
> - this is embedded in more complicated code, and your compiler decided
> to combine multiple field updates in order to generate faster code
> - your compiler was just being perverse, because the combined C, C++
> and pthreads specs clearly don't require both fields to be one at the
> end of this, even if they are both long integers.
>
> I claim this is the wrong answer if you are trying to teach someone how
> to write multithreaded code. This is the sort of problem we're trying
> to fix.
[snippage]
I can see how the coin could flip either way. It depends on programmer
expectations. In all honesty, if I saw the example above, I would
probably give the reasons you listed, especially the one about the bit
fields.
So I think there is probably a differences of expectation. If the
compiler optimizes code to causes surprises, some people would rather
that not happen, "not" being used in the portable sense. Other people
might get bitten, and think, "Wow, I have to turn off the
optimizations."
My guess is that someone who has never written a multi-threaded
application, upon hearing that you and other experts are going to fix
the language so that they could have that, are going to be very
enthusiastic, and willing to wait. (Why suffer needlessly?)
But for me, I might be of the old guard, a Luddite who is willing to
spend effort to get the compilers to behave (I already have to do that
for other things).
If the standardization process is democratic, then of course, the
majority of programmers will get what they want/need.
-Le Chaud Lapin-
Le Chaud Lapin
>
> > void increment_count()
> > {
> > Critical_Section cs; // constructor calls
> > InitializeCriticalSection();
> >
> > ++count;
> > cs.leave(); // LeaveCriticalSection();
> > // ~cs calls DeleteCriticalSection();
> > }
> >
You're right! I hit the post-message button before I realized that I
had made this mistake.
Le Chaud Lapin
peter koch larsen wrote:
> { Redundant signature removed. -mod/aps }
>
> Le Chaud Lapin skrev:
> > James Kanze wrote:
> > > Except if one of the writes migrates across a spin-lock.
> > > (Spin-locks are only guaranteed if special hardware instructions
> > > are used on a Sparc---or a PC. Hardware instructions that are
> > > never generated by Sun CC or by g++---or by the current version
> > > of VC++.)
> >
> > time. In fact, they are used so often, Microsoft make special library
> > functions just for spin-locks. Microsoft uses spin-locks in its own
> > implementation of what they call critical sections.
> (assembly) code used by the compićer-
Just to be clear, there is an entire family of Interlocked-XXXX
functions available on Windows that are available for use.
> > > First you have to define what that part is. Suppose that the
> > > library writer says that you need to manually acquire a lock
> > > before calling malloc (or operator new)?
> >
> > I would ask the library writer why he did that when it does not make
> > sense. It is better to have a thread-safe new() which I use in all my
> > multi-threaded code.
>
> Okay! But this is one of the areas where the C++ standard is going to
> change. It will say something in the direction of that new must be
> reentrant.
The heap requires global state, so if new() and delete() are made
generally reentrant, there will be an unavoidable associated cost.
What does does a single-threaded programmer do when he is told that
new() is reentrant and he simply has to live with this fact?
> Another thing it will say is that the compiler is not
> allowed to reorder code across certain function calls (e.g. calls to
> mutexes), and that it must allow two threads to simultaneously throw an
> exception.
This might be a good idea in general. Seems that, even in the world of
single-threaded applications, this would be a problem, if some feel
that it is a problem.
> I believe that most of the work on the standard will use their effort
> on this subject and the C++ memory model in order to assure that
> "newer" lock-free techniques can be used from C++.
:) Now we get to the real issue. I think that a big fight is
forthcoming, not now, but in the future. I inferred from reading
between the lines of post that there were some people who had lock-free
techniques in mind but were not explicitly saying so. I also inferred
that some people do not particularly like lock-free techniques. I am
indifferent. But one thing is certain, whatever approach is taken, C++
will not be the C++ of today. The change will be semi-radical. It
will start to influence how programmers think about system structure.
> > Saying that a C++ class is not thread safe because objects of the class
> > all operate on a global variable...that's obvious.
>
> This is not obvious at all. On the contrary, many would expect that two
> threads would be able to simultaneously read data and also call some
> constant functions such as e.g. std::vector<>.begin(),
> std::vector<>.end() and std::vector<>operator[]. The standard does not
> give us such promises yet, and we will have to revert to the compiler
> documentation in order to verify the behavior of our program.
This is, again, a difference of expectations. The first thing I see
when I see a global object that has a member function being invoked on
it, const or not, is that the function might result in a perturbation
of state. I ask myself, if this is going to be a problem in a
multi-threaded application. If the answer is yes, I add protection.
If the answer is no, I use no protection. If the answer is "I don't
know", I add protection.
There are others who might interpret the semantics of const to apply to
multi-threading also. Note here, however, that const will not mitigate
the effects of a mutable member variable. So it was never the case
that const means, "will not change."
But again, this is a difference of expectation.
> > Now if you are saying that the C++ committee needs to structure there
> > libraries so that that they can be single-threaded and multi-threaded,
> > I agree with that, but that is the library, not the language proper.
> > And I have always said that this is a library issue more than anything.
> >
> Those libraries are part of the standard, and it is not just a library
> issue. The "difficult" part is IMHO the memory model and the new
> thread-related libraries (if they are to appear).
Yes, someone is going to have to take a consensus of expectations on
say, map<>. It will be have to be determined, what is the "mood" or
"mentality" of a programmer when s/he uses a global const map<>. This
will get very interesting indeed.
peter koch larsen
Pete Becker skrev:
> peter koch larsen wrote:
> >
> > I believe that most of the work on the standard will use their effort
> > on this subject and the C++ memory model in order to assure that
> > "newer" lock-free techniques can be used from C++.
> >
>
> "newer" as in forty years old. Lock-free techniques haven't proved
> popular because they're brittle. Nothing in the current lock-free
> infatuation changes that.
>
programming anytime near, but there will still be (important) niches
where lock-free programming (defined as mutating access to shared data)
will be most valuable.
/Peter
--
James Kanze
> Pete Becker wrote:
> > Le Chaud Lapin wrote:
> > > Mutex counter_mutex; // global
> > > void increment_counter ()
> > > {
> > > counter_mutex.acquire();
> > > ++count;
> > > counter_mutex.release();
> > > }
> > The increment has no visible side effects, so the compiler is not
> > obliged to sandwich it between the acquire and the release. How do you
> > ensure that the compiler won't do either of those?
> I would take whatever recourse is available in all situations like
> these. If I may answer with an example...
> Consider a single-threaded program that has a function that aims a
> missile at an adjacent country and launches it. Aiming is achieved by
> incrementing an memory-mapped register. Launching is achieved by
> setting a different memory mapped register to "true":
> static unsigned int ®ister_azimuth = *reinterpret_cast<unsigned int
> *>(0x12345678);
> static bool ®ister_launch = *reinterpret_cast<bool *>(0x12345680);
> void aim_and_launch_missile ()
> {
> register_azimuth += 75; // degrees
> register_launch = true;
> }
> Technically, IIUC, the compiler has the right to reorder these two
> statements, since they are visibly independent, thus launching the
> missile at a potentially friendly neighboring country and subsequently
> pointing the launch pad at the enemy.
Not just technically. It wouldn't be at all surprising if the
compiler did. And no embedded programmer with any experience
would write something like that.
C++ does have something (inherited from C) designed to support
memory mapped IO: volatile. The exact semantics of it are
implementation defined, because obviously, memory mapped IO
pretty much depends on the platform you're running the program
on. The intent, however, is clear here (even if neither Sun CC
nor g++). An embedded programmer would declare his references
volatile, which means that the order between accesses through
these references (but not for anything else) is ordered, and he
would also read the documentation of the compiler very
carefully, to ensure that it interpreted volatile in a way that
was compatible with his needs. (Although to tell the truth, as
a long time embedded programmer, I would write such critical
parts in assembler. Just to be sure.)
Note that volatile only applies to accesses through a volatile
qualified lvalue expression. Just declaring one of the
references volatile isn't sufficient, since the compiler could
still move the other. And that an object being constructed is
never volatile (just as it is never const); volatile only takes
effect after construction.
> Another example where a programmer has written a piece of code that he
> thought was portable that gives a rough idea of how fast 1,000,000
> global memory references can be performed by the CPU:
> static int x;
> int main ()
> {
> Instant before = now();
> unsigned int count = 1000000;
> while (count--)
> x = 0;
> Instant after = now();
> cout << count << " memory references in " << (after-before) << "
> seconds." << endl;
> return 0;
> }
> On some compilers, he finds that the while loop is not performed until
> just before the "return" 0. On other compilers, he finds that the
> while loop has been completely omitted, as it is obviously superfluous,
> resulting in that machine counting to a 1,000,000 is almost 0 seconds.
I think that almost all current compilers fall into the latter
category. G++, Sun CC and VC++ certainly do: the code generated
by g++ (for Sparc) for the loop is:
sethi %hi(x), %g1
mov %o0, %l1
st %g0, [%g1+%lo(x)]
No loop at all. Sun CC gives:
sethi %hi(0xf4000),%g2
sethi %hi(x),%g3
st %g0,[%g3+%lo(x)]
add %g2,575,%i0
or %g0,%o0,%i1
orcc %g0,%i0,%g0
.L900000116:
add %i0,-1,%i0
bne .L900000116
orcc %g0,%i0,%g0
The loop is still there, but the assignment to x has been moved
out of it. And for what it's worth, VC++ (on a Windows PC, this
time) generates:
mov DWORD PTR _x, 0
(and mixes it in with the storing of the results of the first
call to time()). Again, no loop.
I know that when I designed my benchmark framework, I had to
jump through hoops to ensure that the compiler didn't optimize
the benchmark loop away completely. (And I know that some
really sophisticated compilers can still do it.) And that all
of the standard benchmarks (Whetstone, dhrystone, etc.) go to
great lengths to output a value which depends on all of the
loops actually being executed.
(I might add that on any modern machine, 1,000,000 global memory
references will take considerably less than a second. In fact,
on most modern machines, even if the compiler didn't optimize,
the hardware would; the code in the loop would get around to the
second write before the first was finished, the hardware would
notice that they both had the same effect, and suppress one of
them. Unless, of course, you inserted the necessary fence or
membar instructions.)
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
Pete Becker
>
>
> If so, does that mean that the c++ standard dictates that VLIW cpu's
> with parallel execution units can not be effectively, efficiently
> utilized without violating the standard?
>
The standard tells you what a well-formed program means. If your
compiler generates code that does what the standard says the program
should do then it conforms to the standard, even if it transparently and
correctly passes tasks out among various cpus.
Note that the discussion here is about the inverse problem: what changes
are needed to the language definition to be able to write programs that
explicitly take advantage of multiple threads of execution.
--
-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
James Kanze
> Pete Becker wrote:
> > Le Chaud Lapin wrote:
> [sample code by Chaud Lapin reaffirming what Pete wrote]
> > > Technically, IIUC, the compiler has the right to reorder these two
> > > statements, since they are visibly independent, thus launching the
> > > missile at a potentially friendly neighboring country and subsequently
> > > pointing the launch pad at the enemy.
> > Yup. And embedded programmers have to be very careful about what the
> > compiler does in order to make that sort of code work right. In
> > particular, you'd test that the code actually executed in the required
> > order. Do you propose doing that for every lock and unlock in a
> > multi-threaded program?
> Well, I guess there are two options.
> One, the whole issue of optimization (statement reordering in
> particular) needs to be addressed (no pun intended), which is, in way,
> separate from multi-threading, but definitely affects it.
The issue has been addressed. It very much conditionned the
wording in '1.9, the concept of sequence points, and the
undefined behavior in '5/4 (which many of us would like to see
tightened), for example. The problem is that the way it was
addressed has no meaning for multithreaded code.
> Not sure if the people who like optimization will scream if
> someone says, "You need to turn the optimizer off" if you want
> your code to execute correctly.
You bet they will. Some people need all the performance they
can get. (I'm not one of them, and I don't normally use the
optimizer, even on delivered code. But I've talked to people
who do need performance.)
Note that C99 goes one step further, and has added a new keyword
(restrict) solely to allow the programmer to pass additional
information to the optimizer; restrict has no effect whatsoever
unless the compiler is trying to optimize code.
> The other issue would be to add extra keywords to the language which
> would be particular to threading that would prevent the compiler from
> statement reordering. But then, I guess you would want to make those
> keywords not thread-specific but useful in general.
The problem is that enforcing ordering, in general, would mean
slowing up even unoptimized code by a factor of maybe 5, on a
modern machine. (It means that you'd have to insert fences
between every access, in order to prevent hardware re-ordering.)
And it isn't at all necessary; all you need and want is that at
certain, well defined instances, all previous writes are
completed, and no following reads have started. Posix requires
functions like pthread_lock and pthread_unlock to provide this,
in addition to their functionality on the mutex. In practice,
Windows does too, although I've never seen it documented. Which
means that if you use the system primitives for synchronization
on these systems, all you have to worry about is compiler code
movement. Posix provides guarantees for this as well, at least
for C; I've not seen similar written guarantees for Windows, but
I can't imagine VC++ doing otherwise.
Part of the goal in standardizing is to define a set of
functions which provides such guarantees. (Note that in this
case, library and language overlap. The language allows code
movement, except over such and such a function.)
> For me, a lot of people are not going to like this, but if the compiler
> did that with my code, I would turn off optimization for affected code,
> which means not using macros for synchronization, etc. Not the best
> solution.
That's life. Slowing all programs down by a factor of 5 isn't
the best solution, either, and making all reasonable
optimization impossible (and slowing some numeric programs down
by a factor of maybe 20) isn't a particularly good solution
either.
--
James Kanze (GABI Software) email:james...@gmail.com
Conseils en informatique orientie objet/
Beratung in objektorientierter Datenverarbeitung
9 place Simard, 78210 St.-Cyr-l'Icole, France, +33 (0)1 30 23 00 34
Nicola Musatti
Thant Tessman wrote:
[...]
> This post (specifically the word "brittle") prompted me to finally look
> up "lock-free" threading. When I said threading was basically a solved
> problem, I was definitely *not* referring to this. I was referring to
> language-level threading based on continuations (and signals if you got
> 'em). This kind of threading isn't brittle at all. It's also completely
> impossible in a language like C++.
Do you have any reading reccomendations?
Cheers,
Nicola Musatti