[jmm-dev] weakCompareAndSet memory semantics

[David Holmes]

On 21/04/2016 6:32 PM, Aleksey Shipilev wrote:
> On 21.04.2016 10:52, Andrew Haley wrote:
>> On 21/04/16 00:10, David Holmes wrote:
>>> On 21/04/2016 8:59 AM, Justin Sampson wrote:
>>>> David Holmes wrote:
>>>>
>>>>> Side question: why would you replace compareAndSet with
>>>>> weakCompareAndSet when that would expose those ll/sc spurious
>>>>> failures?
>>>>
>>>> The spurious failures are irrelevant because the whole thing is
>>>> wrapped in a retry loop anyway.
>>>
>>> And in the compareAndSet the spurious failures never escape because it
>>> also has a retry loop. So my question stands: why would you switch to
>>> weakCompareAndSet in "busy loops" and how would this be a benefit?
>>
>> Say you're incrementing a heavily-contended counter.  There's no point
>> spinning in a loop if the store fails or if there is a spurious failure.
>>
>> You want to do this:
>>
>> loop:
>>      ldax x0, [addr]
>>      add x0, x0, #1
>>      stlx status, x0, [addr]
>>      cbnz status, loop
>>
>> You can simulate this with weakCompareAndSet.
>
> Yes, that seems to be the similar thing I was saying in my original note:
>
> void incr() {
>    int v;
>    do {
>      v = ai.get();
>    } while (!weakCompareAndSet(v, v + 1)); // single LL/SC
> }
>
> IOW, there is no point in spinning inside CAS method to emulate strong
> CAS with LL/SC, when you can just retry in the upper loop -- and reap
> the benefits from it, because you will have an opportunity to come up
> with an *new* value to set, rather than busting the doors trying to put
> in the stale value.

How are you busting the doors if you get a _spurious_ failure? It means 
something unrelated directly to your CAS (so your value is not stale!) 
happened. The spurious failures from ll/sc are a result of 
implementation constraints so it has never made sense to me to have that 
exposed at a higher level. On the contrary many CAS-based algorithms 
expect that failure indicates some other thread made progress.

David
-----

> I think this is the reason why C++11 says: "The weak forms (1-2) of the
> functions are allowed to fail spuriously, that is, act as if *this !=
> expected even if they are equal. When a compare-and-exchange is in a
> loop, the weak version will yield better performance on some platforms."
>    http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange
>
> Thanks,
> -Aleksey
>