[concurrency-interest] AtomicReference.updateAndGet() mandatory updating

Alex Otenko oleksandr.otenko at gmail.com
Thu May 25 18:41:37 EDT 2017


Ok, if this is rare, then isn’t also a CAS with expected == new value rare?

It is not just about delaying the stores, but also about seeing them all at the same time.

x=1
y=2
z.CAS(…)

guarantees that another thread reading z after CAS will observe *both* y=2 and x=1.

If we make the case z.CAS(e, e) special (not a store, or no barrier before the volatile load in the “optimized” version), then this no longer can be guaranteed.

If the store is eliminated from CAS, then another thread does not synchronize-with the thread performing this CAS. In real terms this means it will not guarantee visibility of *both* y=2 and x=1.

Alex

> On 25 May 2017, at 23:01, Hans Boehm <boehm at acm.org> wrote:
> 
> IIUC, you're arguing that this transformation is valid only if we know that the implementation does not indefinitely delay the store to x past the do-while loop implementing compareAndSet()? E.g. if the compareAndSet thread subsequently prints something, and then goes into an infinite loop, I still have a guarantee that a thread that alternately reads x and y will eventually see x == 1?
> 
> I'm inclined to agree with that, though I expect that implementations violating this assumption are really rare.
> 
> On Thu, May 25, 2017 at 1:23 AM, Alex Otenko <oleksandr.otenko at gmail.com <mailto:oleksandr.otenko at gmail.com>> wrote:
> How quickly you arrived at “no algorithm whatsoever”! :-)
> 
> x=1;
> y.compareAndSet(e,v)
> 
> Under assumption that there are infinitely many volatile reads of y, the return from compareAndSet is a witness that there exists a read in the future that synchronizes-with this invocation of compareAndSet.
> 
> You cannot argue that sometimes you can skip the volatile store semantics on what would be a successful compareAndSet - because then the stores preceding compareAndSet are not guaranteed to be visible - ever. This optimization is a platform-specific decision.
> 
> 
> You can argue about what happens if compareAndSet fails. My take is it should still have volatile store semantics - ie should be equivalent to the store of the value that is already there, so it appears unmodified, but synchronizes-with edges can be established.
> 
> 
> Alex
> 
> > On 24 May 2017, at 20:38, Justin Sampson <jsampson at guidewire.com <mailto:jsampson at guidewire.com>> wrote:
> >
> > Andrew Haley wrote:
> >> Mike Duigou wrote:
> >>> I find that I write a lot of update functions which only occasionally
> >>> change the value. For these cases I wonder if it would be reasonable to
> >>> skip the update if the value of next is unchanged from previous.
> >>
> >> I don't think so, because the update has the effect of a volatile
> >> write. If you skip the update you lose the happens-before ordering
> >> of that write.
> >
> > That's strictly true (the memory barriers come out different), but no
> > algorithm could actually rely on the difference. The reading thread can't
> > tell if it's reading after the write (and therefore can depend on the
> > happens-before) or reading before the write (and therefore cannot), since
> > it sees the same value in either case.
> >
> > This kind of optimization is already done in some places in the JDK, such
> > as AtomicStampedReference and AtomicMarkableReference, both of which skip
> > the write if the current value is already equal to the new value in set(),
> > compareAndSet(), etc.
> >
> > Cheers,
> > Justin
> >
> > _______________________________________________
> > Concurrency-interest mailing list
> > Concurrency-interest at cs.oswego.edu <mailto:Concurrency-interest at cs.oswego.edu>
> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
> 
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu <mailto:Concurrency-interest at cs.oswego.edu>
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest <http://cs.oswego.edu/mailman/listinfo/concurrency-interest>
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20170525/4790cff3/attachment.html>


More information about the Concurrency-interest mailing list