ArrayArrays

[Simon Peyton Jones]

OK Tuesday afternoon break!

S

From: ghc-devs [mailto:ghc-devs-bounces at haskell.org] On Behalf Of Johan Tibell
Sent: 01 September 2015 06:14
To: Ryan Yates
Cc: Simon Marlow; Manuel M T Chakravarty; Chao-Hong Chen; ghc-devs; Ryan Scott; Ryan Yates
Subject: Re: ArrayArrays

Works for me.

On Mon, Aug 31, 2015 at 3:50 PM, Ryan Yates <fryguybob at gmail.com<mailto:fryguybob at gmail.com>> wrote:
Any time works for me.

Ryan

On Mon, Aug 31, 2015 at 6:11 PM, Ryan Newton <rrnewton at gmail.com<mailto:rrnewton at gmail.com>> wrote:
> 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
>>>>
>>>
>>
>
> _______________________________________________
> 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/20150901/c9862e62/attachment-0001.html>