[concurrency-interest] The very best CAS loop

Aleksey Shipilev shade at redhat.com
Mon Sep 26 03:20:53 EDT 2016


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 --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160926/63a8f11f/attachment-0001.sig>


More information about the Concurrency-interest mailing list