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

Hans Boehm 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
and x=1"

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>
wrote:

> 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>
> 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>
>> 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
>> > http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu
>> 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/daa6c5a5/attachment.html>


More information about the Concurrency-interest mailing list