<div dir="ltr">Once you start to include all the other primitive types there is a bit more of an explosion. MVar#, TVar#, MutVar#, Small variants, etc. can all be modified to carry unlifted content. <div><br></div><div>Being able to be parametric over that choice would permit a number of things in user land to do the same thing with an open-ended set of design possibilities that are rather hard to contemplate in advance. e.g. being able to abstract over them could let you just use a normal (,) to carry around unlifted parametric data types or being able to talk about [MVar# s a] drastically reducing the number of one off data types we need to invent.</div><div><br></div><div>If you can talk about the machinery mentioned above then you can have typeclasses parameterized on an argument that could be either unlifted or lifted.<br><div><br></div><div><div>I'm not willing to fight too hard for it, but it feels more like the "right" solution than retaining a cut-and-paste copy of the same code and bifurcating further on each argument you want to consider such a degree of freedom.<br></div><div><br></div><div>As such it seems like a pretty big win for a comparatively minor change to the levity polymorphism machinery.</div><div><br></div></div><div><div>-Edward</div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Sep 8, 2015 at 3:40 AM, Simon Marlow <span dir="ltr"><<a href="mailto:marlowsd@gmail.com" target="_blank">marlowsd@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">This would be very cool, however it's questionable whether it's worth it.<br>
<br>
Without any unlifted kind, we need<br>
- ArrayArray#<br>
- a set of new/read/write primops for every element type,<br>
either built-in or made from unsafeCoerce#<br>
<br>
With the unlifted kind, we would need<br>
- ArrayArray#<br>
- one set of new/read/write primops<br>
<br>
With levity polymorphism, we would need<br>
- none of this, Array# can be used<br>
<br>
So having an unlifted kind already kills a lot of the duplication, polymorphism only kills a bit more.<br>
<br>
Cheers<br>
Simon<br>
<br>
On 08/09/2015 00:14, Edward Kmett wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Assume we had the ability to talk about Levity in a new way and instead<br>
of just:<br>
<br>
data Levity = Lifted | Unlifted<br>
<br>
type * = TYPE 'Lifted<br>
type # = TYPE 'Unlifted<br>
<br>
we replace had a more nuanced notion of TYPE parameterized on another<br>
data type:<br>
<br>
data Levity = Lifted | Unlifted<br>
data Param = Composite | Simple Levity<br>
<br>
and we parameterized TYPE with a Param rather than Levity.<br>
<br>
Existing strange representations can continue to live in TYPE 'Composite<br>
<br>
(# Int# , Double #) :: TYPE 'Composite<br>
<br>
and we don't support parametricity in there, just like, currently we<br>
don't allow parametricity in #.<br>
<br>
We can include the undefined example from Richard's talk:<br>
<br>
undefined :: forall (v :: Param). v<br>
<br>
and ultimately lift it into his pi type when it is available just as before.<br>
<br>
But we could let consider TYPE ('Simple 'Unlifted) as a form of<br>
'parametric #' covering unlifted things we're willing to allow<br>
polymorphism over because they are just pointers to something in the<br>
heap, that just happens to not be able to be _|_ or a thunk.<br>
<br>
In this setting, recalling that above, I modified Richard's TYPE to take<br>
a Param instead of Levity, we can define a type alias for things that<br>
live as a simple pointer to a heap allocated object:<br>
<br>
type GC (l :: Levity) = TYPE ('Simple l)<br>
type * = GC 'Lifted<br>
<br>
and then we can look at existing primitives generalized:<br>
<br>
Array# :: forall (l :: Levity) (a :: GC l). a -> GC 'Unlifted<br>
MutableArray# :: forall (l :: Levity) (a :: GC l). * -> a -> GC 'Unlifted<br>
SmallArray# :: forall (l :: Levity) (a :: GC l). a -> GC 'Unlifted<br>
SmallMutableArray# :: forall (l :: Levity) (a :: GC l). * -> a -> GC<br>
'Unlifted<br>
MutVar# :: forall (l :: Levity) (a :: GC l). * -> a -> GC 'Unlifted<br>
MVar# :: forall (l :: Levity) (a :: GC l). * -> a -> GC 'Unlifted<br>
<br>
Weak#, StablePtr#, StableName#, etc. all can take similar modifications.<br>
<br>
Recall that an ArrayArray# was just an Array# hacked up to be able to<br>
hold onto the subset of # that is collectable.<br>
<br>
Almost all of the operations on these data types can work on the more<br>
general kind of argument.<br>
<br>
newArray# :: forall (s :: *) (l :: Levity) (a :: GC l). Int# -> a -><br>
State# s -> (# State# s, MutableArray# s a #)<br>
<br>
writeArray# :: forall (s :: *) (l :: Levity) (a :: GC l). MutableArray#<br>
s a -> Int# -> a -> State# s -> State# s<br>
<br>
readArray# :: forall (s :: *) (l :: Levity) (a :: GC l). MutableArray# s<br>
a -> Int# -> State# s -> (# State# s, a #)<br>
<br>
etc.<br>
<br>
Only a couple of our existing primitives _can't_ generalize this way.<br>
The one that leaps to mind is atomicModifyMutVar, which would need to<br>
stay constrained to only work on arguments in *, because of the way it<br>
operates.<br>
<br>
With that we can still talk about<br>
<br>
MutableArray# s Int<br>
<br>
but now we can also talk about:<br>
<br>
MutableArray# s (MutableArray# s Int)<br>
<br>
without the layer of indirection through a box in * and without an<br>
explosion of primops. The same newFoo, readFoo, writeFoo machinery works<br>
for both kinds.<br>
<br>
The struct machinery doesn't get to take advantage of this, but it would<br>
let us clean house elsewhere in Prim and drastically improve the range<br>
of applicability of the existing primitives with nothing more than a<br>
small change to the levity machinery.<br>
<br>
I'm not attached to any of the names above, I coined them just to give<br>
us a concrete thing to talk about.<br>
<br>
Here I'm only proposing we extend machinery in GHC.Prim this way, but an<br>
interesting 'now that the barn door is open' question is to consider<br>
that our existing Haskell data types often admit a similar form of<br>
parametricity and nothing in principle prevents this from working for<br>
Maybe or [] and once you permit inference to fire across all of GC l<br>
then it seems to me that you'd start to get those same capabilities<br>
there as well when LevityPolymorphism was turned on.<br>
<br>
-Edward<br>
<br>
On Mon, Sep 7, 2015 at 5:56 PM, Simon Peyton Jones<br>
<<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a> <mailto:<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a>>> wrote:<br>
<br>
This could make the menagerie of ways to pack<br>
{Small}{Mutable}Array{Array}# references into a<br>
{Small}{Mutable}Array{Array}#' actually typecheck soundly, reducing<br>
the need for folks to descend into the use of the more evil<br>
structure primitives we're talking about, and letting us keep a few<br>
more principles around us.____<br>
<br>
__ __<br>
<br>
I’m lost. Can you give some concrete examples that illustrate how<br>
levity polymorphism will help us?____<br>
<br>
<br>
Simon____<br>
<br>
__ __<br>
<br>
*From:*Edward Kmett [mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a> <mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>>]<br>
*Sent:* 07 September 2015 21:17<br>
*To:* Simon Peyton Jones<br>
*Cc:* Ryan Newton; Johan Tibell; Simon Marlow; Manuel M T<br>
Chakravarty; Chao-Hong Chen; ghc-devs; Ryan Scott; Ryan Yates<br>
*Subject:* Re: ArrayArrays____<br>
<br>
__ __<br>
<br>
I had a brief discussion with Richard during the Haskell Symposium<br>
about how we might be able to let parametricity help a bit in<br>
reducing the space of necessarily primops to a slightly more<br>
manageable level. ____<br>
<br>
__ __<br>
<br>
Notably, it'd be interesting to explore the ability to allow<br>
parametricity over the portion of # that is just a gcptr.____<br>
<br>
__ __<br>
<br>
We could do this if the levity polymorphism machinery was tweaked a<br>
bit. You could envision the ability to abstract over things in both<br>
* and the subset of # that are represented by a gcptr, then<br>
modifying the existing array primitives to be parametric in that<br>
choice of levity for their argument so long as it was of a "heap<br>
object" levity.____<br>
<br>
__ __<br>
<br>
This could make the menagerie of ways to pack<br>
{Small}{Mutable}Array{Array}# references into a<br>
{Small}{Mutable}Array{Array}#' actually typecheck soundly, reducing<br>
the need for folks to descend into the use of the more evil<br>
structure primitives we're talking about, and letting us keep a few<br>
more principles around us.____<br>
<br>
__ __<br>
<br>
Then in the cases like `atomicModifyMutVar#` where it needs to<br>
actually be in * rather than just a gcptr, due to the constructed<br>
field selectors it introduces on the heap then we could keep the<br>
existing less polymorphic type.____<br>
<br>
__ __<br>
<br>
-Edward____<br>
<br>
__ __<br>
<br>
On Mon, Sep 7, 2015 at 9:59 AM, Simon Peyton Jones<br>
<<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a> <mailto:<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a>>> wrote:____<br>
<br>
It was fun to meet and discuss this.____<br>
<br>
____<br>
<br>
Did someone volunteer to write a wiki page that describes the<br>
proposed design? And, I earnestly hope, also describes the<br>
menagerie of currently available array types and primops so that<br>
users can have some chance of picking the right one?!____<br>
<br>
____<br>
<br>
Thanks____<br>
<br>
____<br>
<br>
Simon____<br>
<br>
____<br>
<br>
*From:*ghc-devs [mailto:<a href="mailto:ghc-devs-bounces@haskell.org" target="_blank">ghc-devs-bounces@haskell.org</a><br>
<mailto:<a href="mailto:ghc-devs-bounces@haskell.org" target="_blank">ghc-devs-bounces@haskell.org</a>>] *On Behalf Of *Ryan Newton<br>
*Sent:* 31 August 2015 23:11<br>
*To:* Edward Kmett; Johan Tibell<br>
*Cc:* Simon Marlow; Manuel M T Chakravarty; Chao-Hong Chen;<br>
ghc-devs; Ryan Scott; Ryan Yates<br>
*Subject:* Re: ArrayArrays____<br>
<br>
____<br>
<br>
Dear Edward, Ryan Yates, and other interested parties -- ____<br>
<br>
____<br>
<br>
So when should we meet up about this?____<br>
<br>
____<br>
<br>
May I propose the Tues afternoon break for everyone at ICFP who<br>
is interested in this topic? We can meet out in the coffee area<br>
and congregate around Edward Kmett, who is tall and should be<br>
easy to find ;-).____<br>
<br>
____<br>
<br>
I think Ryan is going to show us how to use his new primops for<br>
combined array + other fields in one heap object?____<br>
<br>
____<br>
<br>
On Sat, Aug 29, 2015 at 9:24 PM Edward Kmett <<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a><br>
<mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>>> wrote:____<br>
<br>
Without a custom primitive it doesn't help much there, you<br>
have to store the indirection to the mask.____<br>
<br>
____<br>
<br>
With a custom primitive it should cut the on heap<br>
root-to-leaf path of everything in the HAMT in half. A<br>
shorter HashMap was actually one of the motivating factors<br>
for me doing this. It is rather astoundingly difficult to<br>
beat the performance of HashMap, so I had to start cheating<br>
pretty badly. ;)____<br>
<br>
____<br>
<br>
-Edward____<br>
<br>
____<br>
<br>
On Sat, Aug 29, 2015 at 5:45 PM, Johan Tibell<br>
<<a href="mailto:johan.tibell@gmail.com" target="_blank">johan.tibell@gmail.com</a> <mailto:<a href="mailto:johan.tibell@gmail.com" target="_blank">johan.tibell@gmail.com</a>>><br>
wrote:____<br>
<br>
I'd also be interested to chat at ICFP to see if I can<br>
use this for my HAMT implementation.____<br>
<br>
____<br>
<br>
On Sat, Aug 29, 2015 at 3:07 PM, Edward Kmett<br>
<<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a> <mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>>> wrote:____<br>
<br>
Sounds good to me. Right now I'm just hacking up<br>
composable accessors for "typed slots" in a fairly<br>
lens-like fashion, and treating the set of slots I<br>
define and the 'new' function I build for the data<br>
type as its API, and build atop that. This could<br>
eventually graduate to template-haskell, but I'm not<br>
entirely satisfied with the solution I have. I<br>
currently distinguish between what I'm calling<br>
"slots" (things that point directly to another<br>
SmallMutableArrayArray# sans wrapper) and "fields"<br>
which point directly to the usual Haskell data types<br>
because unifying the two notions meant that I<br>
couldn't lift some coercions out "far enough" to<br>
make them vanish.____<br>
<br>
____<br>
<br>
I'll be happy to run through my current working set<br>
of issues in person and -- as things get nailed down<br>
further -- in a longer lived medium than in personal<br>
conversations. ;)____<br>
<br>
____<br>
<br>
-Edward____<br>
<br>
____<br>
<br>
On Sat, Aug 29, 2015 at 7:59 AM, Ryan Newton<br>
<<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a> <mailto:<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>>><br>
wrote:____<br>
<br>
I'd also love to meet up at ICFP and discuss<br>
this. I think the array primops plus a TH layer<br>
that lets (ab)use them many times without too<br>
much marginal cost sounds great. And I'd like<br>
to learn how we could be either early users of,<br>
or help with, this infrastructure.____<br>
<br>
____<br>
<br>
CC'ing in Ryan Scot and Omer Agacan who may also<br>
be interested in dropping in on such discussions<br>
@ICFP, and Chao-Hong Chen, a Ph.D. student who<br>
is currently working on concurrent data<br>
structures in Haskell, but will not be at ICFP.____<br>
<br>
____<br>
<br>
____<br>
<br>
On Fri, Aug 28, 2015 at 7:47 PM, Ryan Yates<br>
<<a href="mailto:fryguybob@gmail.com" target="_blank">fryguybob@gmail.com</a><br>
<mailto:<a href="mailto:fryguybob@gmail.com" target="_blank">fryguybob@gmail.com</a>>> wrote:____<br>
<br>
I completely agree. I would love to spend<br>
some time during ICFP and<br>
friends talking about what it could look<br>
like. My small array for STM<br>
changes for the RTS can be seen here [1].<br>
It is on a branch somewhere<br>
between 7.8 and 7.10 and includes irrelevant<br>
STM bits and some<br>
confusing naming choices (sorry), but should<br>
cover all the details<br>
needed to implement it for a non-STM<br>
context. The biggest surprise<br>
for me was following small array too closely<br>
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]:<br>
<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>
<br>
On Fri, Aug 28, 2015 at 10:09 PM, Edward<br>
Kmett <<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a><br>
<mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>>> wrote:<br>
> I'd love to have that last 10%, but its a<br>
lot of work to get there and more<br>
> importantly I don't know quite what it<br>
should look like.<br>
><br>
> On the other hand, I do have a pretty<br>
good idea of how the primitives above<br>
> could be banged out and tested in a long<br>
evening, well in time for 7.12. And<br>
> as noted earlier, those remain useful<br>
even if a nicer typed version with an<br>
> extra level of indirection to the sizes<br>
is built up after.<br>
><br>
> The rest sounds like a good graduate<br>
student project for someone who has<br>
> graduate students lying around. Maybe<br>
somebody at Indiana University who has<br>
> an interest in type theory and<br>
parallelism can find us one. =)<br>
><br>
> -Edward<br>
><br>
> On Fri, Aug 28, 2015 at 8:48 PM, Ryan<br>
Yates <<a href="mailto:fryguybob@gmail.com" target="_blank">fryguybob@gmail.com</a><br>
<mailto:<a href="mailto:fryguybob@gmail.com" target="_blank">fryguybob@gmail.com</a>>> wrote:<br>
>><br>
>> I think from my perspective, the<br>
motivation for getting the type<br>
>> checker involved is primarily bringing<br>
this to the level where users<br>
>> could be expected to build these<br>
structures. it is reasonable to<br>
>> think that there are people who want to<br>
use STM (a context with<br>
>> mutation already) to implement a<br>
straight forward data structure that<br>
>> avoids extra indirection penalty. There<br>
should be some places where<br>
>> knowing that things are field accesses<br>
rather then array indexing<br>
>> could be helpful, but I think GHC is<br>
good right now about handling<br>
>> constant offsets. In my code I don't do<br>
any bounds checking as I know<br>
>> I will only be accessing my arrays with<br>
constant indexes. I make<br>
>> wrappers for each field access and leave<br>
all the unsafe stuff in<br>
>> there. When things go wrong though, the<br>
compiler is no help. Maybe<br>
>> template Haskell that generates the<br>
appropriate wrappers is the right<br>
>> direction to go.<br>
>> There is another benefit for me when<br>
working with these as arrays in<br>
>> that it is quite simple and direct<br>
(given the hoops already jumped<br>
>> through) to play with alignment. I can<br>
ensure two pointers are never<br>
>> on the same cache-line by just spacing<br>
things out in the array.<br>
>><br>
>> On Fri, Aug 28, 2015 at 7:33 PM, Edward<br>
Kmett <<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a><br>
<mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>>> 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<br>
Newton <<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a><br>
<mailto:<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>>> wrote:<br>
>> ><br>
>> > You presumably also save a bounds<br>
check on reads by hard-coding the<br>
>> > sizes?<br>
>> ><br>
>> > On Fri, Aug 28, 2015 at 3:39 PM,<br>
Edward Kmett <<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a><br>
<mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>>> wrote:<br>
>> >><br>
>> >> Also there are 4 different "things"<br>
here, basically depending on two<br>
>> >> independent questions:<br>
>> >><br>
>> >> a.) if you want to shove the sizes<br>
into the info table, and<br>
>> >> b.) if you want cardmarking.<br>
>> >><br>
>> >> Versions with/without cardmarking for<br>
different sizes can be done<br>
>> >> pretty<br>
>> >> easily, but as noted, the infotable<br>
variants are pretty invasive.<br>
>> >><br>
>> >> -Edward<br>
>> >><br>
>> >> On Fri, Aug 28, 2015 at 6:36 PM,<br>
Edward Kmett <<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a><br>
<mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>>> wrote:<br>
>> >>><br>
>> >>> Well, on the plus side you'd save 16<br>
bytes per object, which adds up<br>
>> >>> if<br>
>> >>> they were small enough and there are<br>
enough of them. You get a bit<br>
>> >>> better<br>
>> >>> locality of reference in terms of<br>
what fits in the first cache line of<br>
>> >>> them.<br>
>> >>><br>
>> >>> -Edward<br>
>> >>><br>
>> >>> On Fri, Aug 28, 2015 at 6:14 PM,<br>
Ryan Newton <<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a><br>
<mailto:<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>>><br>
>> >>> wrote:<br>
>> >>>><br>
>> >>>> Yes. And for the short term I can<br>
imagine places we will settle with<br>
>> >>>> arrays even if it means tracking<br>
lengths unnecessarily and<br>
>> >>>> unsafeCoercing<br>
>> >>>> pointers whose types don't actually<br>
match their siblings.<br>
>> >>>><br>
>> >>>> Is there anything to recommend the<br>
hacks mentioned for fixed sized<br>
>> >>>> array<br>
>> >>>> objects *other* than using them to<br>
fake structs? (Much to<br>
>> >>>> derecommend, as<br>
>> >>>> you mentioned!)<br>
>> >>>><br>
>> >>>> On Fri, Aug 28, 2015 at 3:07 PM<br>
Edward Kmett <<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a><br>
<mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>>><br>
>> >>>> wrote:<br>
>> >>>>><br>
>> >>>>> I think both are useful, but the<br>
one you suggest requires a lot more<br>
>> >>>>> plumbing and doesn't subsume all<br>
of the usecases of the other.<br>
>> >>>>><br>
>> >>>>> -Edward<br>
>> >>>>><br>
>> >>>>> On Fri, Aug 28, 2015 at 5:51 PM,<br>
Ryan Newton <<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a><br>
<mailto:<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>>><br>
>> >>>>> wrote:<br>
>> >>>>>><br>
>> >>>>>> So that primitive is an array<br>
like thing (Same pointed type,<br>
>> >>>>>> unbounded<br>
>> >>>>>> length) with extra payload.<br>
>> >>>>>><br>
>> >>>>>> I can see how we can do without<br>
structs if we have arrays,<br>
>> >>>>>> especially<br>
>> >>>>>> with the extra payload at front.<br>
But wouldn't the general solution<br>
>> >>>>>> for<br>
>> >>>>>> structs be one that that allows<br>
new user data type defs for #<br>
>> >>>>>> types?<br>
>> >>>>>><br>
>> >>>>>><br>
>> >>>>>><br>
>> >>>>>> On Fri, Aug 28, 2015 at 4:43 PM<br>
Edward Kmett <<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a><br>
<mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>>><br>
>> >>>>>> wrote:<br>
>> >>>>>>><br>
>> >>>>>>> Some form of MutableStruct# with<br>
a known number of words and a<br>
>> >>>>>>> known<br>
>> >>>>>>> number of pointers is basically<br>
what Ryan Yates was suggesting<br>
>> >>>>>>> above, but<br>
>> >>>>>>> where the word counts were<br>
stored in the objects themselves.<br>
>> >>>>>>><br>
>> >>>>>>> Given that it'd have a couple of<br>
words for those counts it'd<br>
>> >>>>>>> likely<br>
>> >>>>>>> want to be something we build in<br>
addition to MutVar# rather than a<br>
>> >>>>>>> replacement.<br>
>> >>>>>>><br>
>> >>>>>>> On the other hand, if we had to<br>
fix those numbers and build info<br>
>> >>>>>>> tables that knew them, and<br>
typechecker support, for instance, it'd<br>
>> >>>>>>> get<br>
>> >>>>>>> rather invasive.<br>
>> >>>>>>><br>
>> >>>>>>> Also, a number of things that we<br>
can do with the 'sized' versions<br>
>> >>>>>>> above, like working with evil<br>
unsized c-style arrays directly<br>
>> >>>>>>> inline at the<br>
>> >>>>>>> end of the structure cease to be<br>
possible, so it isn't even a pure<br>
>> >>>>>>> win if we<br>
>> >>>>>>> did the engineering effort.<br>
>> >>>>>>><br>
>> >>>>>>> I think 90% of the needs I have<br>
are covered just by adding the one<br>
>> >>>>>>> primitive. The last 10% gets<br>
pretty invasive.<br>
>> >>>>>>><br>
>> >>>>>>> -Edward<br>
>> >>>>>>><br>
>> >>>>>>> On Fri, Aug 28, 2015 at 5:30 PM,<br>
Ryan Newton <<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a><br>
<mailto:<a href="mailto:rrnewton@gmail.com" target="_blank">rrnewton@gmail.com</a>>><br>
>> >>>>>>> wrote:<br>
>> >>>>>>>><br>
>> >>>>>>>> I like the possibility of a<br>
general solution for mutable structs<br>
>> >>>>>>>> (like Ed said), and I'm trying<br>
to fully understand why it's hard.<br>
>> >>>>>>>><br>
>> >>>>>>>> So, we can't unpack MutVar into<br>
constructors because of object<br>
>> >>>>>>>> identity problems. But what<br>
about directly supporting an<br>
>> >>>>>>>> extensible set of<br>
>> >>>>>>>> unlifted MutStruct# objects,<br>
generalizing (and even replacing)<br>
>> >>>>>>>> MutVar#? That<br>
>> >>>>>>>> may be too much work, but is it<br>
problematic otherwise?<br>
>> >>>>>>>><br>
>> >>>>>>>> Needless to say, this is also<br>
critical if we ever want best in<br>
>> >>>>>>>> class<br>
>> >>>>>>>> lockfree mutable structures,<br>
just like their Stm and sequential<br>
>> >>>>>>>> counterparts.<br>
>> >>>>>>>><br>
>> >>>>>>>> On Fri, Aug 28, 2015 at 4:43 AM<br>
Simon Peyton Jones<br>
>> >>>>>>>> <<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a><br>
<mailto:<a href="mailto:simonpj@microsoft.com" target="_blank">simonpj@microsoft.com</a>>> wrote:<br>
>> >>>>>>>>><br>
>> >>>>>>>>> At the very least I'll take<br>
this email and turn it into a short<br>
>> >>>>>>>>> article.<br>
>> >>>>>>>>><br>
>> >>>>>>>>> Yes, please do make it into a<br>
wiki page on the GHC Trac, 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<br>
[mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a><br>
<mailto:<a href="mailto:ekmett@gmail.com" target="_blank">ekmett@gmail.com</a>>]<br>
>> >>>>>>>>> Sent: 27 August 2015 16:54<br>
>> >>>>>>>>> To: Simon Peyton Jones<br>
>> >>>>>>>>> Cc: Manuel M T Chakravarty;<br>
Simon Marlow; ghc-devs<br>
>> >>>>>>>>> Subject: Re: ArrayArrays<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> An ArrayArray# is just an<br>
Array# with a modified invariant. It<br>
>> >>>>>>>>> points directly to other<br>
unlifted ArrayArray#'s or ByteArray#'s.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> While those live in #, they<br>
are garbage collected objects, so<br>
>> >>>>>>>>> this<br>
>> >>>>>>>>> all lives on the heap.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> They were added to make some<br>
of the DPH stuff fast when it has<br>
>> >>>>>>>>> to<br>
>> >>>>>>>>> deal with nested arrays.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> I'm currently abusing them as<br>
a placeholder for a better thing.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> The Problem<br>
>> >>>>>>>>><br>
>> >>>>>>>>> -----------------<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> Consider the scenario where<br>
you write a classic doubly-linked<br>
>> >>>>>>>>> list<br>
>> >>>>>>>>> in Haskell.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> data DLL = DLL (IORef (Maybe<br>
DLL) (IORef (Maybe DLL)<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> Chasing from one DLL to the<br>
next requires following 3 pointers<br>
>> >>>>>>>>> on<br>
>> >>>>>>>>> the heap.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> DLL ~> IORef (Maybe DLL) ~><br>
MutVar# RealWorld (Maybe DLL) ~><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<br>
unpacking the IORef with<br>
>> >>>>>>>>> -funbox-strict-fields or UNPACK<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> We can trim another by adding<br>
a 'Nil' constructor for DLL and<br>
>> >>>>>>>>> worsening our representation.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> data DLL = DLL !(IORef DLL)<br>
!(IORef DLL) | Nil<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> but now we're still stuck with<br>
a level of indirection<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> DLL ~> MutVar# RealWorld DLL<br>
~> DLL<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> This means that every<br>
operation we perform on this structure<br>
>> >>>>>>>>> will<br>
>> >>>>>>>>> be about half of the speed of<br>
an implementation in most other<br>
>> >>>>>>>>> languages<br>
>> >>>>>>>>> assuming we're memory bound on<br>
loading things into cache!<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> Making Progress<br>
>> >>>>>>>>><br>
>> >>>>>>>>> ----------------------<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> I have been working on a<br>
number of data structures where the<br>
>> >>>>>>>>> indirection of going from<br>
something in * out to an object in #<br>
>> >>>>>>>>> which<br>
>> >>>>>>>>> contains the real pointer to<br>
my target and coming back<br>
>> >>>>>>>>> effectively doubles<br>
>> >>>>>>>>> my runtime.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> We go out to the MutVar#<br>
because we are allowed to put the<br>
>> >>>>>>>>> MutVar#<br>
>> >>>>>>>>> onto the mutable list when we<br>
dirty it. There is a well defined<br>
>> >>>>>>>>> write-barrier.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> I could change out the<br>
representation to use<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> data DLL = DLL (MutableArray#<br>
RealWorld DLL) | Nil<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> I can just store two pointers<br>
in the MutableArray# every time,<br>
>> >>>>>>>>> but<br>
>> >>>>>>>>> this doesn't help _much_<br>
directly. It has reduced the amount of<br>
>> >>>>>>>>> distinct<br>
>> >>>>>>>>> addresses in memory I touch on<br>
a walk of the DLL from 3 per<br>
>> >>>>>>>>> object to 2.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> I still have to go out to the<br>
heap from my DLL and get to the<br>
>> >>>>>>>>> array<br>
>> >>>>>>>>> object and then chase it to<br>
the next DLL and chase that to the<br>
>> >>>>>>>>> next array. I<br>
>> >>>>>>>>> do get my two pointers<br>
together in memory though. I'm paying for<br>
>> >>>>>>>>> a card<br>
>> >>>>>>>>> marking table as well, which I<br>
don't particularly need with just<br>
>> >>>>>>>>> two<br>
>> >>>>>>>>> pointers, but we can shed that<br>
with the "SmallMutableArray#"<br>
>> >>>>>>>>> machinery added<br>
>> >>>>>>>>> back in 7.10, which is just<br>
the old array code a a new data<br>
>> >>>>>>>>> type, which can<br>
>> >>>>>>>>> speed things up a bit when you<br>
don't have very big arrays:<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> data DLL = DLL<br>
(SmallMutableArray# RealWorld DLL) | Nil<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> But what if I wanted my object<br>
itself to live in # and have two<br>
>> >>>>>>>>> mutable fields and be able to<br>
share the sme write barrier?<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> An ArrayArray# points directly<br>
to other unlifted array types.<br>
>> >>>>>>>>> What<br>
>> >>>>>>>>> if we have one # -> * wrapper<br>
on the outside to deal with the<br>
>> >>>>>>>>> impedence<br>
>> >>>>>>>>> mismatch between the<br>
imperative world and Haskell, and then just<br>
>> >>>>>>>>> let the<br>
>> >>>>>>>>> ArrayArray#'s hold other<br>
arrayarrays.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> data DLL = DLL<br>
(MutableArrayArray# RealWorld)<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> now I need to make up a new<br>
Nil, which I can just make be a<br>
>> >>>>>>>>> special<br>
>> >>>>>>>>> MutableArrayArray# I allocate<br>
on program startup. I can even<br>
>> >>>>>>>>> abuse pattern<br>
>> >>>>>>>>> synonyms. Alternately I can<br>
exploit the internals further to<br>
>> >>>>>>>>> make this<br>
>> >>>>>>>>> cheaper.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> Then I can use the<br>
readMutableArrayArray# and<br>
>> >>>>>>>>> writeMutableArrayArray# calls<br>
to directly access the preceding<br>
>> >>>>>>>>> and next<br>
>> >>>>>>>>> entry in the linked list.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> So now we have one DLL wrapper<br>
which just 'bootstraps me' into a<br>
>> >>>>>>>>> strict world, and everything<br>
there lives in #.<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> next :: DLL -> IO DLL<br>
>> >>>>>>>>><br>
>> >>>>>>>>> next (DLL m) = IO $ \s -> case<br>
readMutableArrayArray# s of<br>
>> >>>>>>>>><br>
>> >>>>>>>>> (# s', n #) -> (# s', DLL n #)<br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>><br>
>> >>>>>>>>> It turns out GHC is quite<br>
happy to optimize all of that code to<br>
>> >>>>>>>>> keep things unboxed. The 'DLL'<br>
wrappers get removed pretty<br>
>> >>>>>>>>> easily when they<br>
>> >>>>>>>>> are known strict and you chain</blockquote>
</blockquote></div><br></div>