There has been a fair amount of discussion about a memory model for
C++, paralleling that for Java in JSR-166. In particular, see:
  Memory model for multithreaded C++: Issues
  Document Number: WG21/N1777=J16/05-0037
  Date: 2005-03-04
and also notes from Hans Boehm at:
http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/.

  There is some recent discussion of this on
"comp.lang.c++.moderated" under the topic "Memory Models."  The
moderator there has suggested that the topic might be more on topic for
this newsgroup.

  The suggested approach here is based on the premise that a
generalized "compare-and-swap" is an appropriate abstraction for
both the compiler and the human reader for specifying, optimizing and
reasoning about synchronization of memory accesses for most
applications, and that this abstraction is sufficient, but not
necessary, basis for a C++ Memory Model.  The generalization envisioned
can, where necessary, internally use basic lock-free programming
techniques to expand on direct hardware techniques for extended byte
length operands and for atomic changes to multiple locations.

   C++ language support is suggested in terms of update operations for
"synchronization elements" that could be specified with syntax such
as:
  old  =? current : new // swap new for old, if
                         //   old is current;
                         // otherwise, assign
                         //   current to old
Typical usage would then be:
  old = current ;
  do {
          - - -
  } while ( old =? current : new )  ;

    This provides a generalized "compare-and-swap" capability that,
depending on the byte length of the synchronization element, can be
directly supported on some processors. Others can use a basic lock or
lock-free algorithm to provide the capability.

Additional atomic operations might be specified as:
// atomic add of suitable integer types
   integerValue  +=? oldInteger : integerIncrement
// general integer operation
   integerValue  op=? oldInteger : integerOperand
// atomic increment
   ++ integerValue  ? oldInteger
// to test read consistency
//   (for transactions, below)
   newValue      ==? oldValue
// conditional CAS
   updateValue   =? oldValue : newValue : predicate

  For a limited form of transaction support (either all or none of a
set of changes occur) multiple updates are specified with an extension
of the above syntax.  For instance, insertion of a new element into a
doubly linked list between a previous and a next element, might be
specified with:
    SynchronizationElement<ElementPointer>
        new, previous, next;
    // Note: ElementPointer provides for ABA reuse
    //   protection and exposes the referenced
    //   element memory location.
    new = - - -         // build new element
    do {
         - - -          // find insertion point
         new.prev = previous ;
         new.next = next     ;
    } while ( previous.next   =? next    : new &&
              next.prev       =? previous: new    )

 This model is based on synchronization of a set of data changes.  It
is complementary to other approaches, such as the Java model, that are
based on capturing an ordered sequence of critical memory updates, with
appropriate regard for synchronizing relations including
"is-sequenced-before", "is-ordered-before", "depends on"
and "communicates with". Advantages claimed include:

*  It specifies succinctly and completely in the code what data needs
to be synchronized and when.
*  This can lead to faster "memory barriers" on processors where
only the relevant cache data needs to be flushed, invalidated, or
synchronized.
*  It can be supported on many processors with well known
"lock-free" techniques.
*  It is essentially portable.
*  It provides a level of abstraction that appears considerably easier
to code to and to reason about for correctness.

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

billclare3@aol.com wrote:
>   There has been a fair amount of discussion about a memory model for
> C++, paralleling that for Java in JSR-166. In particular, see:
>   Memory model for multithreaded C++: Issues
>   Document Number: WG21/N1777=J16/05-0037
>   Date: 2005-03-04
> and also notes from Hans Boehm at:
> http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/.
>
>   There is some recent discussion of this on
> "comp.lang.c++.moderated" under the topic "Memory Models."  The
> moderator there has suggested that the topic might be more on topic for
> this newsgroup.
>
>   The suggested approach here is based on the premise that a
> generalized "compare-and-swap" is an appropriate abstraction

    Note that the "suggested approach here" is that of billclare3@aol.com,
not Hans Boehm.  Boehm's paper does not mention compare and swap.

    John Nagle

---
[ 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.comeaucomputing.com/csc/faq.html                      ]

billclare3@aol.com wrote:
>   There has been a fair amount of discussion about a memory model for
> C++, paralleling that for Java in JSR-166. In particular, see:
>   Memory model for multithreaded C++: Issues
>   Document Number: WG21/N1777=J16/05-0037
>   Date: 2005-03-04
> and also notes from Hans Boehm at:
> http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/.
>
>   There is some recent discussion of this on
> "comp.lang.c++.moderated" under the topic "Memory Models."  The
> moderator there has suggested that the topic might be more on topic for
> this newsgroup.
>
>   The suggested approach here is based on the premise that a
> generalized "compare-and-swap" is an appropriate abstraction for
> both the compiler and the human reader for specifying, optimizing and
> reasoning about synchronization of memory accesses for most
> applications, and that this abstraction is sufficient, but not
> necessary, basis for a C++ Memory Model.  The generalization envisioned
> can, where necessary, internally use basic lock-free programming
> techniques to expand on direct hardware techniques for extended byte
> length operands and for atomic changes to multiple locations.
>
>    C++ language support is suggested in terms of update operations for
> "synchronization elements" that could be specified with syntax such
> as:
>   old  =? current : new // swap new for old, if
>                          //   old is current;
>                          // otherwise, assign
>                          //   current to old
> Typical usage would then be:
>   old = current ;
>   do {
>           - - -
>   } while ( old =? current : new )  ;
>
>     This provides a generalized "compare-and-swap" capability that,
> depending on the byte length of the synchronization element, can be
> directly supported on some processors. Others can use a basic lock or
> lock-free algorithm to provide the capability.
>
> Additional atomic operations might be specified as:
> // atomic add of suitable integer types
>    integerValue  +=? oldInteger : integerIncrement
> // general integer operation
>    integerValue  op=? oldInteger : integerOperand
> // atomic increment
>    ++ integerValue  ? oldInteger
> // to test read consistency
> //   (for transactions, below)
>    newValue      ==? oldValue
> // conditional CAS
>    updateValue   =? oldValue : newValue : predicate

That one in particular has the problem that remembering the order of
arguments is tricky.

I don't think that the new syntax is particularly clear compared to a
library based solution involving either free functions or a class like
std::atomic<int>. Certainly libraries should always be considered before
inventing a new syntax.

>
>   For a limited form of transaction support (either all or none of a
> set of changes occur) multiple updates are specified with an extension
> of the above syntax.  For instance, insertion of a new element into a
> doubly linked list between a previous and a next element, might be
> specified with:
>     SynchronizationElement<ElementPointer>
>         new, previous, next;
>     // Note: ElementPointer provides for ABA reuse
>     //   protection and exposes the referenced
>     //   element memory location.
>     new = - - -         // build new element
>     do {
>          - - -          // find insertion point
>          new.prev = previous ;
>          new.next = next     ;
>     } while ( previous.next   =? next    : new &&
>               next.prev       =? previous: new    )
>
>  This model is based on synchronization of a set of data changes.  It
> is complementary to other approaches, such as the Java model, that are
> based on capturing an ordered sequence of critical memory updates, with
> appropriate regard for synchronizing relations including
> "is-sequenced-before", "is-ordered-before", "depends on"
> and "communicates with". Advantages claimed include:

I'll look at these compared to a library based solution:

> *  It specifies succinctly and completely in the code what data needs
> to be synchronized and when.

Same for a library.

> *  This can lead to faster "memory barriers" on processors where
> only the relevant cache data needs to be flushed, invalidated, or
> synchronized.

That's true of any solution. A library based solution can make this more
explicit and controllable (e.g. see Terekhov's atomic<T> template).

> *  It can be supported on many processors with well known
> "lock-free" techniques.
> *  It is essentially portable.
> *  It provides a level of abstraction that appears considerably easier
> to code to and to reason about for correctness.

All also true for a library based solution.

Personally, I don't think a solution based on volatile is any good
either, since that isn't flexible or explicit enough. But that doesn't
mean we need new obscure syntax.

Tom

---
[ 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.comeaucomputing.com/csc/faq.html                      ]