[concurrency-interest] The very best CAS loop

Martin Buchholz martinrb at google.com
Mon Sep 26 13:01:22 EDT 2016


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;
    }


On Mon, Sep 26, 2016 at 12:20 AM, Aleksey Shipilev <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/5d219e12/attachment.html>


More information about the Concurrency-interest mailing list