ArrayArrays

[Simon Peyton Jones]

It was fun to meet and discuss this.

Did someone volunteer to write a wiki page that describes the proposed design?  And, I earnestly hope, also describes the menagerie of currently available array types and primops so that users can have some chance of picking the right one?!

Thanks

Simon

From: ghc-devs [mailto:ghc-devs-bounces at haskell.org] On Behalf Of Ryan Newton
Sent: 31 August 2015 23:11
To: Edward Kmett; Johan Tibell
Cc: Simon Marlow; Manuel M T Chakravarty; Chao-Hong Chen; ghc-devs; Ryan Scott; Ryan Yates
Subject: Re: ArrayArrays

Dear Edward, Ryan Yates, and other interested parties --

So when should we meet up about this?

May I propose the Tues afternoon break for everyone at ICFP who is interested in this topic?  We can meet out in the coffee area and congregate around Edward Kmett, who is tall and should be easy to find ;-).

I think Ryan is going to show us how to use his new primops for combined array + other fields in one heap object?

On Sat, Aug 29, 2015 at 9:24 PM Edward Kmett <ekmett at gmail.com<mailto:ekmett at gmail.com>> wrote:
Without a custom primitive it doesn't help much there, you have to store the indirection to the mask.

With a custom primitive it should cut the on heap root-to-leaf path of everything in the HAMT in half. A shorter HashMap was actually one of the motivating factors for me doing this. It is rather astoundingly difficult to beat the performance of HashMap, so I had to start cheating pretty badly. ;)

-Edward

On Sat, Aug 29, 2015 at 5:45 PM, Johan Tibell <johan.tibell at gmail.com<mailto:johan.tibell at gmail.com>> wrote:
I'd also be interested to chat at ICFP to see if I can use this for my HAMT implementation.

On Sat, Aug 29, 2015 at 3:07 PM, Edward Kmett <ekmett at gmail.com<mailto:ekmett at gmail.com>> wrote:
Sounds good to me. Right now I'm just hacking up composable accessors for "typed slots" in a fairly lens-like fashion, and treating the set of slots I define and the 'new' function I build for the data type as its API, and build atop that. This could eventually graduate to template-haskell, but I'm not entirely satisfied with the solution I have. I currently distinguish between what I'm calling "slots" (things that point directly to another SmallMutableArrayArray# sans wrapper) and "fields" which point directly to the usual Haskell data types because unifying the two notions meant that I couldn't lift some coercions out "far enough" to make them vanish.

I'll be happy to run through my current working set of issues in person and -- as things get nailed down further -- in a longer lived medium than in personal conversations. ;)

-Edward

On Sat, Aug 29, 2015 at 7:59 AM, Ryan Newton <rrnewton at gmail.com<mailto:rrnewton at gmail.com>> wrote:
I'd also love to meet up at ICFP and discuss this.  I think the array primops plus a TH layer that lets (ab)use them many times without too much marginal cost sounds great.  And I'd like to learn how we could be either early users of, or help with, this infrastructure.

CC'ing in Ryan Scot and Omer Agacan who may also be interested in dropping in on such discussions @ICFP, and Chao-Hong Chen, a Ph.D. student who is currently working on concurrent data structures in Haskell, but will not be at ICFP.


On Fri, Aug 28, 2015 at 7:47 PM, Ryan Yates <fryguybob at gmail.com<mailto:fryguybob at gmail.com>> wrote:
I completely agree.  I would love to spend some time during ICFP and
friends talking about what it could look like.  My small array for STM
changes for the RTS can be seen here [1].  It is on a branch somewhere
between 7.8 and 7.10 and includes irrelevant STM bits and some
confusing naming choices (sorry), but should cover all the details
needed to implement it for a non-STM context.  The biggest surprise
for me was following small array too closely and having a word/byte
offset miss-match [2].

[1]: https://github.com/fryguybob/ghc/compare/ghc-htm-bloom...fryguybob:ghc-htm-mut
[2]: https://ghc.haskell.org/trac/ghc/ticket/10413

Ryan

On Fri, Aug 28, 2015 at 10:09 PM, Edward Kmett <ekmett at gmail.com<mailto:ekmett at gmail.com>> wrote:
> I'd love to have that last 10%, but its a lot of work to get there and more
> importantly I don't know quite what it should look like.
>
> On the other hand, I do have a pretty good idea of how the primitives above
> could be banged out and tested in a long evening, well in time for 7.12. And
> as noted earlier, those remain useful even if a nicer typed version with an
> extra level of indirection to the sizes is built up after.
>
> The rest sounds like a good graduate student project for someone who has
> graduate students lying around. Maybe somebody at Indiana University who has
> an interest in type theory and parallelism can find us one. =)
>
> -Edward
>
> On Fri, Aug 28, 2015 at 8:48 PM, Ryan Yates <fryguybob at gmail.com<mailto:fryguybob at gmail.com>> wrote:
>>
>> I think from my perspective, the motivation for getting the type
>> checker involved is primarily bringing this to the level where users
>> could be expected to build these structures.  it is reasonable to
>> think that there are people who want to use STM (a context with
>> mutation already) to implement a straight forward data structure that
>> avoids extra indirection penalty.  There should be some places where
>> knowing that things are field accesses rather then array indexing
>> could be helpful, but I think GHC is good right now about handling
>> constant offsets.  In my code I don't do any bounds checking as I know
>> I will only be accessing my arrays with constant indexes.  I make
>> wrappers for each field access and leave all the unsafe stuff in
>> there.  When things go wrong though, the compiler is no help.  Maybe
>> template Haskell that generates the appropriate wrappers is the right
>> direction to go.
>> There is another benefit for me when working with these as arrays in
>> that it is quite simple and direct (given the hoops already jumped
>> through) to play with alignment.  I can ensure two pointers are never
>> on the same cache-line by just spacing things out in the array.
>>
>> On Fri, Aug 28, 2015 at 7:33 PM, Edward Kmett <ekmett at gmail.com<mailto:ekmett at gmail.com>> wrote:
>> > They just segfault at this level. ;)
>> >
>> > Sent from my iPhone
>> >
>> > On Aug 28, 2015, at 7:25 PM, Ryan Newton <rrnewton at gmail.com<mailto:rrnewton at gmail.com>> wrote:
>> >
>> > You presumably also save a bounds check on reads by hard-coding the
>> > sizes?
>> >
>> > On Fri, Aug 28, 2015 at 3:39 PM, Edward Kmett <ekmett at gmail.com<mailto:ekmett at gmail.com>> wrote:
>> >>
>> >> Also there are 4 different "things" here, basically depending on two
>> >> independent questions:
>> >>
>> >> a.) if you want to shove the sizes into the info table, and
>> >> b.) if you want cardmarking.
>> >>
>> >> Versions with/without cardmarking for different sizes can be done
>> >> pretty
>> >> easily, but as noted, the infotable variants are pretty invasive.
>> >>
>> >> -Edward
>> >>
>> >> On Fri, Aug 28, 2015 at 6:36 PM, Edward Kmett <ekmett at gmail.com<mailto:ekmett at gmail.com>> wrote:
>> >>>
>> >>> Well, on the plus side you'd save 16 bytes per object, which adds up
>> >>> if
>> >>> they were small enough and there are enough of them. You get a bit
>> >>> better
>> >>> locality of reference in terms of what fits in the first cache line of
>> >>> them.
>> >>>
>> >>> -Edward
>> >>>
>> >>> On Fri, Aug 28, 2015 at 6:14 PM, Ryan Newton <rrnewton at gmail.com<mailto:rrnewton at gmail.com>>
>> >>> wrote:
>> >>>>
>> >>>> Yes. And for the short term I can imagine places we will settle with
>> >>>> arrays even if it means tracking lengths unnecessarily and
>> >>>> unsafeCoercing
>> >>>> pointers whose types don't actually match their siblings.
>> >>>>
>> >>>> Is there anything to recommend the hacks mentioned for fixed sized
>> >>>> array
>> >>>> objects *other* than using them to fake structs? (Much to
>> >>>> derecommend, as
>> >>>> you mentioned!)
>> >>>>
>> >>>> On Fri, Aug 28, 2015 at 3:07 PM Edward Kmett <ekmett at gmail.com<mailto:ekmett at gmail.com>>
>> >>>> wrote:
>> >>>>>
>> >>>>> I think both are useful, but the one you suggest requires a lot more
>> >>>>> plumbing and doesn't subsume all of the usecases of the other.
>> >>>>>
>> >>>>> -Edward
>> >>>>>
>> >>>>> On Fri, Aug 28, 2015 at 5:51 PM, Ryan Newton <rrnewton at gmail.com<mailto:rrnewton at gmail.com>>
>> >>>>> wrote:
>> >>>>>>
>> >>>>>> So that primitive is an array like thing (Same pointed type,
>> >>>>>> unbounded
>> >>>>>> length) with extra payload.
>> >>>>>>
>> >>>>>> I can see how we can do without structs if we have arrays,
>> >>>>>> especially
>> >>>>>> with the extra payload at front. But wouldn't the general solution
>> >>>>>> for
>> >>>>>> structs be one that that allows new user data type defs for #
>> >>>>>> types?
>> >>>>>>
>> >>>>>>
>> >>>>>>
>> >>>>>> On Fri, Aug 28, 2015 at 4:43 PM Edward Kmett <ekmett at gmail.com<mailto:ekmett at gmail.com>>
>> >>>>>> wrote:
>> >>>>>>>
>> >>>>>>> Some form of MutableStruct# with a known number of words and a
>> >>>>>>> known
>> >>>>>>> number of pointers is basically what Ryan Yates was suggesting
>> >>>>>>> above, but
>> >>>>>>> where the word counts were stored in the objects themselves.
>> >>>>>>>
>> >>>>>>> Given that it'd have a couple of words for those counts it'd
>> >>>>>>> likely
>> >>>>>>> want to be something we build in addition to MutVar# rather than a
>> >>>>>>> replacement.
>> >>>>>>>
>> >>>>>>> On the other hand, if we had to fix those numbers and build info
>> >>>>>>> tables that knew them, and typechecker support, for instance, it'd
>> >>>>>>> get
>> >>>>>>> rather invasive.
>> >>>>>>>
>> >>>>>>> Also, a number of things that we can do with the 'sized' versions
>> >>>>>>> above, like working with evil unsized c-style arrays directly
>> >>>>>>> inline at the
>> >>>>>>> end of the structure cease to be possible, so it isn't even a pure
>> >>>>>>> win if we
>> >>>>>>> did the engineering effort.
>> >>>>>>>
>> >>>>>>> I think 90% of the needs I have are covered just by adding the one
>> >>>>>>> primitive. The last 10% gets pretty invasive.
>> >>>>>>>
>> >>>>>>> -Edward
>> >>>>>>>
>> >>>>>>> On Fri, Aug 28, 2015 at 5:30 PM, Ryan Newton <rrnewton at gmail.com<mailto:rrnewton at gmail.com>>
>> >>>>>>> wrote:
>> >>>>>>>>
>> >>>>>>>> I like the possibility of a general solution for mutable structs
>> >>>>>>>> (like Ed said), and I'm trying to fully understand why it's hard.
>> >>>>>>>>
>> >>>>>>>> So, we can't unpack MutVar into constructors because of object
>> >>>>>>>> identity problems. But what about directly supporting an
>> >>>>>>>> extensible set of
>> >>>>>>>> unlifted MutStruct# objects, generalizing (and even replacing)
>> >>>>>>>> MutVar#? That
>> >>>>>>>> may be too much work, but is it problematic otherwise?
>> >>>>>>>>
>> >>>>>>>> Needless to say, this is also critical if we ever want best in
>> >>>>>>>> class
>> >>>>>>>> lockfree mutable structures, just like their Stm and sequential
>> >>>>>>>> counterparts.
>> >>>>>>>>
>> >>>>>>>> On Fri, Aug 28, 2015 at 4:43 AM Simon Peyton Jones
>> >>>>>>>> <simonpj at microsoft.com<mailto:simonpj at microsoft.com>> wrote:
>> >>>>>>>>>
>> >>>>>>>>> At the very least I'll take this email and turn it into a short
>> >>>>>>>>> article.
>> >>>>>>>>>
>> >>>>>>>>> Yes, please do make it into a wiki page on the GHC Trac, and
>> >>>>>>>>> maybe
>> >>>>>>>>> make a ticket for it.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Thanks
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Simon
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> From: Edward Kmett [mailto:ekmett at gmail.com<mailto:ekmett at gmail.com>]
>> >>>>>>>>> Sent: 27 August 2015 16:54
>> >>>>>>>>> To: Simon Peyton Jones
>> >>>>>>>>> Cc: Manuel M T Chakravarty; Simon Marlow; ghc-devs
>> >>>>>>>>> Subject: Re: ArrayArrays
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> An ArrayArray# is just an Array# with a modified invariant. It
>> >>>>>>>>> points directly to other unlifted ArrayArray#'s or ByteArray#'s.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> While those live in #, they are garbage collected objects, so
>> >>>>>>>>> this
>> >>>>>>>>> all lives on the heap.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> They were added to make some of the DPH stuff fast when it has
>> >>>>>>>>> to
>> >>>>>>>>> deal with nested arrays.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> I'm currently abusing them as a placeholder for a better thing.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> The Problem
>> >>>>>>>>>
>> >>>>>>>>> -----------------
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Consider the scenario where you write a classic doubly-linked
>> >>>>>>>>> list
>> >>>>>>>>> in Haskell.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> data DLL = DLL (IORef (Maybe DLL) (IORef (Maybe DLL)
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Chasing from one DLL to the next requires following 3 pointers
>> >>>>>>>>> on
>> >>>>>>>>> the heap.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> DLL ~> IORef (Maybe DLL) ~> MutVar# RealWorld (Maybe DLL) ~>
>> >>>>>>>>> Maybe
>> >>>>>>>>> DLL ~> DLL
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> That is 3 levels of indirection.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> We can trim one by simply unpacking the IORef with
>> >>>>>>>>> -funbox-strict-fields or UNPACK
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> We can trim another by adding a 'Nil' constructor for DLL and
>> >>>>>>>>> worsening our representation.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> data DLL = DLL !(IORef DLL) !(IORef DLL) | Nil
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> but now we're still stuck with a level of indirection
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> DLL ~> MutVar# RealWorld DLL ~> DLL
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> This means that every operation we perform on this structure
>> >>>>>>>>> will
>> >>>>>>>>> be about half of the speed of an implementation in most other
>> >>>>>>>>> languages
>> >>>>>>>>> assuming we're memory bound on loading things into cache!
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Making Progress
>> >>>>>>>>>
>> >>>>>>>>> ----------------------
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> I have been working on a number of data structures where the
>> >>>>>>>>> indirection of going from something in * out to an object in #
>> >>>>>>>>> which
>> >>>>>>>>> contains the real pointer to my target and coming back
>> >>>>>>>>> effectively doubles
>> >>>>>>>>> my runtime.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> We go out to the MutVar# because we are allowed to put the
>> >>>>>>>>> MutVar#
>> >>>>>>>>> onto the mutable list when we dirty it. There is a well defined
>> >>>>>>>>> write-barrier.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> I could change out the representation to use
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> data DLL = DLL (MutableArray# RealWorld DLL) | Nil
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> I can just store two pointers in the MutableArray# every time,
>> >>>>>>>>> but
>> >>>>>>>>> this doesn't help _much_ directly. It has reduced the amount of
>> >>>>>>>>> distinct
>> >>>>>>>>> addresses in memory I touch on a walk of the DLL from 3 per
>> >>>>>>>>> object to 2.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> I still have to go out to the heap from my DLL and get to the
>> >>>>>>>>> array
>> >>>>>>>>> object and then chase it to the next DLL and chase that to the
>> >>>>>>>>> next array. I
>> >>>>>>>>> do get my two pointers together in memory though. I'm paying for
>> >>>>>>>>> a card
>> >>>>>>>>> marking table as well, which I don't particularly need with just
>> >>>>>>>>> two
>> >>>>>>>>> pointers, but we can shed that with the "SmallMutableArray#"
>> >>>>>>>>> machinery added
>> >>>>>>>>> back in 7.10, which is just the old array code a a new data
>> >>>>>>>>> type, which can
>> >>>>>>>>> speed things up a bit when you don't have very big arrays:
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> data DLL = DLL (SmallMutableArray# RealWorld DLL) | Nil
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> But what if I wanted my object itself to live in # and have two
>> >>>>>>>>> mutable fields and be able to share the sme write barrier?
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> An ArrayArray# points directly to other unlifted array types.
>> >>>>>>>>> What
>> >>>>>>>>> if we have one # -> * wrapper on the outside to deal with the
>> >>>>>>>>> impedence
>> >>>>>>>>> mismatch between the imperative world and Haskell, and then just
>> >>>>>>>>> let the
>> >>>>>>>>> ArrayArray#'s hold other arrayarrays.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> data DLL = DLL (MutableArrayArray# RealWorld)
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> now I need to make up a new Nil, which I can just make be a
>> >>>>>>>>> special
>> >>>>>>>>> MutableArrayArray# I allocate on program startup. I can even
>> >>>>>>>>> abuse pattern
>> >>>>>>>>> synonyms. Alternately I can exploit the internals further to
>> >>>>>>>>> make this
>> >>>>>>>>> cheaper.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Then I can use the readMutableArrayArray# and
>> >>>>>>>>> writeMutableArrayArray# calls to directly access the preceding
>> >>>>>>>>> and next
>> >>>>>>>>> entry in the linked list.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> So now we have one DLL wrapper which just 'bootstraps me' into a
>> >>>>>>>>> strict world, and everything there lives in #.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> next :: DLL -> IO DLL
>> >>>>>>>>>
>> >>>>>>>>> next (DLL m) = IO $ \s -> case readMutableArrayArray# s of
>> >>>>>>>>>
>> >>>>>>>>>    (# s', n #) -> (# s', DLL n #)
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> It turns out GHC is quite happy to optimize all of that code to
>> >>>>>>>>> keep things unboxed. The 'DLL' wrappers get removed pretty
>> >>>>>>>>> easily when they
>> >>>>>>>>> are known strict and you chain operations of this sort!
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Cleaning it Up
>> >>>>>>>>>
>> >>>>>>>>> ------------------
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Now I have one outermost indirection pointing to an array that
>> >>>>>>>>> points directly to other arrays.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> I'm stuck paying for a card marking table per object, but I can
>> >>>>>>>>> fix
>> >>>>>>>>> that by duplicating the code for MutableArrayArray# and using a
>> >>>>>>>>> SmallMutableArray#. I can hack up primops that let me store a
>> >>>>>>>>> mixture of
>> >>>>>>>>> SmallMutableArray# fields and normal ones in the data structure.
>> >>>>>>>>> Operationally, I can even do so by just unsafeCoercing the
>> >>>>>>>>> existing
>> >>>>>>>>> SmallMutableArray# primitives to change the kind of one of the
>> >>>>>>>>> arguments it
>> >>>>>>>>> takes.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> This is almost ideal, but not quite. I often have fields that
>> >>>>>>>>> would
>> >>>>>>>>> be best left unboxed.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> data DLLInt = DLL !Int !(IORef DLL) !(IORef DLL) | Nil
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> was able to unpack the Int, but we lost that. We can currently
>> >>>>>>>>> at
>> >>>>>>>>> best point one of the entries of the SmallMutableArray# at a
>> >>>>>>>>> boxed or at a
>> >>>>>>>>> MutableByteArray# for all of our misc. data and shove the int in
>> >>>>>>>>> question in
>> >>>>>>>>> there.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> e.g. if I were to implement a hash-array-mapped-trie I need to
>> >>>>>>>>> store masks and administrivia as I walk down the tree. Having to
>> >>>>>>>>> go off to
>> >>>>>>>>> the side costs me the entire win from avoiding the first pointer
>> >>>>>>>>> chase.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> But, if like Ryan suggested, we had a heap object we could
>> >>>>>>>>> construct that had n words with unsafe access and m pointers to
>> >>>>>>>>> other heap
>> >>>>>>>>> objects, one that could put itself on the mutable list when any
>> >>>>>>>>> of those
>> >>>>>>>>> pointers changed then I could shed this last factor of two in
>> >>>>>>>>> all
>> >>>>>>>>> circumstances.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Prototype
>> >>>>>>>>>
>> >>>>>>>>> -------------
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Over the last few days I've put together a small prototype
>> >>>>>>>>> implementation with a few non-trivial imperative data structures
>> >>>>>>>>> for things
>> >>>>>>>>> like Tarjan's link-cut trees, the list labeling problem and
>> >>>>>>>>> order-maintenance.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> https://github.com/ekmett/structs
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Notable bits:
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Data.Struct.Internal.LinkCut provides an implementation of
>> >>>>>>>>> link-cut
>> >>>>>>>>> trees in this style.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Data.Struct.Internal provides the rather horrifying guts that
>> >>>>>>>>> make
>> >>>>>>>>> it go fast.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Once compiled with -O or -O2, if you look at the core, almost
>> >>>>>>>>> all
>> >>>>>>>>> the references to the LinkCut or Object data constructor get
>> >>>>>>>>> optimized away,
>> >>>>>>>>> and we're left with beautiful strict code directly mutating out
>> >>>>>>>>> underlying
>> >>>>>>>>> representation.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> At the very least I'll take this email and turn it into a short
>> >>>>>>>>> article.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> -Edward
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> On Thu, Aug 27, 2015 at 9:00 AM, Simon Peyton Jones
>> >>>>>>>>> <simonpj at microsoft.com<mailto:simonpj at microsoft.com>> wrote:
>> >>>>>>>>>
>> >>>>>>>>> Just to say that I have no idea what is going on in this thread.
>> >>>>>>>>> What is ArrayArray?  What is the issue in general?  Is there a
>> >>>>>>>>> ticket? Is
>> >>>>>>>>> there a wiki page?
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> If it’s important, an ab-initio wiki page + ticket would be a
>> >>>>>>>>> good
>> >>>>>>>>> thing.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Simon
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> From: ghc-devs [mailto:ghc-devs-bounces at haskell.org<mailto:ghc-devs-bounces at haskell.org>] On Behalf
>> >>>>>>>>> Of
>> >>>>>>>>> Edward Kmett
>> >>>>>>>>> Sent: 21 August 2015 05:25
>> >>>>>>>>> To: Manuel M T Chakravarty
>> >>>>>>>>> Cc: Simon Marlow; ghc-devs
>> >>>>>>>>> Subject: Re: ArrayArrays
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> When (ab)using them for this purpose, SmallArrayArray's would be
>> >>>>>>>>> very handy as well.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Consider right now if I have something like an order-maintenance
>> >>>>>>>>> structure I have:
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> data Upper s = Upper {-# UNPACK #-} !(MutableByteArray s) {-#
>> >>>>>>>>> UNPACK #-} !(MutVar s (Upper s)) {-# UNPACK #-} !(MutVar s
>> >>>>>>>>> (Upper s))
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> data Lower s = Lower {-# UNPACK #-} !(MutVar s (Upper s)) {-#
>> >>>>>>>>> UNPACK #-} !(MutableByteArray s) {-# UNPACK #-} !(MutVar s
>> >>>>>>>>> (Lower s)) {-#
>> >>>>>>>>> UNPACK #-} !(MutVar s (Lower s))
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> The former contains, logically, a mutable integer and two
>> >>>>>>>>> pointers,
>> >>>>>>>>> one for forward and one for backwards. The latter is basically
>> >>>>>>>>> the same
>> >>>>>>>>> thing with a mutable reference up pointing at the structure
>> >>>>>>>>> above.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> On the heap this is an object that points to a structure for the
>> >>>>>>>>> bytearray, and points to another structure for each mutvar which
>> >>>>>>>>> each point
>> >>>>>>>>> to the other 'Upper' structure. So there is a level of
>> >>>>>>>>> indirection smeared
>> >>>>>>>>> over everything.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> So this is a pair of doubly linked lists with an upward link
>> >>>>>>>>> from
>> >>>>>>>>> the structure below to the structure above.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Converted into ArrayArray#s I'd get
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> data Upper s = Upper (MutableArrayArray# s)
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> w/ the first slot being a pointer to a MutableByteArray#, and
>> >>>>>>>>> the
>> >>>>>>>>> next 2 slots pointing to the previous and next previous objects,
>> >>>>>>>>> represented
>> >>>>>>>>> just as their MutableArrayArray#s. I can use
>> >>>>>>>>> sameMutableArrayArray# on these
>> >>>>>>>>> for object identity, which lets me check for the ends of the
>> >>>>>>>>> lists by tying
>> >>>>>>>>> things back on themselves.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> and below that
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> data Lower s = Lower (MutableArrayArray# s)
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> is similar, with an extra MutableArrayArray slot pointing up to
>> >>>>>>>>> an
>> >>>>>>>>> upper structure.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> I can then write a handful of combinators for getting out the
>> >>>>>>>>> slots
>> >>>>>>>>> in question, while it has gained a level of indirection between
>> >>>>>>>>> the wrapper
>> >>>>>>>>> to put it in * and the MutableArrayArray# s in #, that one can
>> >>>>>>>>> be basically
>> >>>>>>>>> erased by ghc.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Unlike before I don't have several separate objects on the heap
>> >>>>>>>>> for
>> >>>>>>>>> each thing. I only have 2 now. The MutableArrayArray# for the
>> >>>>>>>>> object itself,
>> >>>>>>>>> and the MutableByteArray# that it references to carry around the
>> >>>>>>>>> mutable
>> >>>>>>>>> int.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> The only pain points are
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> 1.) the aforementioned limitation that currently prevents me
>> >>>>>>>>> from
>> >>>>>>>>> stuffing normal boxed data through a SmallArray or Array into an
>> >>>>>>>>> ArrayArray
>> >>>>>>>>> leaving me in a little ghetto disconnected from the rest of
>> >>>>>>>>> Haskell,
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> and
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> 2.) the lack of SmallArrayArray's, which could let us avoid the
>> >>>>>>>>> card marking overhead. These objects are all small, 3-4 pointers
>> >>>>>>>>> wide. Card
>> >>>>>>>>> marking doesn't help.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> Alternately I could just try to do really evil things and
>> >>>>>>>>> convert
>> >>>>>>>>> the whole mess to SmallArrays and then figure out how to
>> >>>>>>>>> unsafeCoerce my way
>> >>>>>>>>> to glory, stuffing the #'d references to the other arrays
>> >>>>>>>>> directly into the
>> >>>>>>>>> SmallArray as slots, removing the limitation  we see here by
>> >>>>>>>>> aping the
>> >>>>>>>>> MutableArrayArray# s API, but that gets really really dangerous!
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> I'm pretty much willing to sacrifice almost anything on the
>> >>>>>>>>> altar
>> >>>>>>>>> of speed here, but I'd like to be able to let the GC move them
>> >>>>>>>>> and collect
>> >>>>>>>>> them which rules out simpler Ptr and Addr based solutions.
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> -Edward
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> On Thu, Aug 20, 2015 at 9:01 PM, Manuel M T Chakravarty
>> >>>>>>>>> <chak at cse.unsw.edu.au<mailto:chak at cse.unsw.edu.au>> wrote:
>> >>>>>>>>>
>> >>>>>>>>> That’s an interesting idea.
>> >>>>>>>>>
>> >>>>>>>>> Manuel
>> >>>>>>>>>
>> >>>>>>>>> > Edward Kmett <ekmett at gmail.com<mailto:ekmett at gmail.com>>:
>> >>>>>>>>>
>> >>>>>>>>> >
>> >>>>>>>>> > Would it be possible to add unsafe primops to add Array# and
>> >>>>>>>>> > SmallArray# entries to an ArrayArray#? The fact that the
>> >>>>>>>>> > ArrayArray# entries
>> >>>>>>>>> > are all directly unlifted avoiding a level of indirection for
>> >>>>>>>>> > the containing
>> >>>>>>>>> > structure is amazing, but I can only currently use it if my
>> >>>>>>>>> > leaf level data
>> >>>>>>>>> > can be 100% unboxed and distributed among ByteArray#s. It'd be
>> >>>>>>>>> > nice to be
>> >>>>>>>>> > able to have the ability to put SmallArray# a stuff down at
>> >>>>>>>>> > the leaves to
>> >>>>>>>>> > hold lifted contents.
>> >>>>>>>>> >
>> >>>>>>>>> > I accept fully that if I name the wrong type when I go to
>> >>>>>>>>> > access
>> >>>>>>>>> > one of the fields it'll lie to me, but I suppose it'd do that
>> >>>>>>>>> > if i tried to
>> >>>>>>>>> > use one of the members that held a nested ArrayArray# as a
>> >>>>>>>>> > ByteArray#
>> >>>>>>>>> > anyways, so it isn't like there is a safety story preventing
>> >>>>>>>>> > this.
>> >>>>>>>>> >
>> >>>>>>>>> > I've been hunting for ways to try to kill the indirection
>> >>>>>>>>> > problems I get with Haskell and mutable structures, and I
>> >>>>>>>>> > could shoehorn a
>> >>>>>>>>> > number of them into ArrayArrays if this worked.
>> >>>>>>>>> >
>> >>>>>>>>> > Right now I'm stuck paying for 2 or 3 levels of unnecessary
>> >>>>>>>>> > indirection compared to c/java and this could reduce that pain
>> >>>>>>>>> > to just 1
>> >>>>>>>>> > level of unnecessary indirection.
>> >>>>>>>>> >
>> >>>>>>>>> > -Edward
>> >>>>>>>>>
>> >>>>>>>>> > _______________________________________________
>> >>>>>>>>> > ghc-devs mailing list
>> >>>>>>>>> > ghc-devs at haskell.org<mailto:ghc-devs at haskell.org>
>> >>>>>>>>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>>
>> >>>>>>>>> _______________________________________________
>> >>>>>>>>> ghc-devs mailing list
>> >>>>>>>>> ghc-devs at haskell.org<mailto:ghc-devs at haskell.org>
>> >>>>>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>> >>>>>>>
>> >>>>>>>
>> >>>>>
>> >>>
>> >>
>> >
>> >
>> > _______________________________________________
>> > ghc-devs mailing list
>> > ghc-devs at haskell.org<mailto:ghc-devs at haskell.org>
>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>> >
>
>



_______________________________________________
ghc-devs mailing list
ghc-devs at haskell.org<mailto:ghc-devs at haskell.org>
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20150907/772a08e5/attachment-0001.html>