ArrayArrays

[Edward Kmett]

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> 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> 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> 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>
>> 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>
>> 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> 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>
>> 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>
>> 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>
>> >> >>> 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>
>> >> >>>> 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
>> >
>> >> >>>>> 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>
>> >> >>>>>> 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>
>> >> >>>>>>> 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> 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]
>> >> >>>>>>>>> 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> 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] 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> wrote:
>> >> >>>>>>>>>
>> >> >>>>>>>>> That’s an interesting idea.
>> >> >>>>>>>>>
>> >> >>>>>>>>> Manuel
>> >> >>>>>>>>>
>> >> >>>>>>>>> > Edward Kmett <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
>> >> >>>>>>>>> > http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>> >> >>>>>>>>>
>> >> >>>>>>>>>
>> >> >>>>>>>>>
>> >> >>>>>>>>>
>> >> >>>>>>>>>
>> >> >>>>>>>>> _______________________________________________
>> >> >>>>>>>>> ghc-devs mailing list
>> >> >>>>>>>>> ghc-devs at haskell.org
>> >> >>>>>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
>> >> >>>>>>>
>> >> >>>>>>>
>> >> >>>>>
>> >> >>>
>> >> >>
>> >> >
>> >> >
>> >> > _______________________________________________
>> >> > ghc-devs mailing list
>> >> > 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/20150829/75f28184/attachment-0001.html>