[concurrency-interest] AtomicReference.updateAndGet() mandatory updating
boehm at acm.org
Thu May 25 19:44:27 EDT 2017
Full counterexamples, with both threads, would be extremely useful here.
"guarantees that another thread reading z after CAS will observe *both* y=2
Only if it can somehow tell that it read z after the CAS. If the CAS didn't
change the value of z, that's exceedingly hard to tell. Even if we presume
there is a (non-volatile) store to w after the CAS, and the other thread
sees the store to w, this is not guaranteed if e.g. the CAS is implemented
with a critical section.
On Thu, May 25, 2017 at 3:41 PM, Alex Otenko <oleksandr.otenko at gmail.com>
> 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.
> 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
> 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.
> 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>
>> How quickly you arrived at “no algorithm whatsoever”! :-)
>> 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.
>> > On 24 May 2017, at 20:38, Justin Sampson <jsampson at guidewire.com>
>> > 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
>> >>> 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
>> > tell if it's reading after the write (and therefore can depend on the
>> > happens-before) or reading before the write (and therefore cannot),
>> > it sees the same value in either case.
>> > This kind of optimization is already done in some places in the JDK,
>> > as AtomicStampedReference and AtomicMarkableReference, both of which
>> > the write if the current value is already equal to the new value in
>> > compareAndSet(), etc.
>> > Cheers,
>> > Justin
>> > _______________________________________________
>> > Concurrency-interest mailing list
>> > Concurrency-interest at cs.oswego.edu
>> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Concurrency-interest