Compare-and-swap semantics in GHC

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Compare-and-swap semantics in GHC

KwangYul Seo
Hi,

java.util.concurrent.atomic package provides two flavors of compare and set
operations: compareAndSet and weakCompareAndSet. The latter does not create
any happens-before orderings, so we can use it where no guarantees with
respect to previous or subsequent reads and writes of any variables other
than the target of the weakCompareAndSet are required.

I'd like to ask if the compare-and-swap function provided by GHC runtime
(cas() in includes/stg/SMP.h) is strong or weak. If it is strong, do all
use cases of cas() require this semantics?

Regards,
Kwang Yul Seo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20131205/4dd16fec/attachment-0001.html>

Reply | Threaded
Open this post in threaded view
|

Compare-and-swap semantics in GHC

Carter Schonwald
cas in ghc has sequential semantics.

i'm not sure if every use of it needs that semantics, if you identify
examples where weaker operations may suffice, please share!


On Thu, Dec 5, 2013 at 2:58 AM, KwangYul Seo <kwangyul.seo at gmail.com> wrote:

> Hi,
>
> java.util.concurrent.atomic package provides two flavors of compare and
> set operations: compareAndSet and weakCompareAndSet. The latter does not
> create any happens-before orderings, so we can use it where no guarantees
> with respect to previous or subsequent reads and writes of any variables
> other than the target of the weakCompareAndSet are required.
>
> I'd like to ask if the compare-and-swap function provided by GHC runtime
> (cas() in includes/stg/SMP.h) is strong or weak. If it is strong, do all
> use cases of cas() require this semantics?
>
> Regards,
> Kwang Yul Seo
>
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://www.haskell.org/mailman/listinfo/ghc-devs
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20131205/d3b4e94a/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Compare-and-swap semantics in GHC

Carter Schonwald
hrm, i'm reading your mesage a bit more closely, and i'm not sure i
understand the distinction you mean by strong vs weak.

Do you mean "strong" as in STM style semantics for reads and writes? (ie if
i'm doing a CAS on memory location x, it totally orders all reads and
writes to ANY location y!=x too?).

if you mean something like that, I think CAS isn't strong, though perhaps
the best way to answer you question is to read the source for CAS and look
up the semantics of the assembly instructions on various architectures!

cheers (and apologies for the confusion on my part)
-Carter



On Thu, Dec 5, 2013 at 3:48 AM, Carter Schonwald <carter.schonwald at gmail.com
> wrote:

> cas in ghc has sequential semantics.
>
> i'm not sure if every use of it needs that semantics, if you identify
> examples where weaker operations may suffice, please share!
>
>
> On Thu, Dec 5, 2013 at 2:58 AM, KwangYul Seo <kwangyul.seo at gmail.com>wrote:
>
>> Hi,
>>
>> java.util.concurrent.atomic package provides two flavors of compare and
>> set operations: compareAndSet and weakCompareAndSet. The latter does not
>> create any happens-before orderings, so we can use it where no guarantees
>> with respect to previous or subsequent reads and writes of any variables
>> other than the target of the weakCompareAndSet are required.
>>
>> I'd like to ask if the compare-and-swap function provided by GHC runtime
>> (cas() in includes/stg/SMP.h) is strong or weak. If it is strong, do all
>> use cases of cas() require this semantics?
>>
>> Regards,
>> Kwang Yul Seo
>>
>>
>> _______________________________________________
>> ghc-devs mailing list
>> ghc-devs at haskell.org
>> http://www.haskell.org/mailman/listinfo/ghc-devs
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20131205/4b8a8077/attachment.html>

Reply | Threaded
Open this post in threaded view
|

Compare-and-swap semantics in GHC

Edward Z. Yang
In reply to this post by KwangYul Seo
It's strong.  How to tell: x86 doesn't support really have any kind of
weak CAS implementation; and our PowerPC implementation loops over
LL/SC. (oh, and our asm is marked volatile)

As for whether or not there are any uses of CAS that don't need these
guarantees, probably the best way to figure this out is to look for any
uses of CAS, for which better algorithms using LL/SC are known (since
that's really the only well known implementation of this "weak" compare
and swap).  Of course, it's worth noting that any of these improvements
would not apply to today's x86, so they'd be of somewhat limited
applicability.

Cheers,
Edward

Excerpts from KwangYul Seo's message of 2013-12-04 23:58:50 -0800:

> Hi,
>
> java.util.concurrent.atomic package provides two flavors of compare and set
> operations: compareAndSet and weakCompareAndSet. The latter does not create
> any happens-before orderings, so we can use it where no guarantees with
> respect to previous or subsequent reads and writes of any variables other
> than the target of the weakCompareAndSet are required.
>
> I'd like to ask if the compare-and-swap function provided by GHC runtime
> (cas() in includes/stg/SMP.h) is strong or weak. If it is strong, do all
> use cases of cas() require this semantics?
>
> Regards,
> Kwang Yul Seo