<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class="">On 26 Sep 2016, at 10:01, Martin Buchholz <<a href="mailto:martinrb@google.com" class="">martinrb@google.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="">Hi Aleksey,</div><div class=""><br class=""></div><div class="">My goals were to </div><div class="">- have the shortest code path if the CAS succeeds the first time, which is hopefully the common case</div><div class="">- 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.</div><div class="">- 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!</div><div class=""><br class=""></div><div class="">    public final V getAndUpdate(UnaryOperator<V> updateFunction) {</div><div class="">        for (;;) {</div><div class="">            V prev = get();</div><div class="">            V next = updateFunction.apply(prev);</div><div class="">            if (strongCas(prev, next))</div><div class="">                return prev;</div><div class="">        }</div><div class="">    }</div><div class="">    /** Implement strong CAS using weak CAS. */</div><div class="">    boolean strongCas(V expectedValue, V newValue) {</div><div class="">        while (get() == expectedValue) {</div><div class="">            if (weakCompareAndSetVolatile(expectedValue, newValue))</div><div class="">                return true;</div><div class="">        }</div><div class="">        return false;</div><div class="">    }</div><div class=""><br class=""></div></div></div></blockquote><div><br class=""></div>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.</div><div><br class=""></div><div>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.</div><div> </div><div>I prefer Aleksey’s version.</div><div><br class=""></div><div>Paul.</div><div> </div><div><br class=""></div><div><br class=""><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="gmail_extra"><br class=""><div class="gmail_quote">On Mon, Sep 26, 2016 at 12:20 AM, Aleksey Shipilev <span dir="ltr" class=""><<a href="mailto:shade@redhat.com" target="_blank" class="">shade@redhat.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="gmail-HOEnZb"><div class="gmail-h5">On 09/24/2016 06:51 PM, Martin Buchholz wrote:<br class="">
> Discussion on CAS loops got me looking again at our own:<br class="">
><br class="">
>     public final V getAndUpdate(UnaryOperator<V> updateFunction) {<br class="">
>         V prev = get(), next = null;<br class="">
>         for (boolean haveNext = false;;) {<br class="">
>             if (!haveNext)<br class="">
>                 next = updateFunction.apply(prev);<br class="">
>             if (weakCompareAndSetVolatile(<wbr class="">prev, next))<br class="">
>                 return prev;<br class="">
>             haveNext = (prev == (prev = get()));<br class="">
>         }<br class="">
>     }<br class="">
><br class="">
> The haveNext boolean and useless initialization of next bothers me.  We<br class="">
> can do better!<br class="">
><br class="">
>     public final V getAndUpdate(UnaryOperator<V> updateFunction) {<br class="">
>         for (V prev = get();;) {<br class="">
>             V next = updateFunction.apply(prev);<br class="">
>             do {<br class="">
>                 if (weakCompareAndSetVolatile(<wbr class="">prev, next))<br class="">
>                     return prev;<br class="">
>             } while (prev == (prev = get()));<br class="">
>         }<br class="">
>     }<br class="">
><br class="">
> even though it probably saves more bytecodes than cycles.<br class="">
<br class="">
</div></div>I don't quite get why do we need to retry on the same "prev" to begin<br class="">
with: we are allowed to call function several times on the same value.<br class="">
If so, there is a more canonical form:<br class="">
<span class="gmail-"><br class="">
     public final V getAndUpdate(UnaryOperator<V> updateFunction) {<br class="">
</span>         V prev, next;<br class="">
         do {<br class="">
             prev = get();<br class="">
             next = updateFunction.apply(prev);<br class="">
         } while (!weakCompareAndSetVolatile(<wbr class="">prev, next));<br class="">
         return prev;<br class="">
     }<br class="">
<br class="">
CAS-vs-CAE example shows us that additional branches in the hot CAS loop<br class="">
would be detrimental for performance under contention (and an quick<br class="">
update function here, probably). Accurate benchmarking would tell you a<br class="">
story, we cannot do this by looking at the code.<br class="">
<br class="">
Also, retrying on (spurious) failure when prev had not changed negates<br class="">
the reason to use weakCAS: now you have just constructed the retry loop<br class="">
that strong CAS does with LL/SC, and we have tried to avoid that with<br class="">
weakCAS!<br class="">
<br class="">
Thanks,<br class="">
-Aleksey<br class="">
<br class="">
</blockquote></div><br class=""></div></div>
</div></blockquote></div><br class=""></body></html>