Best way to get to CAS/fetch-and-add on unboxed vectors?

Thu Nov 21 19:33:41 UTC 2013

nothing blocking adding the primops right now from a technical standpoint
(though it'd be too late for the 7.8 merge window).
The main blocker is i'm moving over the next month + I'm amidst sorting
transitioning from consulting to some other work. (life and all).

i want to also add the inline  primops to the native code gen  and -fvia-c
in tandem with baking in the LLVM support. Which will take a teeny bit of
extra work, but really very much worth it I think.

Glad you agree about the constructors being handy! Should make is possible
to have the CAS vector stuff working as a selfcontained experiment that
just works ™ with current vector.

On Thu, Nov 21, 2013 at 2:05 PM, Ryan Newton <rrnewton at gmail.com> wrote:

> I'm not sure why this would be a ticket, because it's not really a bug or
> an issue with GHC.  But I did go ahead and write up the state of affairs in
> a Haskell wiki page here:
>
>     http://www.haskell.org/haskellwiki/AtomicMemoryOps
>
> There's just a fundamental impedance mismatch between having a lazy/pure
> world where pointer equality is meaningless, and operations based on
> pointer-equality like CAS.  I think we've papered over that as best we
> could with the "Ticketed" interface describe in that wiki, but I don't
> think there's anything else I could have asked of GHC to make this any
> easier.
>
> But as you know there are several improvements that can be made to make
> what we've got better.  Are you blocked on anything wrt to adding direct
> LLVM support for the primops in question?
>
> On Wed, Nov 20, 2013 at 4:38 PM, Carter Schonwald <
> carter.schonwald at gmail.com> wrote:
>
>> I though Vector instances had their constructors exported so that you can
>> get at the underlying Primitive vectors, and and Primitive vectors have a
>> bytearray underneath!
>> I don't understand why Vector/MVector needs to be changed here to support
>> that info.
>> For the Atomic operations, it seems like you just really want to only
>> support the operations on vector types directly expressable with Primitive
>> vectors. Perhaps i'm not understanding though.
>>
>
> As far as I can see if the user gives you a "Data.Vector.Unboxed.MVector s
> Int8", what you're getting is the result of this type function:
>
>     newtype instance MVector s Int8 = MV_Int8 (P.MVector s Int8)
>
> .. from Unboxed.Base.hs.  The only thing that's provided for "MVector s a"
> types generally are instances of the Vector/MVector classes, which don't
> say how to get the pointer(s).
>
> BUT... you make a good point about the constructors (e.g. MV_Int8) being
> exposed!  It seems like we CAN make our own type family that mirrors the
> MVector one, and which leverages *each* of those "newtype instance"
> equations, matching on an MV_Int8 and grabbing the underlying Primitive
> vector... Nice!
>
>
>
>
> On Wed, Nov 20, 2013 at 10:57 AM, Ryan Newton <rrnewton at gmail.com> wrote:
>>
>>> We do expose CAS for boxed data, and we depend on that for various
>>> concurrent data structures (e.g. Michael-scott queues).
>>>
>>> But it's a messy business:
>>>
>>> <explanation> You have to fight hard against the GHC optimizer to
>>> prevent it from performing optimizations (e.g. unbox and rebox an Int) that
>>> completely destroy pointer equality (in all runs of the program).  The way
>>> that we've codified our solution to this is to use abstract "Ticket"s
>>> (based on the Any kind) that GHC is not supposed to be able to see through.
>>>  These are used to abstractly represent old reads when you come back to do
>>> a new CAS operation:
>>>
>>>
>>> http://hackage.haskell.org/package/atomic-primops-0.4/docs/Data-Atomics.html#g:2
>>>
>>> Even then, there was a bunch of careful NOINLINE's and other business
>>> necessary to achieve something workable, and it's highly GHC specific.  If
>>> we were to expose CAS on boxed "Data.Vector", I think it would only make
>>> sense as the ticketed interface above (raw CAS is useless, and will just
>>> condemn others to the same problems we had).
>>> </explanation>
>>>
>>> As a result of all this the CAS for Data.Vector would have a different
>>> signature (unless we wanted to force Storable/Unbox to use Tickets), and
>>> thus couldn't go in the "MVector" type class along with all the other basic
>>> operations that are uniform across representations.
>>>
>>> That said, it's easy to provide CAS from a separate "vector-atomics"
>>> package, because Data.Vector exposes the MVector constructor that lets you
>>> get at the underlying MutableArray.  So we certainly can provide the
>>> functionality somewhere, somehow.
>>>
>>>   -Ryan
>>>
>>>
>>>
>>> On Wed, Nov 20, 2013 at 10:21 AM, Jan-Willem Maessen <
>>> jmaessen at alum.mit.edu> wrote:
>>>
>>>> On Wed, Nov 20, 2013 at 10:06 AM, Ryan Newton <rrnewton at gmail.com>wrote:
>>>>
>>>>> (3) The most invasive (but best for the user) change would be to
>>>>> extend the basic MVector interface to include notions of
>>>>> concurrency-related operations right inside the vector package (CAS, etc).
>>>>>  But they should still probably go in a separate class (not class MVector),
>>>>> just because they will be specific to Unboxed and Storable vectors rather
>>>>> than boxed ones....
>>>>>
>>>>
>>>> Any reason we shouldn't be able to CAS on boxed vectors?  Every
>>>> architecture supports a pointer-sized CAS.  What "equality" means for CAS,
>>>> of course, has to be rather carefully defined, but that's equally true for
>>>> the unboxed types.
>>>>
>>>> -Jan
>>>>
>>>>
>>>>>
>>>>>   -Ryan
>>>>>
>>>>>
>>>>> _______________________________________________
>>>>> Libraries mailing list
>>>>> Libraries at haskell.org
>>>>> http://www.haskell.org/mailman/listinfo/libraries
>>>>>
>>>>>
>>>>
>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries at haskell.org
>>> http://www.haskell.org/mailman/listinfo/libraries
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20131121/90df5163/attachment.html>