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

[Carter Schonwald]

Ryan,
would you please file a ticket on GHC trac explaining WHY ghc makes it
difficult to support CAS for boxed vectors? And you would like to be able
to do vs what you have had to do? Understanding why its currently difficult
to write new primitives for lockfree concurrency in user land seems like
something worth digging deeper into! (and perhaps trying to fix!)

as much as CAS on Storable / Unboxed would be cool, It seems like it'd only
work on instances that are actually 4,8,16 byte locations, right? 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.



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/20131120/278b0b4e/attachment.html>