[concurrency-interest] AtomicReference weakCompareAndSet "Mayfailspuriously"?

Boehm, Hans hans.boehm at hp.com
Wed May 17 20:40:42 EDT 2006


I'm not completely convinced that the issue is really different for
references.

I think that fundamentally spurious failures and ordering are quite
different.  Allowing spurious failures is occasionally useful, and I
think something that's relatively easily understood.  Relaxing the
ordering can occasionally also be very useful, especially for low level
libraries, but I think it gets you considerably further into
"wizards-only" territory.

My impression, based in part on recent discussions in a C++ context, is
that few people really understand that in the absence of the ordering
semantics, data- or control-dependence does not imply ordering.  This
may be less of an issue with CompareAndSet, but I still think that the
fact that the changes to x and y in

if(x.weakCompareAndSet(a, b)) {
	y = 17;
}

can appear out of order is really unintuitive for most people.  And such
code is essentially untestable, since the ordering is in fact implied in
most cases, with most compilers, on most current hardware.  If you
require ordering, this sort of issue just goes away.

It seems to me that references are special, only in that the
weakCompareAndSet is often dereferenced before or after the
WeakCompareAndSet.  But that's a statistical property; not a guarantee.
It's certainly conceivable that references are used in an algorithm in
which they are only compared and never dereferenced.  Thus the contents
don't need to be communicated.  (I know of one large C++ program for
which the contents corresponding to many references were in fact dead
and had been explicitly deallocated.)  And I'm not sure that the
reference situation in which the contents of the reference are used is
much different from the AtomicInteger situation for which a later load
is dependent on the weakCompareAndSet result, as above.

Thus I think I would argue against resolving this differently for
AtomicReference and AtomicInteger.

I would be more positive on strengthening ordering of weakCompareAndSet
for both.  If you really want relaxed ordering variants for
CompareAndSet, my intuition is that all four possible variants (no
ordering, acquire, release, both) have about equal utility, and the "no
ordering" variant is the hardest to understand.  (It's usually
insufficient for reference counting, as I recall.)  And each weakening
potentially involves a performance gain. On the other hand, I'm not at
all sure that this is a sufficient argument for change at this point.

Hans

> -----Original Message-----
> From: Bill Pugh
> 
> weakCompareAndSet has volatile semantics, _except_ that it 
> doesn't create any happens-before edges.
> 
> Thus, using weakCompareAndSet is ideal for things such as 
> performance counters, unique identifiers and reference counting.
> 
> However, what about AtomicReference? If you actually try to 
> pass references between threads, you need to establish a 
> happens-before relationship between the two threads, so that 
> the contents of the object are communicated as well.
> 
> So, here is the question we should discuss:
> 
> **********
> 
> Should weakCompareAndSet on an AtomicReference create happens 
> before edges (just as compareAndSwap does)?
> 
> **********
> 
> For AtomicInteger, and similar classes, there isn't a 
> question. Just for AtomicReference classes.
> 
> I talked with Doug, and we agreed that we didn't have enough 
> use cases to really decide.
> 
> The only possible use for a weakCompareAndSet on a reference 
> where you don't need a happens-before edge is if you can 
> prove that a happens-before edge is created by some other mechanism.
> 
> So, if weakCompareAndSet does not establish a happens-before 
> ordering, then a few people (i.e, just Doug) might be able to 
> effectively use it to superoptimize some code.  
> However, without the happens-before ordering, some potential 
> use cases are invalid, and many people trying to use it will 
> create a data race.
> 
> Thoughts?
> 
> 	Bill
> 
> 
> 
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
> 



More information about the Concurrency-interest mailing list