[cpp-threads]atomic operations package

[Boehm, Hans]

It seems to me that we will have to make some serious compromises here.
In some cases, we will not be able to generate the fastest
possible code for every algorithm without resorting to assembly
code.

The problems with extremely fine-grained control are:

1) I think we mostly agreed the last time that this came up
that ordering constraints which mention data or control dependence
explicitly get in the way of separate compilation, at least if
we used the only reasonable definition that we (actually Peter)
could come up with.  A call to an atomic operation in one file
would inhibit standard transformations in a function called
by it, since compilers routinely add and eliminate data- and
control-dependencies.  I think this is clearly unacceptable.

2) It seems to be getting increasingly clear that other
variants are hard to specify, and potentially complicate the
memory model.

In my view, the data- and control-dependence based ordering
constraints are out, unless someone can address the specification
and separate compilation issues.

(I'm not entirely happy with this either.  If I want to write

r = p; // p shared "atomic" int * variable
*r = 13;

and I want the load and the store to be ordered, I currently
need an acquire load of p to ensure the ordering, which adds
overhead on some architectures.  That's in spite of the fact
that it's awfully hard to conceive of an architecture or
compiler that would really reorder those.  But I can't think of a
way to capture that in a way that makes sense at the source level.
Thus I currently have no such constraint on unordered reads.) 

I haven't thought about ordering constraints on reference counting
in a while.  I think the constraints we need to enforce are:

1) Updates to a specific reference count within a thread become visible
in order.  I'd be inclined to say that this should be a property
of even unordered atomic writes.

2) Field accesses need to be visible before the corresponding reference
count decrement.

3) The final reference count decrement needs to be visible before
the memory is deallocated and reused in a different thread.  I would
expect the memory allocator to handle that as part of it's shared
state update, e.g. with a release-store to a shared free list.

I think (2) can be handled with a release constraint on the decrement,
which also handles (1), if necessary.  This seems slightly suboptimal
on some architectures, but not horrible.  Am I missing something?

Hans

> -----Original Message-----
> From: 
> Cpp-threads_decadentplace.org.uk-bounces at decadentplace.org.uk 
> [mailto:Cpp-threads_decadentplace.org.uk-bounces at decadentplace
> .org.uk] On Behalf Of Alexander Terekhov
> Sent: Monday, August 15, 2005 2:02 AM
> To: cpp-threads at decadentplace.org.uk
> Subject: Re: [cpp-threads]atomic operations package
> 
> 
> On 8/14/05, Doug Lea <dl at cs.oswego.edu> wrote:
> > Boehm, Hans wrote:
> > > Since the details of the atomic operations package seem 
> to influence 
> > > the memory model and our terminology, and I haven't seen any 
> > > concrete proposals for the interface to the package, I put up a 
> > > concrete though very preliminary proposal at:
> > >
> > > http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/atomics.h.txt
> > >
> > > Please comment.
> > >
> > 
> > 
> >         template <ordering_constraint c>
> >             void store(const T&);
> >             // Compile-time error if c is neither none nor release.
> >         template <ordering_constraint c>
> >             T load();
> >             // Compile-time error if c is neither none nor acquire.
> > 
> > 
> > I think this is fine. I know that neither Peter Dimov nor Alexander 
> > Terekhov think this suffices to support usages they say they need. 
> > (Which is the main reason I gave up on variants of this.)
> > 
> > Peter and/or Alexander: Could you soon post something 
> (re)stating your 
> > concerns so we can make a decision about it rather than 
> continuing to 
> > stall?
> 
> One concern is that it won't suffice to efficiently support things 
> like reference counting for immutable objects and read-only 
> locks (all without suppressing reordering of writes). In the case of 
> read-only locks and when refcounts reach zero, we want (at most) 
> dd-/cc- hsb on read{-modify-write} ops for dependent writes (which 
> you seem to be ready to impose implicitly on all reads, if I 
> understand "the compromise" correctly).
> 
> regards,
> alexander.
> 
> -- 
> cpp-threads mailing list
> cpp-threads at decadentplace.org.uk 
> http://decadentplace.org.uk/mailman/listinfo/cpp-threads_decad
entplace.org.uk