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