[concurrency-interest] The very best CAS loop

Martin Buchholz martinrb at google.com
Mon Sep 26 13:51:59 EDT 2016


On Mon, Sep 26, 2016 at 10:36 AM, Paul Sandoz <paul.sandoz at oracle.com>
wrote:

>
> 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.
>
>
That code was just demonstrating how the return value from get() was
getting lost, whereas if you inline a weak cas loop as I have done, you
save the extra call to get().


> 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'm imagining user code that counts all the calls to getAndUpdate, and all
the calls to updateFunction.  If they differ, I would like that to be
evidence of true contention.   True, we tell users updateFunction is
supposed to be side-effect-free.  OTOH, we say that attempted updates may
fail due to "contention among threads", suggesting we don't call
updateFunction spuriously.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20160926/cb1db864/attachment.html>


More information about the Concurrency-interest mailing list