<div dir="ltr">Ah yes. In my research work I extended Mutable Constructor fields to allow a mutable array field to help with that problem. This allowed me to have a Nil constructor in a sum type and a Node constructor with normal fields as well as an array of mutable fields. Pointer tagging worked as expected so a case match on a dereference of a field would not need to follow the pointer and no intermediate objects were between Node objects.<div><br></div><div><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 15, 2020 at 4:08 PM David Feuer <<a href="mailto:david.feuer@gmail.com">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto">This might be lost in the noise for MVar and TVar, but for arrays, there are tremendous advantages to cutting out the extra heap objects. </div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 15, 2020, 1:10 PM Ryan Yates <<a href="mailto:fryguybob@gmail.com" target="_blank">fryguybob@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">I haven't been following this discussion too closely, but in my research work I found that some of the benefits that I wanted in this direction were already there with pointer tagging.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 15, 2020 at 12:59 PM David Feuer <<a href="mailto:david.feuer@gmail.com" rel="noreferrer" target="_blank">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto">Yes, that's something quite different. We'd need a whole different heap object type for such MVars and TVars. My approach covers the case where the unboxed thing can only take on a few values, for some value of "a few" which, depending on implementation, may or may not be very small. If the nulls point to actual heap objects in pre-allocated pinned memory (say), then up to 64 or so might be reasonable. If they point to "invalid" address space, then the numbers could go up a good bit.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 15, 2020, 12:50 PM Carter Schonwald <<a href="mailto:carter.schonwald@gmail.com" rel="noreferrer" target="_blank">carter.schonwald@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto">Indeed, I mean things that aren’t pointery, and could be represented by a tvar paired with a mutable byte array or mvar with mutable byte array, but which we’d want considered as a single heap object from the rts/gc perspective. </div><div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 15, 2020 at 11:58 AM David Feuer <<a href="mailto:david.feuer@gmail.com" rel="noreferrer noreferrer" target="_blank">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto">Sorry, unlifted, not unboxed...</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 15, 2020, 11:57 AM David Feuer <<a href="mailto:david.feuer@gmail.com" rel="noreferrer noreferrer" target="_blank">david.feuer@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto">Putting unboxed things in TVar, MVar, etc., is part of Andrew Martin's accepted BoxedRep proposal.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 15, 2020, 11:44 AM Carter Schonwald <<a href="mailto:carter.schonwald@gmail.com" rel="noreferrer noreferrer noreferrer" target="_blank">carter.schonwald@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div dir="auto">A related idea that came up recently and is perhaps simpler ties into this via the lens of having unboxed Mvars/tvars (even if it’s restricted to just things we can embed in a word64#)</div></div><div dir="auto"><br></div><div dir="auto">This came up in <div dir="auto"><a href="https://gitlab.haskell.org/ghc/ghc/-/issues/18798#note_307410" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank">https://gitlab.haskell.org/ghc/ghc/-/issues/18798#note_307410</a>, where viktor had millions of independent mvars holding what’s essentially a strict unit ()! </div><div dir="auto"><br></div><div dir="auto">The motivation in this later scenario is that in high concurrency settings, the less trivial stuff the gc needs to trace under updates, the better ghc scales. </div><div dir="auto"><br></div><div dir="auto">This may not be a use case david has in mind, but certainly seems related. </div><div dir="auto"><br></div><div dir="auto">Phrased more succinctly: gc perf dominates large heap / many core computation in Haskell via sensitivity to allocation volume / mutation volume (to ensure generational hypothesis stays valid), and providing tools to incrementally reduce the pressure with local changes would be good. </div><div dir="auto"><br></div><div dir="auto">So I’d propose / suggest that a baby step towards what david asks would be for us to work out some manner of unboxed tvar/mvar ref machinery that supports unboxed values. </div><div dir="auto"><br></div><div dir="auto"><br></div></div><div><div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Oct 15, 2020 at 5:32 AM Andreas Klebinger <<a href="mailto:klebinger.andreas@gmx.at" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank">klebinger.andreas@gmx.at</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div bgcolor="#FFFFFF">From a implementors
perspective my main questions would be:<br>
<br>
* How big is the benefit in practice? How many use cases are there?<br>
* How bad are the costs? (Runtime overhead, rts complexity, ...)<br>
<br>
The details of how this would be exposed to a user would are important.<br>
But if the costs are too high for the drawbacks then it becomes a moot
point.</div><div bgcolor="#FFFFFF"><br>
<br>
<span>David Feuer schrieb am 14.10.2020 um 22:21:</span><br>
<blockquote type="cite">
<div dir="auto">Forwarded from Andrew Martin below. I think we want
more than just Maybe (more than one null), but the nesting I described
is certainly more convenience than necessity.</div>
<br>
<div class="gmail_quote"><div dir="ltr" class="gmail_attr">----------
Forwarded message ---------<br>From: <strong class="gmail_sendername" dir="auto">Andrew Martin</strong> <span dir="auto"><<a href="mailto:andrew.thaddeus@gmail.com" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank">andrew.thaddeus@gmail.com</a>></span><br>Date:
Wed, Oct 14, 2020, 4:14 PM<br>Subject: Re: Restricted sums in BoxedRep<br>To:
David Feuer <<a href="mailto:david.feuer@gmail.com" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank">david.feuer@gmail.com</a>><br></div><br><br><div dir="ltr"><div>You'll have to forward this to the ghc-devs list to
share it with others since I'm not currently subscribed to it, but I've
had this same thought before. It is discussed at <a href="https://github.com/andrewthad/impure-containers/issues/12" rel="noreferrer noreferrer noreferrer noreferrer noreferrer" target="_blank">https://github.com/andrewthad/impure-containers/issues/12</a>.
Here's the relevant excerpt:</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><p>Relatedly, I was thinking the
other day that after finishing implementing <a href="https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0203-pointer-rep.rst" rel="noreferrer noreferrer noreferrer noreferrer noreferrer" target="_blank">https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0203-pointer-rep.rst</a>,
I should really look at seeing if it's possible to add this
maybe-of-a-lifted value trick straight to GHC. I think that with:</p>
<pre style="font-family:monospace"><code style="font-family:monospace">data RuntimpRep
= BoxedRep Levity
| MaybeBoxedRep Levity
| IntRep
| ...
data BuiltinMaybe :: forall (v :: Levity). TYPE v -> TYPE ('MaybeBoxedRep v)
</code></pre>
<p>This doesn't have the nesting issues because the kind system prevents
nesting. But anyway, back to the original question. I would recommend
not using <code style="font-family:monospace">Maybe.Unsafe</code> and using <code style="font-family:monospace">unpacked-maybe</code>
instead. The latter is definitely safe, and it only costs an extra
machine word of space in each data constructor it gets used in, and it
doesn't introduce more indirections.</p></div></blockquote></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Oct 13,
2020 at 5:47 PM David Feuer <<a href="mailto:david.feuer@gmail.com" rel="noreferrer noreferrer noreferrer noreferrer noreferrer" target="_blank">david.feuer@gmail.com</a>>
wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto">Null pointers are widely known to be a lousy language feature
in general, but there are certain situations where they're *really*
useful for compact representation. For example, we define<div dir="auto"><br></div><div dir="auto"> newtype TMVar a = TMVar (TVar (Maybe a))</div><div dir="auto"><br></div><div dir="auto">We don't, however, actually use the
fact that (Maybe a) is lifted. So we could represent this much more
efficiently using something like</div><div dir="auto"><br></div><div dir="auto"><span style="font-family:sans-serif"> newtype TMVar a =
TMVar (TVar a)</span><br></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><span style="font-family:sans-serif">where Nothing is represented by a
distinguished "null" pointer.</span></div><div dir="auto"><span style="font-family:sans-serif"><br></span></div><div dir="auto"><font face="sans-serif" style="font-family:sans-serif;color:rgb(0,0,0)">While it's possible to implement this sort of thing in
user code (with lots of fuss and care), it's not very nice at all. What
I'd really like to be able to do is represent certain kinds of sums
like this natively.</font></div><div dir="auto"><font face="sans-serif" style="font-family:sans-serif;color:rgb(0,0,0)"><br></font></div><div dir="auto"><font face="sans-serif" style="font-family:sans-serif;color:rgb(0,0,0)">Now that we're getting BoxedRep, I
think we can probably make it happen. The trick is to add a special
Levity constructor representing sums of particular shapes. Specifically,
we can represent a type like this if it is a possibly-nested sum which,
when flattened into a single sum, consists of some number of nullary
tuples and at most one Lifted or Unlifted type. Then we can have
(inline) primops to convert between the BoxedRep and the sum-of-sums
representations.</font></div><div dir="auto"><font face="sans-serif" style="font-family:sans-serif;color:rgb(0,0,0)"><br></font></div><div dir="auto"><font face="sans-serif" style="font-family:sans-serif;color:rgb(0,0,0)">Anyone have thoughts on details for
what the Levity constructor arguments might look like?</font></div></div></blockquote></div><br clear="all"><br>-- <br><div dir="ltr">-Andrew Thaddeus Martin</div>
</div>
<br>
<fieldset></fieldset>
<br>
<pre style="font-family:monospace">_______________________________________________
ghc-devs mailing list
<a href="mailto:ghc-devs@haskell.org" style="font-family:monospace" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank">ghc-devs@haskell.org</a>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" style="font-family:monospace" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a>
</pre>
</blockquote>
<br>
</div>
_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" rel="noreferrer noreferrer noreferrer noreferrer" target="_blank">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer noreferrer noreferrer noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
</blockquote></div></div>
</div>
</blockquote></div>
</blockquote></div>
</blockquote></div></div>
</blockquote></div>
_______________________________________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org" rel="noreferrer" target="_blank">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a><br>
</blockquote></div>
</blockquote></div>
</blockquote></div>