stl deques and "volatile"
Gerhard Prilmeier
please consider the following code:
#include <deque>
using namespace std;
int main(int argc, char* argv[])
{
volatile deque<volatile int> d;
d.end();
return 0;
}
The line where the end-iterator is queried causes an error (no legal
conversion). I can overcome this problem by having a non-volatile pointer to
the deque, assigned using const_cast. This is the only way I guess?
Now, if you remove the line "d.end();" another error appears, depending on
the compiler it might also have already appeared before. The error occures
in a deallocate function, where no overload of delete can take a pointer to
a volatile type. Is this impossible to fix?
I must admit that I haven't totally grasped the meaning of volatile yet,
which might be the root cause of my problem. I use the deque in multiple
threads, thus I declare it volatile to prevent the compiler from caching it
in a CPU register or whatever. The members of the deque might also be
changed, so they are volatile too. (I don't work with ints here, but with a
POD structure containing a pointer which may be changed)
Is this correct usage of volatile?
How can I achieve what I want to do?
Thanks for your input!
Gerhard
Alexander Terekhov
Gerhard Prilmeier wrote:
>
> Hello,
>
> please consider the following code:
>
> #include <deque>
> using namespace std;
> int main(int argc, char* argv[])
> {
> volatile deque<volatile int> d;
> d.end();
> return 0;
> }
>
> The line where the end-iterator is queried causes an error (no legal
> conversion). I can overcome this problem by having a non-volatile pointer to
> the deque, assigned using const_cast. This is the only way I guess?
>
> Now, if you remove the line "d.end();" another error appears, depending on
> the compiler it might also have already appeared before. The error occures
> in a deallocate function, where no overload of delete can take a pointer to
> a volatile type. Is this impossible to fix?
>
> I must admit that I haven't totally grasped the meaning of volatile yet,
sig_atomic_t statics and severely restricted (in C++) "jumping" aside, it's
simply an abstract model for "hardware registers" -- ``What constitutes an
access to an object that has volatile-qualified type is implementation-
defined'' [ISO/IEC 9899:1999 (E), Pg. 109].
> which might be the root cause of my problem. I use the deque in multiple
> threads, thus I declare it volatile to prevent the compiler from caching it
> in a CPU register or whatever. The members of the deque might also be
> changed, so they are volatile too. (I don't work with ints here, but with a
> POD structure containing a pointer which may be changed)
>
> Is this correct usage of volatile?
Nope.
> How can I achieve what I want to do?
Using execution and memory synchronization calls.
regards,
alexander.
Gerhard Prilmeier
> sig_atomic_t statics and severely restricted (in C++) "jumping" aside,
it's
> simply an abstract model for "hardware registers" -- ``What constitutes an
> access to an object that has volatile-qualified type is implementation-
> defined'' [ISO/IEC 9899:1999 (E), Pg. 109].
>
> > which might be the root cause of my problem. I use the deque in multiple
> > threads, thus I declare it volatile to prevent the compiler from caching
it
> > in a CPU register or whatever. The members of the deque might also be
> > changed, so they are volatile too. (I don't work with ints here, but
with a
> > POD structure containing a pointer which may be changed)
> >
> > Is this correct usage of volatile?
>
> Nope.
>
> > How can I achieve what I want to do?
>
> Using execution and memory synchronization calls.
Aren't synchronization calls a different kind of thing?
I use mutexes to make sure don't access variables at the same time, yes, but
still I have to make sure that no caching or whatever appears. My
understanding of volatile is the following:
bool flag = true;
while(flag)
{
Sleep(100);
}
Now if flag was to be changed by a different thread, the compiler might
figure that Sleep() can't possibly change flag, cache flag in a speedy
hardware location and use the cached version from now on. Thus, the second
thread may set flag as false as it wants, the loop is endless. This
situation can be avoided by declaring
volatile bool flag = true;
If this is correct, I still can not figure out what's wrong with the
approach I described in my original post.
Thanks in advance for any help,
Gerhard
tom_usenet
No, this isn't what volatile does. It is generally used when a
variable might be changed by some hardware or whatever, not another
thread. "volatile" is generally completely useless in multithreaded
code - it simply slows everything down by adding a memory
sychronisation point every time you access it.
Your threading library and compiler will have guarantees as to the
fact that if you change the value of a variable in another thread
(locking appropriately), and then access the value in the second
thread, it will have been updated correctly. Mutexes act as memory
sychronisation points that it can't cache values across, as well as
providing the correct locking.
So, just use sychronisation primitives (such as in the boost.threads,
posix or win32 libraries) and your system will guarantee that properly
access locked variables work.
volatile is required by very few c++ programmers in their lifetimes.
Usually just low level hardware access (where the hardware changes the
data), with data that is modified by interrupt service routines, and
by memory that is shared my multiple *processes*. Within multiple
threads in one process, it isn't required.
Tom
Gerhard Prilmeier
> variable might be changed by some hardware or whatever, not another
> thread. "volatile" is generally completely useless in multithreaded
> code - it simply slows everything down by adding a memory
> sychronisation point every time you access it.
>
> Your threading library and compiler will have guarantees as to the
> fact that if you change the value of a variable in another thread
> (locking appropriately), and then access the value in the second
> thread, it will have been updated correctly. Mutexes act as memory
> sychronisation points that it can't cache values across, as well as
> providing the correct locking.
>
> So, just use sychronisation primitives (such as in the boost.threads,
> posix or win32 libraries) and your system will guarantee that properly
> access locked variables work.
>
> volatile is required by very few c++ programmers in their lifetimes.
> Usually just low level hardware access (where the hardware changes the
> data), with data that is modified by interrupt service routines, and
> by memory that is shared my multiple *processes*. Within multiple
> threads in one process, it isn't required.
>
This sounds good - the compiler identifies critical sections from where I
use mutexes and does all the necessary work himself.
Opposed to that, Andrei Alexandrescu wrote a lengthy article about using
volatile in multhithreaded programs:
http://www.cuj.com/experts/1902/alexandr.htm
You see me rather confused, unfortunately.
Who is wrong? Are both right?
Alexander Terekhov
tom_usenet wrote:
[...]
> >bool flag = true;
> >while(flag)
> >{
> > Sleep(100);
> >}
Don't do this. Follow the portable memory synchronization rules:
http://www.opengroup.org/onlinepubs/007904975/basedefs/xbd_chap04.html#tag_04_10
(Memory Synchronization)
[...]
> "volatile" is generally completely useless in multithreaded
> code - it simply slows everything down
Well, portably, YES. There are non-portable "extensions" that
make use of volatile (remember: "What constitutes an access to
an object that has volatile-qualified type is implementation-
defined" to fight word-tearing race condition, for example:
http://groups.google.com/groups?selm=3D495F1B.60DEA4C1%40web.de
(Subject: Re: "memory location")
> by adding a memory sychronisation point every time you access it.
No, it doesn't add "memory synchronization point every time you
access it" (in C/C++):
http://groups.google.com/groups?threadm=3D36E35C.D8C511AE%40web.de
(Subject: "memory location")
http://groups.google.com/groups?threadm=ajaqne%24n9u%241%40glue.ucr.edu
http://groups.google.com/groups?selm=GJb79.39%24hx2.1165398%40news.cpqcorp.net
http://groups.google.com/groups?selm=3D60D039.DF2B7C42%40web.de
(Subject: concurrency-induced memory-access anomalies)
> Your threading library and compiler will have guarantees as to the
> fact that if you change the value of a variable in another thread
> (locking appropriately), and then access the value in the second
> thread, it will have been updated correctly. Mutexes act as memory
> sychronisation points that it can't cache values across, as well as
> providing the correct locking.
Right. But not only mutexes; ALL *execution* synchronization points
are also *memory* synchronization points. However, Java (and CLI/C#)
has completely deferent "volatiles" -- they ARE relevant to threading
and provide load-acquire and store-release memory sync. semantics
(plus atomicity w.r.t. themselves, of course).
> So, just use sychronisation primitives (such as in the boost.threads,
> posix or win32 libraries) and your system will guarantee that properly
> access locked variables work.
STAY AWAY FROM THE CURRENT VERSION OF BOOST.THREADS.
For now, stick to something like http://sources.redhat.com/pthreads-win32,
"pthreads-etc." and non-portable thinks like IOCP/MS-Win, etc. for "better
performance and scalability".
regards,
alexander.
Alexander Terekhov
Gerhard Prilmeier wrote:
[...]
> Opposed to that, Andrei Alexandrescu wrote a lengthy article about using
> volatile in multhithreaded programs:
> http://www.cuj.com/experts/1902/alexandr.htm
>
> You see me rather confused, unfortunately.
> Who is wrong? Are both right?
Ha! Yeah, that was rather funny and noisy stuff, indeed. ;-)
http://groups.google.com/groups?selm=94ccng%24m2t%241%40nnrp1.deja.com
"Please, Andrei, not 'volatile'!"
http://groups.google.com/groups?selm=3A66E4A1.54EE37AD%40compaq.com
<quote>
Andrei Alexandrescu wrote:
> In my opinion the use of volatile that the article suggests is fully in
> keeping with its original intent. Volatile means "this data can be changed
> beyond compiler's ability to figure it out" and this is exactly what happens
> data that's shared between threads. Once you lock the synchronization
> object, the code's semantics become single-threaded so it cannot be changed
> beyond compiler's ability to comprehend and so you can cast volatile away.
> What's so wicked in that? Looks very kosher to me :o).
After the number of responses in this thread, you can still say that? Amazing.
Original intent? The intent of the "volatile" attribute is to change the code
generated by the compiler on references to memory tagged with that attribute.
You are using the syntactic tag while defeating the intent of that tag, never
allowing the compiler to generate code in the way required by that tag. Abuse,
I'm afraid, is often in the eye of the beholder, but it's hard to see how
anyone could refuse to admit that this is, at best, "pretty close to the edge".
In fact, though you've said you weren't intending to advocate direct access to
any "volatile" variable without applying synchronization and casting away
"volatile", your first Gadget::Wait example does precisely that, and is wildly
incorrect and dangerously misleading. Compiler volatile semantics are not
sufficient when sharing flag_ between threads, because the hardware, as well as
the compiler, may reorder memory accesses arbitrarily, even with volatile. (Nor
would a compiler implementation that issued memory barriers at each sequence
point for volatile variables be sufficient, unless ALL data was volatile, which
is impractical and unreasonably expansive.)
Memory barriers must be applied where necessary on many architectures, and
there is no standard or portable way to generate them. There is no excuse for a
compiler to require both volatile AND memory barriers, because there's no
excuse for a compiler to reorder memory access around its own memory barrier
construct. (Usually either a compiler builtin such as Compaq C/C++ "__MB()" or
an asm("mb") "pseudocall".) The standard and portable way to ensure memory
consistency is to rely on the POSIX memory model, which is based solely on
specific POSIX API calls rather than expensive and inappropriately defined
language keywords or nonportable hardware instructions. A system or compiler
that does not provide the proper memory model (without volatile) with proper
use of the portable POSIX API calls does not conform to POSIX, and cannot be
considered for serious threading work. Volatile is irrelevant.
Entirely aside from the language issues, my point was simply that "volatile",
and especially its association with threaded programming, has been an extremely
confusing issue for many people. Simply using them together is going to cause
even more confusion. The illusory promise of volatile will lead novices into
trouble.
In contradiction to your absurd statement that "writing multithread programs
becomes impossible" without volatile, the intended C and C++ semantics
associated with volatile are neither useful nor sufficient for threaded code.
And it is WITH volatile, not without, that "the compiler wastes vast
optimization opportunities", especially as the expense of meeting the volatile
"contract" is of no benefit to threaded code.
With all that said, I wish there was a language keyword intended to be used in
the manner you're (ab)using volatile. Though I think your method falls far
short of your promises to detect all race conditions at compile time (unless
applying such a limited and unusual definition of "race" that the term becomes
essentially meaningless), it does have value. What you've done is, in some
ways, one step beyond the Java "synchronized" keyword. It provides not only
syntax to require that access be synchronized, but your type magic allows the
compiler to determine whether, in the current scope, the data is already
synchronized. (This might allow avoiding the Java dependency on expensive
recursive mutexes. Though I'm not entirely convinced your method would survive
a complicated application with multilevel lock hierarchies, I'm not entirely
convinced it wouldn't, either.)
Still, if you're willing to point out that applying volatile to tag temporaries
would be "abuse", recognize that others might reasonably draw the line a bit
differently.
</quote>
http://groups.google.com/groups?selm=3A684272.EC191FD%40compaq.com
<quote>
Andrei Alexandrescu wrote:
> "Dave Butenhof" <David.B...@compaq.com> wrote in message
>
> > In fact, though you've said you weren't intending to advocate direct access to
> > any "volatile" variable without applying synchronization and casting away
> > "volatile", your first Gadget::Wait example does precisely that, and is wildly
> > incorrect and dangerously misleading. Compiler volatile semantics are not
> > sufficient when sharing flag_ between threads, because the hardware, as well as
> > the compiler, may reorder memory accesses arbitrarily, even with volatile. (Nor
> > would a compiler implementation that issued memory barriers at each sequence
> > point for volatile variables be sufficient, unless ALL data was volatile, which
> > is impractical and unreasonably expansive.)
>
> Yeah, I learned to hate the Gadget example. Where's that chrononaut to go
> back in time and remove it.
You can, at least, write a followup article to correct and clarify. It won't
reach everyone who ought to see it, but it's better than nothing.
> > In contradiction to your absurd statement that "writing multithread programs
> > becomes impossible" without volatile, the intended C and C++ semantics
> > associated with volatile are neither useful nor sufficient for threaded
> code.
>
> I agree. Boy this is hard :o).
Yeah, well, you certainly got a lot of attention for your paper. As the saying
goes, "I don't care what they say about me as long as they get my name right."
(Or, "all advertising is good advertising.")
You're right; it is hard to play around between the cracks as you're doing.
There's not a lot of wiggle room. Sounds like you'll be more careful in the
future, and that's good. Now your job is to try to help anyone you confused the
first time around. ;-)
> > And it is WITH volatile, not without, that "the compiler wastes vast
> > optimization opportunities", especially as the expense of meeting the volatile
> > "contract" is of no benefit to threaded code.
>
> What I meant was that the compiler would waste optimization opportunities if
> it treated all variables as if they were volatile. But anyway, given that
> volatile is not really of a lot of help...
Ah. Yes, eliminating all optimization would make threaded programming
impractical, at best. After all, most (though not all) applications use threads
to improve performance. While it's true that in some cases parallelized but
unoptimized code might outperform optimized unthreaded code, I wouldn't want to
bet my job on it happening a lot.
> I am glad I'm not the only one who felt there is something cool here.
> Perhaps the most important point of the article is the importance of type
> modifiers in programming languages, and how one can define/use such
> modifiers to help with multithreaded programs.
Oh yes, it's cool. In principle. It's also fairly simple, and may prove
applicable only to relatively simple programs (e.g., that never hold more than
one mutex at a time, as we'll get into below).
Perhaps this is an interesting opportunity for the language folks; to build a
language (or maybe a new C++ version) that allows something like an
"attributedef" statement, defining properties of an attribute keyword that can
be applied to classes and typedefs. You, for example, could have used a
"locked" keyword instead of confusingly overloading "volatile". I'll bet such a
keyword, which could be added or cast away at need, would enable all sorts of
interesting extensions of the compiler's type checking... including perhaps
that thing about detecting temporaries.
> The projects to which I've applied the idiom are "classic" multithreaded
> applications. The technique is easy to explain and is field tested, and not
> only by me - programmers who are not MT saviors have caught it up in no time
> and loved it, and this is is an important reason for which I believe the
> idiom is valuable. Indeed, I don't know what would happen on special
> threading models. Could you please tell what multilevel lock hierarchies
> are?
There are many cases in complicated threaded applications where a region of
code must hold more than one lock at the same time. Such code must always have
DANGER signs posted at the entrances, and you need to be really careful. Still,
there are well established ways to deal with the risks (just as, foolish though
it may be, we often drive our cars onto highways without bothering to consider
that we might die there).
The risk is deadlock, or "deadly embrace" -- the good ol' Dining Philosophers
problem. One thread owns Mutex A, and waits for Mutex B; while another thread
owns Mutex B and waits for Mutex A. The most common and "well structured"
solution to this problem is to design a strict "mutex hierarchy" defining the
"level" of each mutex. That is, if one needs both the mutex on the head of a
queue and on an element of the queue, one must always first lock the head and
only then lock the element. There is no risk of deadlock, because the element
cannot be locked unless the head is also locked.
Your technique doesn't make it impossible or even more difficult to manage
mutex hierarchies: but it doesn't make it any easier, either. Furthermore, the
"advertised power" of the technique (as currently structured) is somewhat
weakened when an object needs to be protected by multiple mutexes: locking the
element would provide a non-volatile pointer, even though correct use of that
pointer actually requires a second mutex (the header). Could you reasonably
extend the model to deal syntactically with mutex hierarchies? Would the
complacency suggested by reliance on the model prove disastrous in an
application that required hierarchies?
</quote>
Well, to be fair:
http://www.informit.com/isapi/product_id~%7BE3967A89-4E20-425B-BCFF-B84B6DEED6CA%7D/element_id~%7B1872DFB1-6031-4CB0-876D-9533C4A23FC9%7D/st~3FAD3499-20A6-4782-9A96-05825F8E6E5B/content/articlex.asp
(Multithreading and the C++ Type System
FEB 08, 2002 By Andrei Alexandrescu. Article is provided courtesy of Addison Wesley.)
<quote>
An article of mine[4] describes practical compile-time race condition
detection in C++. The method exploits the volatile keyword not as a
semantic vehicle, but only as a participant to the C++ type system.
The programmer qualifies the shared user-defined objects with volatile.
Those objects can be manipulated only by applying a const_cast. Finally,
a helper object can ensure that the const_cast is performed only in
conjunction with locking a synchronization object. Effectively, an
object's type (volatile-qualified or not) depends on whether its
corresponding synchronization object is locked or not. The main
caveat of the technique is that the use of the obscure volatile
qualifier might appear confusing to the unwitting maintainer.
</quote>
4. Andrei Alexandrescu, "volatile: Multithreaded Programmer's Best
Friend," C/C++ Users Journal, February 2001.
regards,
alexander.
tom_usenet
<tere...@web.de> wrote:
>> So, just use sychronisation primitives (such as in the boost.threads,
>> posix or win32 libraries) and your system will guarantee that properly
>> access locked variables work.
>
>STAY AWAY FROM THE CURRENT VERSION OF BOOST.THREADS.
>
>For now, stick to something like http://sources.redhat.com/pthreads-win32,
>"pthreads-etc." and non-portable thinks like IOCP/MS-Win, etc. for "better
>performance and scalability".
Just out of interest, what is wrong with boost.threads, as far as it
is currently implemented? The alternative is that I write my own
synchronisation classes that would look quite similar, I think...
Tom
Alexander Terekhov
tom_usenet wrote:
[...]
> Just out of interest, what is wrong with boost.threads, as far as it
http://groups.google.com/groups?threadm=Cwrs8.216462%24u77.45744811%40news02.optonline.net
(Subject: CUJ/"The Boost.Threads Library" article - feedback/comments?!(*))
http://groups.google.com/groups?threadm=67b13fa49e352543557f1f38646224aa.11102%40mygate.mailgate.org
(Subject: Boost.Threads and Dinkum CoreX)
http://groups.google.com/groups?threadm=3D514E1B.E3CF5716%40web.de
(Subject: Boost.Thread: "Threads & Exceptions"/"Enhanced call_once())
regards,
alexander.
(*) original message was eliminated from google archive
by ``someone'' -- probably on ``copyright'' grounds:
http://groups.google.com/groups?threadm=3CB232E0.DF12F3AD%40acm.org
(Subject: [FYI]Re: CUJ/"The Boost.Threads Library" article - feedback/comments?!)