ArrayArrays

Tue Sep 1 06:50:14 UTC 2015

Works for me.

On Mon, Aug 31, 2015 at 10:14 PM, Johan Tibell <johan.tibell at gmail.com>
wrote:

> Works for me.
>
> On Mon, Aug 31, 2015 at 3:50 PM, Ryan Yates <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> 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> 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>
>> >> 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>
>> 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>
>> 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
>> >>>>>> >> >
>> >>>>>> >
>> >>>>>> >
>> >>>>>
>> >>>>>
>> >>>>
>> >>>>
>> >>>> _______________________________________________
>> >>>> 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/20150831/830060aa/attachment-0001.html>