[concurrency-interest] The very best CAS loop

Paul Sandoz paul.sandoz at oracle.com
Mon Sep 26 13:36:26 EDT 2016


> On 26 Sep 2016, at 10:01, Martin Buchholz <martinrb at google.com> wrote:
> 
> Hi Aleksey,
> 
> My goals were to
> - have the shortest code path if the CAS succeeds the first time, which is hopefully the common case
> - never call the update function multiple times in the case of spurious failure, only for real contention.  We don't know how expensive the update function is, and the number of times it is called is user-detectable.
> - yes, I have sort-of reconstructed the retry loop that strong CAS does with LL/SC, BUT we can save the value obtained from get(), which does not happen in the emulation below.  We don't have multiple value return in java!
> 
>     public final V getAndUpdate(UnaryOperator<V> updateFunction) {
>         for (;;) {
>             V prev = get();
>             V next = updateFunction.apply(prev);
>             if (strongCas(prev, next))
>                 return prev;
>         }
>     }
>     /** Implement strong CAS using weak CAS. */
>     boolean strongCas(V expectedValue, V newValue) {
>         while (get() == expectedValue) {
>             if (weakCompareAndSetVolatile(expectedValue, newValue))
>                 return true;
>         }
>         return false;
>     }
> 

If you are gonna do why not just call “compareAndSet" instead of emulating with your own “strongCas” method? and then, i presume, we are back to where we started.

I don’t think the “updateFunction” can tell a spurious failure from another failure given the variable, under contention, can change from and back to the previous between the “strongCas” call.

I prefer Aleksey’s version.

Paul.



> 
> On Mon, Sep 26, 2016 at 12:20 AM, Aleksey Shipilev <shade at redhat.com <mailto:shade at redhat.com>> wrote:
> On 09/24/2016 06:51 PM, Martin Buchholz wrote:
> > Discussion on CAS loops got me looking again at our own:
> >
> >     public final V getAndUpdate(UnaryOperator<V> updateFunction) {
> >         V prev = get(), next = null;
> >         for (boolean haveNext = false;;) {
> >             if (!haveNext)
> >                 next = updateFunction.apply(prev);
> >             if (weakCompareAndSetVolatile(prev, next))
> >                 return prev;
> >             haveNext = (prev == (prev = get()));
> >         }
> >     }
> >
> > The haveNext boolean and useless initialization of next bothers me.  We
> > can do better!
> >
> >     public final V getAndUpdate(UnaryOperator<V> updateFunction) {
> >         for (V prev = get();;) {
> >             V next = updateFunction.apply(prev);
> >             do {
> >                 if (weakCompareAndSetVolatile(prev, next))
> >                     return prev;
> >             } while (prev == (prev = get()));
> >         }
> >     }
> >
> > even though it probably saves more bytecodes than cycles.
> 
> I don't quite get why do we need to retry on the same "prev" to begin
> with: we are allowed to call function several times on the same value.
> If so, there is a more canonical form:
> 
>      public final V getAndUpdate(UnaryOperator<V> updateFunction) {
>          V prev, next;
>          do {
>              prev = get();
>              next = updateFunction.apply(prev);
>          } while (!weakCompareAndSetVolatile(prev, next));
>          return prev;
>      }
> 
> CAS-vs-CAE example shows us that additional branches in the hot CAS loop
> would be detrimental for performance under contention (and an quick
> update function here, probably). Accurate benchmarking would tell you a
> story, we cannot do this by looking at the code.
> 
> Also, retrying on (spurious) failure when prev had not changed negates
> the reason to use weakCAS: now you have just constructed the retry loop
> that strong CAS does with LL/SC, and we have tried to avoid that with
> weakCAS!
> 
> Thanks,
> -Aleksey
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160926/74317c78/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 841 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160926/74317c78/attachment-0001.sig>


More information about the Concurrency-interest mailing list