""Andrei Alexandrescu (See Website for Email)""
<SeeWebsiteForEmail@moderncppdesign.com> wrote in message
> "Peter Dimov" <pdimov@gmail.com> wrote in message
> news:abefd130.0408300553.5b324746@posting.google.com...
> >> void rmw(volatile unsigned* loc, F fun) {
> >>     do {
> >>         volatile unsigned old = *loc;
> >>         volatile unsigned fresh = fun(old);
> >>     } while (!CAS(loc, old, fresh));
> >> }
> >
> > No matter how you define "volatile", 'old' and 'fresh' don't need it.
> >
> > template <class F>
> > void rmw( unsigned volatile * loc, F fun )
> > {
> >    do
> >    {
> >        unsigned old = atomic_read( loc );
> >        unsigned fresh = fun(old);
> >    } while( !CAS(loc, old, fresh) );
> > }
>
> But this is missing the point. All you do is replace a type qualifier with
> what seems to be a function call. But that's not really a regular function
> call - it is a call that the core language knows about: atomic_read is a
> "hard sequence point". In my code, "volatile" implied that. In your code,
> atomic_read implies that. Same thing, different syntax.

If the function does what is suggests, there is a difference. volatile may
mean a sequence point, but atomic means atomic.  that can't fetch some
intermediate value. volatile can.

Let's change the example by replacing 'unsigned' by 'float'. is the top
example safe?  It isn't.   There it is possible to init 'old' with a broken
value, a trap value, an intererminate value that will make it subsequent use
as param to   fun()  undefined behavior.

However if there is a language facility that forces atomic access, it no
longer can happen.

For unsigned I'm not sure what the standard says about bits -- if any bit
pattern is required to work, then it's not UB.  But in real-life situation
that's still can turn to a landmine, if fun() happens to work on only a
subset of values, and expects imput from that set. And the programmer thinks
all that can happen if another thread modifies the value the read will
provide either that or the old value.    While if the access is not atomic,
it is possible to read some mix of values.  (on some architectures possibly
even a completely undefined value or face a bus error.)

AFAIK volatile implies a hard seq point but does not imply atomic access.
And Peter's example did insert that important extra thing.

Paul



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

>Allow me expand on that a little. Even with those there are left many, many
>things that you can't do without dropping to assembler, as I'll show below.
>You suggest the following primitives:
>
>     void atomic_add(volatile unsigned* loc, unsigned incr);
>     unsigned atomic_add_value(volatile unsigned* loc, unsigned incr);
>     void atomic_sub(volatile unsigned* loc, unsigned incr);
>     unsigned atomic_sub_value(volatile unsigned* loc, unsigned incr);
>     void atomic_set(volatile unsigned* loc, unsigned bits);
>     unsigned atomic_set_value(volatile unsigned* loc, unsigned bits);
>     void atomic_clr(volatile unsigned* loc, unsigned bits);
>     unsigned atomic_clr_value(volatile unsigned* loc, unsigned bits);
>     void atomic_toggle(volatile unsigned* loc, unsigned bits);
>     unsigned atomic_toggle_value(volatile unsigned* loc, unsigned bits);
>
>If I understand correctly, they all are "read-modify-write" (RMW)
>operations, consisting of reading a location, applying a function to it, and
>writing it back to the location, all atomically. Let's see what Herlihy has
>proved about RMW operations:
>
>
atomic_set_value is a write only operation and not r/m/w from the looks
of it.

But does Herlihy's conclusion really make the above operations totally
useless ? If I understand correctly
what Herlihy is saying in that paper...
 -  you cant implement more complex functions out of those atomic functions

But in some cases (like incr/dec ref counts) the above operations seem
to suffice. Would that be correct ?
The CAS based implementation seems a lot more in-efficient as compared
to the "native" ones.

The following function

>template <class F>
>void rmw(volatile unsigned* loc, F fun) {
>    do {
>        volatile unsigned old = *loc;
>        volatile unsigned fresh = fun(old);
>    } while (!CAS(loc, old, fresh));
>}
>


 is this really wait-free ? I wonder whats the guarantee that a thread wont
loop forever ?

-Roshan

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

SeeWebsiteForEmail@moderncppdesign.com ("Andrei Alexandrescu (See Website for Email)") wrote in message news:<2pbm1uFj5344U1@uni-berlin.de>...
>
> That not only shows the weakness and incompleteness of the set of primitives
> you suggest, but also the power of CAS, which can be used to implement *all*
> of your primitives. Here they are in one fell swoop:
>
> template <class F>
> void rmw(volatile unsigned* loc, F fun) {
>     do {
>         volatile unsigned old = *loc;
>         volatile unsigned fresh = fun(old);
>     } while (!CAS(loc, old, fresh));
> }
>
> Of course, the code above should be seen as nothing but "pseudocode" because
> we haven't defined the semantics of volatile to mean anything in the context
> of multiple threads.

No matter how you define "volatile", 'old' and 'fresh' don't need it.

template <class F>
void rmw( unsigned volatile * loc, F fun )
{
    do
    {
        unsigned old = atomic_read( loc );
        unsigned fresh = fun(old);
    } while( !CAS(loc, old, fresh) );
}

*loc's volatile qualifier is also cosmetic (so that you can pass the
address of a volatile variable without a cast).

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

SeeWebsiteForEmail@moderncppdesign.com ("Andrei Alexandrescu (See Website for Email)") writes:
[snip]
> That not only shows the weakness and incompleteness of the set of primitives
> you suggest, but also the power of CAS, which can be used to implement *all*
> of your primitives. Here they are in one fell swoop:
>
> template <class F>
> void rmw(volatile unsigned* loc, F fun) {
>     do {
>         volatile unsigned old = *loc;
>         volatile unsigned fresh = fun(old);
>     } while (!CAS(loc, old, fresh));
> }
>
> Of course, the code above should be seen as nothing but "pseudocode" because
> we haven't defined the semantics of volatile to mean anything in the context
> of multiple threads.

And let's please not attept to re-(ab)use volatile for threads; its
    present semantics (whatever they are :-) are AFAICT completely
    unsuitable for MT, and quite poorly specified.

I fear that if C++ tries to re-use volatile for MT, the fog and
    confusion which surrounds volatile will also surround C++
    threading primitives. MT is hard enough without that.

>
> Now you can pass to rmw() functors that increment, decrement, add, subtract,
> multiply, extract base 2 logarithm... you name it, and the code is correct.
>
> But wait, there's more. Herlihy also proved universality results:
>
> <<
> An object is universal if it implements any other object. In this section,
> we show that any object with consensus number n is universal in a system of
> n (or fewer) processes.
>>>
>
>> Compare and swap could certainly be added to that list.
>> Compare-and-swap (which may have to be followed by "back
>> off and retry") has its uses, but isn't the only useful
>> primitive.
>
> Indeed, it's not the only one. It's the one that implements all others :o).
>
>>    As for the "volatile" issue, here's what Linus Torvalds
>> has to say about trying to read the C++ standard and
>> figure out what "volatile" means.
>>
>>    http://gcc.gnu.org/ml/gcc-patches/2001-12/msg01923.html
>
> I certainly enjoyed and agreed with Linus' post. I'd also agree it has about
> zero relevance to our discussion.

The semantics of volatile have nothing to do with threading, as far
    as I can tell, but if you agree with that, why did you apply it
    in your examples?

In any case, I *don't* agree that that thread has 'zero relevance';
    it shows that if MT observable behavior is described in terms of
    lvalues, rvalues, and undefined 'accesses', no-one will ever
    understand what it means, and C++ will be exactly where it is
    now with respect to MT: forget what the standard says, and hope
    your implementor implemented and documented something you can use
    and understand. That's where C++ is with respect to volatile.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

> That not only shows the weakness and incompleteness of the set of primitives
> you suggest, but also the power of CAS, which can be used to implement *all*
> of your primitives. Here they are in one fell swoop:
>
> template <class F>
> void rmw(volatile unsigned* loc, F fun) {
>     do {
>         volatile unsigned old = *loc;
>         volatile unsigned fresh = fun(old);
>     } while (!CAS(loc, old, fresh));
> }
>
> Of course, the code above should be seen as nothing but "pseudocode" because
> we haven't defined the semantics of volatile to mean anything in the context
> of multiple threads.
>
> Now you can pass to rmw() functors that increment, decrement, add, subtract,
> multiply, extract base 2 logarithm... you name it, and the code is correct.
>
> But wait, there's more. Herlihy also proved universality results:
>
> <<
> An object is universal if it implements any other object. In this section,
> we show that any object with consensus number n is universal in a system of
> n (or fewer) processes.
> >>
>
> > Compare and swap could certainly be added to that list.
> > Compare-and-swap (which may have to be followed by "back
> > off and retry") has its uses, but isn't the only useful
> > primitive.
>
> Indeed, it's not the only one. It's the one that implements all others :o).

All thats nice, I guess. But if even the right wait-free/lock-based primitives
are
constructed. that still leaves us the problem surfaced in the DCL article.
The issue about memory coherrency.

 -   That modifying data on a local processor doesn't guarantee anything about
what the other processors see.
 -   The memory subsystem can perform updates in a different order than was done
by the processor

-Roshan

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"llewelly" <llewelly.at@xmission.dot.com> wrote in message
news:86llfwr4x2.fsf@Zorthluthik.local.bar...
> And let's please not attept to re-(ab)use volatile for threads; its
>    present semantics (whatever they are :-) are AFAICT completely
>    unsuitable for MT, and quite poorly specified.

I definitely agree with that.

> The semantics of volatile have nothing to do with threading, as far
>    as I can tell, but if you agree with that, why did you apply it
>    in your examples?

I applied it because it was used (with certain implied semantics) in the
post I replied to. I promise I will try to stay away from it from now on.

> In any case, I *don't* agree that that thread has 'zero relevance';
>    it shows that if MT observable behavior is described in terms of
>    lvalues, rvalues, and undefined 'accesses', no-one will ever
>    understand what it means, and C++ will be exactly where it is
>    now with respect to MT: forget what the standard says, and hope
>    your implementor implemented and documented something you can use
>    and understand. That's where C++ is with respect to volatile.

That's a fair characterization :o).


Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Peter Dimov" <pdimov@gmail.com> wrote in message
news:abefd130.0408300553.5b324746@posting.google.com...
> SeeWebsiteForEmail@moderncppdesign.com ("Andrei Alexandrescu (See Website
> for Email)") wrote in message news:<2pbm1uFj5344U1@uni-berlin.de>...
>> template <class F>
>> void rmw(volatile unsigned* loc, F fun) {
>>     do {
>>         volatile unsigned old = *loc;
>>         volatile unsigned fresh = fun(old);
>>     } while (!CAS(loc, old, fresh));
>> }
>
> No matter how you define "volatile", 'old' and 'fresh' don't need it.
>
> template <class F>
> void rmw( unsigned volatile * loc, F fun )
> {
>    do
>    {
>        unsigned old = atomic_read( loc );
>        unsigned fresh = fun(old);
>    } while( !CAS(loc, old, fresh) );
> }

But this is missing the point. All you do is replace a type qualifier with
what seems to be a function call. But that's not really a regular function
call - it is a call that the core language knows about: atomic_read is a
"hard sequence point". In my code, "volatile" implied that. In your code,
atomic_read implies that. Same thing, different syntax.


Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

SeeWebsiteForEmail@moderncppdesign.com ("Andrei Alexandrescu (See Website for Email)") wrote in message news:<2pjlp5FkveepU1@uni-berlin.de>...
> "Peter Dimov" <pdimov@gmail.com> wrote in message
> news:abefd130.0408300553.5b324746@posting.google.com...
> > SeeWebsiteForEmail@moderncppdesign.com ("Andrei Alexandrescu (See Website
> > for Email)") wrote in message news:<2pbm1uFj5344U1@uni-berlin.de>...
> >> template <class F>
> >> void rmw(volatile unsigned* loc, F fun) {
> >>     do {
> >>         volatile unsigned old = *loc;
> >>         volatile unsigned fresh = fun(old);
> >>     } while (!CAS(loc, old, fresh));
> >> }
> >
> > No matter how you define "volatile", 'old' and 'fresh' don't need it.
> >
> > template <class F>
> > void rmw( unsigned volatile * loc, F fun )
> > {
> >    do
> >    {
> >        unsigned old = atomic_read( loc );
> >        unsigned fresh = fun(old);
> >    } while( !CAS(loc, old, fresh) );
> > }
>
> But this is missing the point. All you do is replace a type qualifier with
> what seems to be a function call. But that's not really a regular function
> call - it is a call that the core language knows about: atomic_read is a
> "hard sequence point". In my code, "volatile" implied that. In your code,
> atomic_read implies that. Same thing, different syntax.

True about the atomic_read. I only used it because I said earlier "no
matter how you define volatile". The code as written above works even
for a no-op volatile. With an appropriate definition, atomic_read( loc
) can be replaced with *loc. The rest of my comment still applies. old
and fresh do not need to be volatile, for any reasonable definition of
volatile.

Actually now that I think about it, depending on the precise semantics
of CAS and if *loc is only modified via rmw, the code may be fine even
without atomic_read _and_ without volatile on *loc. ;-)

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Andrei Alexandrescu (See Website for Email)" wrote:
[...]
> But this is missing the point. All you do is replace a type qualifier with
> what seems to be a function call. But that's not really a regular function
> call - it is a call that the core language knows about: atomic_read is a
> "hard sequence point".

http://www.terekhov.de/pthread_refcount_t/experimental/refcount.cpp

  template<typename min_msync, typename update_msync>
  bool decrement(min_msync mms, update_msync ums) throw() {
    numeric val;
    do {
      val = m_value.load(msync::none);
                         ^^^^^^^^^^^
      assert(min() < val);
      if (min() + 1 == val) {
        m_value.store(min(), mms);
        return false;
      }
    } while (!m_value.attempt_update(val, val - 1, ums));
    return true;
  }

regards,
alexander.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"John Nagle" <nagle@animats.com> wrote in message
news:2BVXc.13220$Sy4.10474@newssvr29.news.prodigy.com...
>    I'm not entirely sure what's going on here.  Andrei seems
> to have latched on to a technique for eliminating spinlocks
> in multiprocessor dispatchers and is trying to generalize it
> into a general theory of multithread programming.  That
> may or may not be a good idea.  But it needs more development.

It does need more development, and I am glad you mentioned that. However, as
far as I know I didn't "latch" on anything, except perhaps rigurous minimal
and complete primitives for concurrency control in C++.

>    Having been around long enough to see concurrent programming
> schemes come and go, I think this one needs to be looked
> at harder.  Remember when LINDA was going to solve all
> our concurrency problems with atomic operations on tuple pools?

I do recall having read a couple papers about LINDA (which IIRC is not
really a language, more like a framework... right?). Did anyone prove
anything about LINDA's capabilities?

> All I'm trying to do is to get some minimal atomic
> operations into the standard.  Without those, there are
> things you can't do without dropping into assembler.

Allow me expand on that a little. Even with those there are left many, many
things that you can't do without dropping to assembler, as I'll show below.
You suggest the following primitives:

     void atomic_add(volatile unsigned* loc, unsigned incr);
     unsigned atomic_add_value(volatile unsigned* loc, unsigned incr);
     void atomic_sub(volatile unsigned* loc, unsigned incr);
     unsigned atomic_sub_value(volatile unsigned* loc, unsigned incr);
     void atomic_set(volatile unsigned* loc, unsigned bits);
     unsigned atomic_set_value(volatile unsigned* loc, unsigned bits);
     void atomic_clr(volatile unsigned* loc, unsigned bits);
     unsigned atomic_clr_value(volatile unsigned* loc, unsigned bits);
     void atomic_toggle(volatile unsigned* loc, unsigned bits);
     unsigned atomic_toggle_value(volatile unsigned* loc, unsigned bits);

If I understand correctly, they all are "read-modify-write" (RMW)
operations, consisting of reading a location, applying a function to it, and
writing it back to the location, all atomically. Let's see what Herlihy has
proved about RMW operations:

<<
THEOREM 4. There is no wait-free solution to three-process consensus using
any combination of read -modify-write operations that apply functions from
an interfering set F.
>>

(We can replace "interfering" with "arbitrary" for simplification.
"Interfering" means functions that can either compose commutatively, or one
overwrites the other.) Then the conclusion is immediate:

<<
It follows that one cannot use any combination of these classical primitives
to construct a wait-free implementation of any object with consensus number
greater than 2.
>>

Consensus number means the maximum number of threads that can access the
object at the same time. A few lines, below. Herlihy proves something else:

<<
THEOREM 5. A compare&swap register has infinite consensus number.
[..]
COROLLARY 3. It is impossible to construct a wait-free implementation of a
compare&swap register from a set of registers that support any combination
of
read, write, test&set, swap, or fetch&add operations in a system of three or
more
processes.
>>

Wow! Now I think it becomes clear why your statement:

>    Many of the things Andrei wants to include can be
> implemented in terms of these primitives.

was answered with:

<<
I am sorry, but the whole argument is wrong, and so is the conclusion. These
are very very weak primitives that cannot be used for much meaningful MT
code.
>>

That not only shows the weakness and incompleteness of the set of primitives
you suggest, but also the power of CAS, which can be used to implement *all*
of your primitives. Here they are in one fell swoop:

template <class F>
void rmw(volatile unsigned* loc, F fun) {
    do {
        volatile unsigned old = *loc;
        volatile unsigned fresh = fun(old);
    } while (!CAS(loc, old, fresh));
}

Of course, the code above should be seen as nothing but "pseudocode" because
we haven't defined the semantics of volatile to mean anything in the context
of multiple threads.

Now you can pass to rmw() functors that increment, decrement, add, subtract,
multiply, extract base 2 logarithm... you name it, and the code is correct.

But wait, there's more. Herlihy also proved universality results:

<<
An object is universal if it implements any other object. In this section,
we show that any object with consensus number n is universal in a system of
n (or fewer) processes.
>>

> Compare and swap could certainly be added to that list.
> Compare-and-swap (which may have to be followed by "back
> off and retry") has its uses, but isn't the only useful
> primitive.

Indeed, it's not the only one. It's the one that implements all others :o).

>    As for the "volatile" issue, here's what Linus Torvalds
> has to say about trying to read the C++ standard and
> figure out what "volatile" means.
>
>    http://gcc.gnu.org/ml/gcc-patches/2001-12/msg01923.html

I certainly enjoyed and agreed with Linus' post. I'd also agree it has about
zero relevance to our discussion.


Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

John Nagle wrote:
>     All I'm trying to do is to get some minimal atomic
> operations into the standard.  Without those, there are
> things you can't do without dropping into assembler.
>
 So what? Real-world C++ applications _do_ use assembler to fight performance
bottlenecks. IMHO these "minimal atomic operations" are _premature_
optimization of C++ MT.

 IMHO we'd better:
1. Make certain changes to the core language to allow for concurrent or
simultaneous execution.
2. Define a _minimal_ portable set of MT-related C++ objects and actions. The
goal is to perform those 20% of work which solves 80% of problems.
3. Carefully design STL MT safety requirements and guarantees.

 I believe the last step requires about 80% of C++ MT efforts while we're
still playing with low-level hardware-dependant bells and whistles...
--
         With all respect, Sergey.               http://ders.angen.net/
         mailto : ders at skeptik.net

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

nagle@animats.com (John Nagle) writes:
[snip]
>     As for the "volatile" issue, here's what Linus Torvalds
> has to say about trying to read the C++ standard and
> figure out what "volatile" means.
>
>     http://gcc.gnu.org/ml/gcc-patches/2001-12/msg01923.html
[snip]

The impression I get from that thread is that volatile is so poorly
    specified in C++ that its only effect is to waste valuable
    implementor resources. The C situation seems little better.

Whatever multi-threading semantics end up in C++, I strongly hope they
    are nothing like volatile, though I'll admit I don't know the
    right approach to specifying them.





---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <2p2e0aFgfd7fU1@uni-berlin.de>, "Andrei Alexandrescu (See
Website for Email)" <SeeWebsiteForEmail@moderncppdesign.com> writes
>Second, I do advise people who are genuinely interested in the issue to
>prepare investing serious time and effort in understanding what's going on,
>and expect very basic beliefs they now hold to be forever shattered.

Thanks for the post. Programmers always have a tendency to over-estimate
their knowledge and understanding of technical issues. MT is one of the
extreme cases. Perhaps it is because it is an area where it is
effectively impossible to learn anything safe and useful by experiment.

It is because you have a great deal of C++ expertise coupled with having
spent time and much mental effort to understand the problems of MT that
I believe that one of the greatest services you could do the C++
community is to write a paper for WG21 proposing those changes to the
C++ core that would allow reliable, portable MT programming to be done.
Obviously good library support is also essential.

At the same time we should be considering other issues raised by the
growing use of multi-processor machines as well as multi-core
processors. Note that those two are not equivalent. It would not be
unusual for each processor to have its own (unshared) memory resources,
but most multi-core architectures that I have looked at assume shared
memory.

Among the things I believe we should be considering are extra modifiers
on function declarations. The most obvious to me is the introduction of
a 'pure' modifier. I suspect that a compile time checkable nothrow would
also be useful.

--
Francis Glassborow      ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
For project ideas and contributions: http://www.spellen.org/youcandoit/projects

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Andrei Alexandrescu (See Website for Email)""
<SeeWebsiteForEmail@moderncppdesign.com> wrote in message
news:2p2e0aFgfd7fU1@uni-berlin.de...

> Then something else happened: I became snooty myself! I mean, whenever
> someone would ask *me* to explain something "simple" wrt memory
reorderings,
> I would just point to some tomes or papers and expect them to acquire the
> appropriate background (which takes its tolls in form of wrinkles and
joints
> that hurt when it rains) before continuing the discussion. Naturally,
people
> would do what I was doing - at best skim the referred article in disbelief
> and ask back more incredulous questions.
>
> So, first I'd like to apologize to our community, because looking back at
my
> own posts I can tell I've been unprecedently harsh and dismissive, even
more
> so than my usual self! :o) Call it "threads understanding syndrome", but
> I've got it, and it's hard to live with it. I will try my best (and I hope
> the true few threading experts that are hanging out here will follow suit)
> to explain things.

Thanks very much for the confession, Andrei. Humility is a rare commodity
in any field, and apparently rarer still among us putative computer
experts. I just hope you can also become more charitable to the C++
committee members, whom you have characterized pretty unkindly in
this thread. (You would have heard more on this subject last week, but
my original posting was so obnoxious itself that the moderators scrubbed
it.)

> Second, I do advise people who are genuinely interested in the issue to
> prepare investing serious time and effort in understanding what's going
on,
> and expect very basic beliefs they now hold to be forever shattered.

Agreed, in spades.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Andrei Alexandrescu (See Website for Email)" wrote:
> ""Edward Diener"" <eldiener@earthlink.net> wrote in message
> news:jIzWc.9990$2L3.7532@newsread3.news.atl.earthlink.net...
>> "Andrei Alexandrescu (See Website for Email)" wrote:
>>> I am sorry, but the whole argument is wrong, and so is the
>>> conclusion. These are very very weak primitives that cannot be used
>>> for much meaningful MT code. See Herlihy's seminal paper that proves
>>> that:
>>>
>>> http://www.podc.org/dijkstra/2003.html
>>
>> The link doesn't point to anything, so I will ask why you think that
>> atomic
>> primitives have no value for MT code.
>
> On my machine, the link points to a page (which I presume you saw)
> that has some introductory text and one link to a paper. The link
> works for me, but only when I connect through the university network.
> That's what made me think it's publically available.
>
> Fortunately, the mentioned paper is freely available online, it just
> takes some googling :o). Here's a link:
>
>
http://citeseer.ist.psu.edu/cache/papers/cs/7628/http:zSzzSzwww.cs.brown.eduzSzcourseszSzcs196azSztoplas.pdf/herlihy93waitfree.pdf
>
>> They certainly seem valuable to me as
>> they will allow values to be changed with the knowledge that no other
>> thread
>> can change the same value in the meantime, and that all other
>> threads will see the new value once it is changed.
>
> "Seem" is key. Herlihy proved that primitives such as atomic
> increment, atomic read/write, or even atomic queues aren't as
> powerful as many thought they are.

Whether they are as valuable as "many thought they are", they hold a basic
value at any rate and I can not see how they would be costly to implement.
So here are some atomic operations which would give the programmer some
control over atomic change of a single value and you say that they have no
value. I say that they have a value even if it is not all that you would
like C++ to do. I am well aware that they do nothing if one has to
synchronize several changes so that other concurrent processing sees these
values as a single completed change. But that is not always necessary in MT
programming.

>
>> How else do you propose to have atomic operations in
>> C++, and if you do not believe that atomic operations are necessary,
>> how do
>> you propose to do MT programming without them ?
>
> I was complaining about what's missing, which makes the mentioned
> collection a random bag of things that "look useful" without anyone
> being able to prove anything relevant about them.

I did "prove" something relevant about them, but you want to say I did not
without disussing the merits of my statements.

> Also, 'volatile' is
> used in those functions' signature just as a cute adornment, without
> any mentioning on what properties are expected from it. Those are
> very important.

One would assume that the properties of "volatile" are explained in the C++
standard. If they are that vague, please explain why, or point me to
something which asserts what you feel is a weakness about it vis-a-vis the
atomic operations suggested.

>
> I'd like to make an "explanatory apology" to the group, and for that
> I'd need to give a little background.
>
> A while ago, after having published "volatile: Multithreaded
> Programmer's best friend", the MT programmer community ripped my
> right leg and beat me to death with it. That was because my article
> had an introduction of the 'volatile' keyword that contained a number
> of gross inaccuracies, the main one being that volatile helps MT
> programming. For the record, the meat of the article still stands,
> but it's a shame it was blurred by some bads in the introduction.
>
>> From what I had seen on public newsgroups, my impression of MT
>> programmers
> was kind of an exclusivistic clique with a superiority complex, and
> the episode with my article strenghtened that impression.
>
> Then I slowly acquired some more understanding of MT programming.
> Nowadays I started the ongoing thread around here, and after having
> posted up and down for a while, I realized something unsettling: that
> I have become snooty, exclusivistic and unkind myself - as much as I
> thoght MT programmers were!
>
> I believe I now know what's happening. (It's a virus.) What's
> happening is that, when starting to talk about MT programming around
> here for example, most of us believe we have a basic understanding of
> what's going on. As such, we are trying to get by by reading the
> posts alone, without going to the extensive documentation (papers,
> articles, books) that those "snooty" MT specialists refer to. We
> believe it is entirely reasonable to figure out what's going on just
> by reading the posts, and we also consider it is fair to ask the
> poster to explain something right then and there, because, hey, we
> know the basics and any new information will add to the basics.
>
> I personally was getting quite irate that MT programmers would not
> care to sit down and explain things to me, and insted direct me to
> some tomes or papers or long threads on comp.programming threads.
> Then something happened to me, in the form of a brick wall which I
> hit when realizing that *nothing* of my cursory knowledge of
> lock-based programming would even start to explain the oddities
> caused by compiler optimizations, memory reorderings, memory barriers
> and the such. It was only then when I realized that I need to destroy
> my entire mental image of threads and build one.
>
> Then something else happened: I became snooty myself! I mean, whenever
> someone would ask *me* to explain something "simple" wrt memory
> reorderings, I would just point to some tomes or papers and expect
> them to acquire the appropriate background (which takes its tolls in
> form of wrinkles and joints that hurt when it rains) before
> continuing the discussion. Naturally, people would do what I was
> doing - at best skim the referred article in disbelief and ask back
> more incredulous questions.
>
> So, first I'd like to apologize to our community, because looking
> back at my own posts I can tell I've been unprecedently harsh and
> dismissive, even more so than my usual self! :o) Call it "threads
> understanding syndrome", but I've got it, and it's hard to live with
> it. I will try my best (and I hope the true few threading experts
> that are hanging out here will follow suit) to explain things.
>
> Second, I do advise people who are genuinely interested in the issue
> to prepare investing serious time and effort in understanding what's
> going on, and expect very basic beliefs they now hold to be forever
> shattered.

This still basically says that you understand things which others do not but
you are not willing to discuss them with others. I do not think this is a
valid way to present proposals on this NG, or to answer others when they
make proposals of their own. If you know something which others do not know
it is up to you to discuss those things with others cogently. Perhaps useful
additions can be made to C++ for mere mortals who want to do simple things
with them, and then the "MT experts" can have their way with their more
complex needs. Unless it is proved to me that the atomic operations
mentioned would not do what I suppose according to the C++ standard, I
certainly see them as valuable in doing what has been suggested. If you tell
me that what has been suggested will achieve very little as far as the more
complex problems of MT programming, and back that up with good arguments, I
can understand that answer even though I may not agree with it. But to argue
the way that you are doing now, which is that only you and "MT experts" know
what is good for the language, is naturally abhorrent to others who feel
that they have knowledge also.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Edward Diener wrote:
> One would assume that the properties of "volatile" are explained in the C++
> standard. If they are that vague, please explain why, or point me to
> something which asserts what you feel is a weakness about it vis-a-vis the
> atomic operations suggested.

The suggested operations didn't explain what the volatile
was for. How would things be different if the arguments
were not pointers to volatile objects?

There have been several discussions on this NG with people
who mistakenly believed that volatile had something to do
with concurrent programming, leading to justifiable suspicion
that this is more of the same.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Andrei Alexandrescu (See Website for Email) wrote:

> "John Nagle" <nagle@animats.com> wrote in message
> news:%dVVc.6523$QJ3.3218@newssvr21.news.prodigy.com...
>
>>  I'd like to suggest that C++ provide these standard
>>"atomic" primitives:
>>
>>    void atomic_add(volatile unsigned* loc, unsigned incr);
>>    unsigned atomic_add_value(volatile unsigned* loc, unsigned incr);
>>    void atomic_sub(volatile unsigned* loc, unsigned incr);
>>    unsigned atomic_sub_value(volatile unsigned* loc, unsigned incr);
>>    void atomic_set(volatile unsigned* loc, unsigned bits);
>>    unsigned atomic_set_value(volatile unsigned* loc, unsigned bits);
>>    void atomic_clr(volatile unsigned* loc, unsigned bits);
>>    unsigned atomic_clr_value(volatile unsigned* loc, unsigned bits);
>>    void atomic_toggle(volatile unsigned* loc, unsigned bits);
>>    unsigned atomic_toggle_value(volatile unsigned* loc, unsigned bits);
>
> [snip discussion]
>
>>   Many of the things Andrei wants to include can be
>>implemented in terms of these primitives.
>
>
> I am sorry, but the whole argument is wrong, and so is the conclusion. These
> are very very weak primitives that cannot be used for much meaningful MT
> code. See Herlihy's seminal paper that proves that:
>
> http://www.podc.org/dijkstra/2003.html
>
> Andrei

    That's a somewhat specialized technique used for multiprocessor
compute-bound jobs where any thread can advance the computation.
It's not particularly relevant to programs where each thread
has a distinct role.  The latter are more common, especially
in I/O bound programs.

    It's a useful technique for eliminating
spinlocks in multiprocessor CPU schedulers, but it rarely
appears in production user programs.  It
should not dominate the design of a general purpose
language.

    I could see adding an atomic compare-and-swap operation to
the above list, since it is easily implementable on many
popular CPUs today.

    We need the minimal atomic primitives in C++.  The
fancy stuff we can leave to Boost.

    John Nagle
    Animats

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"John Nagle" <nagle@animats.com> wrote in message
news:FI3Xc.8052$QJ3.6891@newssvr21.news.prodigy.com...
> Andrei Alexandrescu (See Website for Email) wrote:
>
>> "John Nagle" <nagle@animats.com> wrote in message
>> news:%dVVc.6523$QJ3.3218@newssvr21.news.prodigy.com...
>>
>>>  I'd like to suggest that C++ provide these standard
>>>"atomic" primitives:
>>>
>>>    void atomic_add(volatile unsigned* loc, unsigned incr);
>>>    unsigned atomic_add_value(volatile unsigned* loc, unsigned incr);
>>>    void atomic_sub(volatile unsigned* loc, unsigned incr);
>>>    unsigned atomic_sub_value(volatile unsigned* loc, unsigned incr);
>>>    void atomic_set(volatile unsigned* loc, unsigned bits);
>>>    unsigned atomic_set_value(volatile unsigned* loc, unsigned bits);
>>>    void atomic_clr(volatile unsigned* loc, unsigned bits);
>>>    unsigned atomic_clr_value(volatile unsigned* loc, unsigned bits);
>>>    void atomic_toggle(volatile unsigned* loc, unsigned bits);
>>>    unsigned atomic_toggle_value(volatile unsigned* loc, unsigned bits);

>    That's a somewhat specialized technique used for multiprocessor
> compute-bound jobs where any thread can advance the computation.
> It's not particularly relevant to programs where each thread
> has a distinct role.  The latter are more common, especially
> in I/O bound programs.

It is very relevant in the sense that all of the primitives above can be
implemented with CAS, while CAS cannot be implemented by them. Actually,
very little meaningful synchronization can be done with them.

>    We need the minimal atomic primitives in C++.  The
> fancy stuff we can leave to Boost.

I posted that URL in an attempt to explain that the "minimal atomic
primitives" you mention can't do much, as per Herlihy's impossibility
result. They are not useful, which once more illustrates the challenge in
selecting a set of primitives that's at the same time minimal and
meaningful.


Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Edward Diener"" <eldiener@earthlink.net> wrote in message
news:jIzWc.9990$2L3.7532@newsread3.news.atl.earthlink.net...
> "Andrei Alexandrescu (See Website for Email)" wrote:
>> I am sorry, but the whole argument is wrong, and so is the
>> conclusion. These are very very weak primitives that cannot be used
>> for much meaningful MT code. See Herlihy's seminal paper that proves
>> that:
>>
>> http://www.podc.org/dijkstra/2003.html
>
> The link doesn't point to anything, so I will ask why you think that
> atomic
> primitives have no value for MT code.

On my machine, the link points to a page (which I presume you saw) that has
some introductory text and one link to a paper. The link works for me, but
only when I connect through the university network. That's what made me
think it's publically available.

Fortunately, the mentioned paper is freely available online, it just takes
some googling :o). Here's a link:

http://citeseer.ist.psu.edu/cache/papers/cs/7628/http:zSzzSzwww.cs.brown.eduzSzcourseszSzcs196azSztoplas.pdf/herlihy93waitfree.pdf

> They certainly seem valuable to me as
> they will allow values to be changed with the knowledge that no other
> thread
> can change the same value in the meantime, and that all other threads will
> see the new value once it is changed.

"Seem" is key. Herlihy proved that primitives such as atomic increment,
atomic read/write, or even atomic queues aren't as powerful as many thought
they are.

> How else do you propose to have atomic operations in
> C++, and if you do not believe that atomic operations are necessary, how
> do
> you propose to do MT programming without them ?

I was complaining about what's missing, which makes the mentioned collection
a random bag of things that "look useful" without anyone being able to prove
anything relevant about them. Also, 'volatile' is used in those functions'
signature just as a cute adornment, without any mentioning on what
properties are expected from it. Those are very important.

I'd like to make an "explanatory apology" to the group, and for that I'd
need to give a little background.

A while ago, after having published "volatile: Multithreaded Programmer's
best friend", the MT programmer community ripped my right leg and beat me to
death with it. That was because my article had an introduction of the
'volatile' keyword that contained a number of gross inaccuracies, the main
one being that volatile helps MT programming. For the record, the meat of
the article still stands, but it's a shame it was blurred by some bads in
the introduction.

>From what I had seen on public newsgroups, my impression of MT programmers
was kind of an exclusivistic clique with a superiority complex, and the
episode with my article strenghtened that impression.

Then I slowly acquired some more understanding of MT programming. Nowadays I
started the ongoing thread around here, and after having posted up and down
for a while, I realized something unsettling: that I have become snooty,
exclusivistic and unkind myself - as much as I thoght MT programmers were!

I believe I now know what's happening. (It's a virus.) What's happening is
that, when starting to talk about MT programming around here for example,
most of us believe we have a basic understanding of what's going on. As
such, we are trying to get by by reading the posts alone, without going to
the extensive documentation (papers, articles, books) that those "snooty" MT
specialists refer to. We believe it is entirely reasonable to figure out
what's going on just by reading the posts, and we also consider it is fair
to ask the poster to explain something right then and there, because, hey,
we know the basics and any new information will add to the basics.

I personally was getting quite irate that MT programmers would not care to
sit down and explain things to me, and insted direct me to some tomes or
papers or long threads on comp.programming threads. Then something happened
to me, in the form of a brick wall which I hit when realizing that *nothing*
of my cursory knowledge of lock-based programming would even start to
explain the oddities caused by compiler optimizations, memory reorderings,
memory barriers and the such. It was only then when I realized that I need
to destroy my entire mental image of threads and build one.

Then something else happened: I became snooty myself! I mean, whenever
someone would ask *me* to explain something "simple" wrt memory reorderings,
I would just point to some tomes or papers and expect them to acquire the
appropriate background (which takes its tolls in form of wrinkles and joints
that hurt when it rains) before continuing the discussion. Naturally, people
would do what I was doing - at best skim the referred article in disbelief
and ask back more incredulous questions.

So, first I'd like to apologize to our community, because looking back at my
own posts I can tell I've been unprecedently harsh and dismissive, even more
so than my usual self! :o) Call it "threads understanding syndrome", but
I've got it, and it's hard to live with it. I will try my best (and I hope
the true few threading experts that are hanging out here will follow suit)
to explain things.

Second, I do advise people who are genuinely interested in the issue to
prepare investing serious time and effort in understanding what's going on,
and expect very basic beliefs they now hold to be forever shattered.


Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

eldiener@earthlink.net ("Edward Diener") writes:

>> Second, I do advise people who are genuinely interested in the issue
>> to prepare investing serious time and effort in understanding what's
>> going on, and expect very basic beliefs they now hold to be forever
>> shattered.
>
> This still basically says that you understand things which others do
> not but you are not willing to discuss them with others.

Hasn't Andrei already invested significant effort in such discussion?

> I do not think this is a valid way to present proposals on this NG,
> or to answer others when they make proposals of their own. If you
> know something which others do not know it is up to you to discuss
> those things with others cogently.

I think it would have been entirely reasonable for Andrei to say,

   "This is a big topic; so-and-so is the real expert on this issue;
   (s)he wrote a paper that explains it much better than I could, so
   I'm not going to do it the injustice of a half-baked explanation
   here."

But no, Andrei said

  "I will try my best (and I hope the true few threading experts
   that are hanging out here will follow suit) to explain things."

which seems more than generous to me.

> Perhaps useful additions can be made to C++ for mere mortals who
> want to do simple things with them, and then the "MT experts" can
> have their way with their more complex needs. Unless it is proved to
> me that the atomic operations mentioned would not do what I suppose
> according to the C++ standard, I certainly see them as valuable in
> doing what has been suggested. If you tell me that what has been
> suggested will achieve very little as far as the more complex
> problems of MT programming, and back that up with good arguments, I
> can understand that answer even though I may not agree with it.

Andrei didn't say that your atomic primitives were completely
useless.  He was just saying that without some fundamental changes to
the C++ memory model, *no* synchronization facilities can be used
reliably and portably.  Anything you build on an unstable foundation
is likely to collapse.

> But to argue the way that you are doing now, which is that only you
> and "MT experts" know what is good for the language

It's wrong to accuse him of saying anything like that.

> is naturally abhorrent to others who feel that they have knowledge
> also.

Being asked to consider that your "very basic beliefs" might be wrong
is always threatening.  Being able to accept that challenge is
neccessary to advancing knowledge.

--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Hyman Rosen wrote:
> Edward Diener wrote:
>> One would assume that the properties of "volatile" are explained in
>> the C++ standard. If they are that vague, please explain why, or
>> point me to something which asserts what you feel is a weakness
>> about it vis-a-vis the atomic operations suggested.
>
> The suggested operations didn't explain what the volatile
> was for. How would things be different if the arguments
> were not pointers to volatile objects?
>
> There have been several discussions on this NG with people
> who mistakenly believed that volatile had something to do
> with concurrent programming, leading to justifiable suspicion
> that this is more of the same.

This is clouding the issue of whether the atomic operations have any value
or not. I do not care whether volatile is required or not as long as the
syntax signals to the compiler that a CPU's atomic instruction(s) must be
used to make the change and that the change can not be reordered from one
thread of execution to another. Clearly this is a starting point for
discussion but is no reason for rejection of the idea to add syntax in C++
for atomic operations.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

""Edward Diener"" <eldiener@earthlink.net> wrote in message
news:HktXc.4826$Y%3.1612@newsread2.news.atl.earthlink.net...
> "Andrei Alexandrescu (See Website for Email)" wrote:
>> I was complaining about what's missing, which makes the mentioned
>> collection a random bag of things that "look useful" without anyone
>> being able to prove anything relevant about them.
>
> I did "prove" something relevant about them, but you want to say I did not
> without disussing the merits of my statements.

I don't know. All I'm saying is that Herlihy proved mathematically that the
mentioned primitives cannot synchronize more than two threads. I also want
so say that, if we want to add threading primitives to the standard, the "by
ear" approach in which people suggest primitives that seem good is not
satisfactory. We need something more rigurous than that. Sure, those are
good to have, but not a complete set. I'm not sure why half a dozen function
became such a point of contention.

>> Also, 'volatile' is
>> used in those functions' signature just as a cute adornment, without
>> any mentioning on what properties are expected from it. Those are
>> very important.
>
> One would assume that the properties of "volatile" are explained in the
> C++
> standard. If they are that vague, please explain why, or point me to
> something which asserts what you feel is a weakness about it vis-a-vis the
> atomic operations suggested.

Sure. First, I have to say that I am a bit hurt that this post took some
time to reply in quite rough terms to my apology, when that time could have
been much better invested in simply searching the Standard for "volatile" or
"observable behavior". I mean, that is the due dilligence that I advocated
as very necessary, and now I am replying to a post that not only shows no
due diligence took place, but also scolds me for "not willing to discuss
them with others." (That hurts even more; honestly I find it a tad
offensive. I've layed all my cards on the table. I took long times to
compose these posts, all of which contain information that is available
elsewhere. I also sent detailed references to all of the work that I am
familiar with and that formed my current understanding of threads. I've also
offered and sent about a dozen of copies of my upcoming article to anyone
who asked for it, thus formally breaking my contract with CUJ.)

Now on to "volatile". There is nothing that "one would assume". We go an
look in the standard to see what is going on. Next thing would be that I
actually go look, which please allow me to do.

First literal occurence of the word "volatile" is 1.9/6: "The observable
behavior of the abstract machine is its sequence of reads and writes to
volatile data and calls to library I/O functions".

Right off the bat, there are two problems with that:

1) Implicitly there is only one thread, so there is no guarantee that the
observable behavior, namely the sequence of volatile data access, will be
the same in *all* threads.

2) But let's assume we fix 1 to say the order is the same in all threads.
But now there is no guarantee about the /relative/ ordering of accesses
among volatile and non-volatile data. This would lead us to concluding that,
assuming we fix point 1, all data accessed by more than one thread must be
volatile. But hey, that's not how we're used to work. We are used to work
with locking a synchronization object, and then use liberally data that's
nicely protected by that synchronization object. The data is not volatile.

[snipoletto]
> This still basically says that you understand things which others do not
> but
> you are not willing to discuss them with others.

Again, I strongly disagree with such a representation. What I basically said
is that I promised to "inline" more context than I did. And I also made an
appeal for due diligence on the part of people involved in the discussion.

> I do not think this is a
> valid way to present proposals on this NG, or to answer others when they
> make proposals of their own. If you know something which others do not
> know
> it is up to you to discuss those things with others cogently.

I do not understand where this comes from. I answered to half a dozen of
primitives saying they are not enough, and posted a reference to a paper
that proves it beyond doubt. I definitely could have been more delicate in
the choice of words. But as far as cogency goes, I think my stuff was
together.

If I'm allowed a sort of a retort, it's funny this post mentioned the
"volatile" keyword again. A few days ago, I have taken an hour to write a
long post explaining with quotes from the C++ Standard what the relationship
between observable behavior, volatile variables, and threads. I think (hope)
that that post was "standalone" enough. But now this post brings the fresh
issue once again, which suggests that post hasn't been even read!

> Perhaps useful
> additions can be made to C++ for mere mortals who want to do simple things
> with them, and then the "MT experts" can have their way with their more
> complex needs. Unless it is proved to me that the atomic operations
> mentioned would not do what I suppose according to the C++ standard, I
> certainly see them as valuable in doing what has been suggested. If you
> tell
> me that what has been suggested will achieve very little as far as the
> more
> complex problems of MT programming, and back that up with good arguments,
> I
> can understand that answer even though I may not agree with it. But to
> argue
> the way that you are doing now, which is that only you and "MT experts"
> know
> what is good for the language, is naturally abhorrent to others who feel
> that they have knowledge also.

I did not say so. At all. This is really... ick.


Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

eldiener@earthlink.net ("Edward Diener") wrote in message news:<HktXc.4826$Y%3.1612@newsread2.news.atl.earthlink.net>...
> "Andrei Alexandrescu (See Website for Email)" wrote:
> >
> > "Seem" is key. Herlihy proved that primitives such as atomic
> > increment, atomic read/write, or even atomic queues aren't as
> > powerful as many thought they are.
>
> Whether they are as valuable as "many thought they are", they hold a basic
> value at any rate and I can not see how they would be costly to implement.
> So here are some atomic operations which would give the programmer some
> control over atomic change of a single value and you say that they have no
> value.

I don't see where Andrei claimed that atomic_increment et al "have no
value".

> I say that they have a value even if it is not all that you would
> like C++ to do. I am well aware that they do nothing if one has to
> synchronize several changes so that other concurrent processing sees these
> values as a single completed change. But that is not always necessary in MT
> programming.

It is necessary more often than you would think. Let me give you an
example (Alexander Terekhov enlightened me with it a while ago).
Consider a textbook reference counting implementation based on
atomic_increment and atomic_decrement:

counted_ptr<X> p1( new X ), p2( p1 );

// thread 1

p1->f(); // writes to *p1, which is also *p2
p1.reset();

// thread 2

p2.reset(); // implicit p2->~X();

There is no guarantee that ~X in thread 2 will see the changes to *p2
made by X::f() in thread 1.

> [...] Perhaps useful
> additions can be made to C++ for mere mortals who want to do simple things
> with them, and then the "MT experts" can have their way with their more
> complex needs.

It is the other way around. The primitives proposed by "mere mortals"
are very hard to use correctly by non-"MT experts". At the same time
they don't have the expressive power usually implied by the term
"primitive".

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

    I'm not entirely sure what's going on here.  Andrei seems
to have latched on to a technique for eliminating spinlocks
in multiprocessor dispatchers and is trying to generalize it
into a general theory of multithread programming.  That
may or may not be a good idea.  But it needs more development.

    Having been around long enough to see concurrent programming
schemes come and go, I think this one needs to be looked
at harder.  Remember when LINDA was going to solve all
our concurrency problems with atomic operations on tuple pools?

    All I'm trying to do is to get some minimal atomic
operations into the standard.  Without those, there are
things you can't do without dropping into assembler.

Compare and swap could certainly be added to that list.
Compare-and-swap (which may have to be followed by "back
off and retry") has its uses, but isn't the only useful
primitive.  It's actually more useful for non-shared-memory
messaging systems.  FireWire devices offer atomic compare
and swap over the network, (it may be called a "bus", but
it's really a packet-based LAN underneath) which is how
they allocate some resources.

    As for the "volatile" issue, here's what Linus Torvalds
has to say about trying to read the C++ standard and
figure out what "volatile" means.

    http://gcc.gnu.org/ml/gcc-patches/2001-12/msg01923.html

   John Nagle
   Animats

P.J. Plauger wrote:

> ""Andrei Alexandrescu (See Website for Email)""
> <SeeWebsiteForEmail@moderncppdesign.com> wrote in message
> news:2p2e0aFgfd7fU1@uni-berlin.de...
>
>
>>Then something else happened: I became snooty myself! I mean, whenever
>>someone would ask *me* to explain something "simple" wrt memory
>
> reorderings,

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"John Nagle" <nagle@animats.com> wrote in message
news:%dVVc.6523$QJ3.3218@newssvr21.news.prodigy.com...
>   I'd like to suggest that C++ provide these standard
> "atomic" primitives:
>
>     void atomic_add(volatile unsigned* loc, unsigned incr);
>     unsigned atomic_add_value(volatile unsigned* loc, unsigned incr);
>     void atomic_sub(volatile unsigned* loc, unsigned incr);
>     unsigned atomic_sub_value(volatile unsigned* loc, unsigned incr);
>     void atomic_set(volatile unsigned* loc, unsigned bits);
>     unsigned atomic_set_value(volatile unsigned* loc, unsigned bits);
>     void atomic_clr(volatile unsigned* loc, unsigned bits);
>     unsigned atomic_clr_value(volatile unsigned* loc, unsigned bits);
>     void atomic_toggle(volatile unsigned* loc, unsigned bits);
>     unsigned atomic_toggle_value(volatile unsigned* loc, unsigned bits);
[snip discussion]
>    Many of the things Andrei wants to include can be
> implemented in terms of these primitives.

I am sorry, but the whole argument is wrong, and so is the conclusion. These
are very very weak primitives that cannot be used for much meaningful MT
code. See Herlihy's seminal paper that proves that:

http://www.podc.org/dijkstra/2003.html

Andrei


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Andrei Alexandrescu (See Website for Email)" wrote:
> "John Nagle" <nagle@animats.com> wrote in message
> news:%dVVc.6523$QJ3.3218@newssvr21.news.prodigy.com...
>>   I'd like to suggest that C++ provide these standard
>> "atomic" primitives:
>>
>>     void atomic_add(volatile unsigned* loc, unsigned incr);
>>     unsigned atomic_add_value(volatile unsigned* loc, unsigned incr);
>>     void atomic_sub(volatile unsigned* loc, unsigned incr);
>>     unsigned atomic_sub_value(volatile unsigned* loc, unsigned incr);
>>     void atomic_set(volatile unsigned* loc, unsigned bits);
>>     unsigned atomic_set_value(volatile unsigned* loc, unsigned bits);
>>     void atomic_clr(volatile unsigned* loc, unsigned bits);
>>     unsigned atomic_clr_value(volatile unsigned* loc, unsigned bits);
>>     void atomic_toggle(volatile unsigned* loc, unsigned bits);
>>     unsigned atomic_toggle_value(volatile unsigned* loc, unsigned
>>    bits); [snip discussion] Many of the things Andrei wants to
>> include can be
>> implemented in terms of these primitives.
>
> I am sorry, but the whole argument is wrong, and so is the
> conclusion. These are very very weak primitives that cannot be used
> for much meaningful MT code. See Herlihy's seminal paper that proves
> that:
>
> http://www.podc.org/dijkstra/2003.html

The link doesn't point to anything, so I will ask why you think that atomic
primitives have no value for MT code. They certainly seem valuable to me as
they will allow values to be changed with the knowledge that no other thread
can change the same value in the meantime, and that all other threads will
see the new value once it is changed. To me they are a start to at least a
basic level of MT code. How else do you propose to have atomic operations in
C++, and if you do not believe that atomic operations are necessary, how do
you propose to do MT programming without them ?

>
> Andrei
>
>
> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting
> with ] [ your news-reader.  If that fails, use
> mailto:std-c++@ncar.ucar.edu    ] [              --- Please see the
> FAQ before posting. ---               ] [ FAQ:
> http://www.jamesd.demon.co.uk/csc/faq.html                       ]

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Edward Diener wrote:

> John Nagle wrote:
>
>>   I'd like to suggest that C++ provide these standard
>>"atomic" primitives:
>>
>>     void atomic_add(volatile unsigned* loc, unsigned incr);
>>     unsigned atomic_add_value(volatile unsigned* loc, unsigned incr);
>>     void atomic_sub(volatile unsigned* loc, unsigned incr);
>>     unsigned atomic_sub_value(volatile unsigned* loc, unsigned incr);
>>     void atomic_set(volatile unsigned* loc, unsigned bits);
>>     unsigned atomic_set_value(volatile unsigned* loc, unsigned bits);
>>     void atomic_clr(volatile unsigned* loc, unsigned bits);
>>     unsigned atomic_clr_value(volatile unsigned* loc, unsigned bits);
>>     void atomic_toggle(volatile unsigned* loc, unsigned bits);
>>     unsigned atomic_toggle_value(volatile unsigned* loc, unsigned
>>bits);
>>snipped...
>
>
> Bravo ! A small nit is that if there are CPUs which do not support any of
> these primitives, a conforming compiler for that particular CPU must at
> least issue a warning if any of these are used. Then on that CPU, using the
> primitive is still valid but does not guaramtee atomicity.

     Which ones?  Those primitives have been implemented for QNX
on x86, ARM, PowerPC, MIPS, and SH4.  The only place where
there's likely to be trouble is in exotic multiprocessors with
weak cache semantics.  But few of those were ever made and fewer
are still running.  SPARC machines and the current SGI
shared-memory multiprocessors have hardware cache synchronization
and barriers, so they can do it.  Can you name a CPU in
current production which supports C++ but cannot support
these primitives?

    John Nagle
    Animats

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

John Nagle wrote:
> Edward Diener wrote:
>
>> John Nagle wrote:
>>
>>>   I'd like to suggest that C++ provide these standard
>>> "atomic" primitives:
>>>
>>>     void atomic_add(volatile unsigned* loc, unsigned incr);
>>>     unsigned atomic_add_value(volatile unsigned* loc, unsigned
>>>     incr); void atomic_sub(volatile unsigned* loc, unsigned incr);
>>>     unsigned atomic_sub_value(volatile unsigned* loc, unsigned
>>>     incr); void atomic_set(volatile unsigned* loc, unsigned bits);
>>>     unsigned atomic_set_value(volatile unsigned* loc, unsigned
>>>     bits); void atomic_clr(volatile unsigned* loc, unsigned bits);
>>>     unsigned atomic_clr_value(volatile unsigned* loc, unsigned
>>>     bits); void atomic_toggle(volatile unsigned* loc, unsigned
>>>     bits); unsigned atomic_toggle_value(volatile unsigned* loc,
>>> unsigned
>>> bits);
>>> snipped...
>>
>>
>> Bravo ! A small nit is that if there are CPUs which do not support
>> any of these primitives, a conforming compiler for that particular
>> CPU must at least issue a warning if any of these are used. Then on
>> that CPU, using the primitive is still valid but does not guaramtee
>> atomicity.
>
>      Which ones?  Those primitives have been implemented for QNX
> on x86, ARM, PowerPC, MIPS, and SH4.  The only place where
> there's likely to be trouble is in exotic multiprocessors with
> weak cache semantics.  But few of those were ever made and fewer
> are still running.  SPARC machines and the current SGI
> shared-memory multiprocessors have hardware cache synchronization
> and barriers, so they can do it.  Can you name a CPU in
> current production which supports C++ but cannot support
> these primitives?

No. But my suggestion is simply that if one exists and the programmer is
writing code for it which uses one of the primitives which are not
supported, he needs to be warned about it. If absolutely all processors for
which a C++ compiler are written support all of the primitives then there is
nothing to worry about. Even if there are a few processors which do not
support all of the primitives that is no reason why C++ should not have
them, and I fully support your proposal.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

   I'd like to suggest that C++ provide these standard
"atomic" primitives:

     void atomic_add(volatile unsigned* loc, unsigned incr);
     unsigned atomic_add_value(volatile unsigned* loc, unsigned incr);
     void atomic_sub(volatile unsigned* loc, unsigned incr);
     unsigned atomic_sub_value(volatile unsigned* loc, unsigned incr);
     void atomic_set(volatile unsigned* loc, unsigned bits);
     unsigned atomic_set_value(volatile unsigned* loc, unsigned bits);
     void atomic_clr(volatile unsigned* loc, unsigned bits);
     unsigned atomic_clr_value(volatile unsigned* loc, unsigned bits);
     void atomic_toggle(volatile unsigned* loc, unsigned bits);
     unsigned atomic_toggle_value(volatile unsigned* loc, unsigned bits);

Discussion:

    These primitives cannot be written in C++ as it exists, because
the language currently has no notion of atomicity across thread
boundaries.  So they are proper primitives.  They generally
need to be implemented in assembler or in the compiler, because
they may require the use of instructions that are not normally
emitted.

    These primitives do not require operating system support, so
they are proper language primitives.  There's no need to defer
to POSIX for these.

    They are well established primitives, with a history all
the way back to Djykstra's work in the late 1960s and early
1970s. They're known to be sufficient to implement the non
blocking part of mutexes and useful non-blocking primitives
such as circular buffers.  They have a strong history in
reliable production systems.  This particular set of primitives
is the basis of synchronization in QNX.  Linux has a similar
set, although they are usually used only in the kernel.  The
BeOS has most of these primitives available to user programs.
There's a good track record here.

    Efficient implementations for these primitives exist
for most, if not all, CPU architectures. Even the little
machines, like the ARM, can support these primitives.

    Many of the things Andrei wants to include can be
implemented in terms of these primitives.

    These seem a low-risk set of primitives to provide.
Without them, you can't do atomic operations without
dropping into assembler or making system calls.  With
them, you can build most other non-blocking primitives.

    John Nagle
    Animats



---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

John Nagle wrote:
>    I'd like to suggest that C++ provide these standard
> "atomic" primitives:
>
>      void atomic_add(volatile unsigned* loc, unsigned incr);
>      unsigned atomic_add_value(volatile unsigned* loc, unsigned incr);
>      void atomic_sub(volatile unsigned* loc, unsigned incr);
>      unsigned atomic_sub_value(volatile unsigned* loc, unsigned incr);
>      void atomic_set(volatile unsigned* loc, unsigned bits);
>      unsigned atomic_set_value(volatile unsigned* loc, unsigned bits);
>      void atomic_clr(volatile unsigned* loc, unsigned bits);
>      unsigned atomic_clr_value(volatile unsigned* loc, unsigned bits);
>      void atomic_toggle(volatile unsigned* loc, unsigned bits);
>      unsigned atomic_toggle_value(volatile unsigned* loc, unsigned
> bits);
> snipped...

Bravo ! A small nit is that if there are CPUs which do not support any of
these primitives, a conforming compiler for that particular CPU must at
least issue a warning if any of these are used. Then on that CPU, using the
primitive is still valid but does not guaramtee atomicity.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]