Fwd: Restricted sums in BoxedRep

[Carter Schonwald]

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#)

This came up in
https://gitlab.haskell.org/ghc/ghc/-/issues/18798#note_307410, where viktor
had millions of independent mvars holding what’s essentially a strict unit
()!

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.

This may not be a use case david has in mind, but certainly seems related.

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.

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.



On Thu, Oct 15, 2020 at 5:32 AM Andreas Klebinger <klebinger.andreas at gmx.at>
wrote:

> From a implementors perspective my main questions would be:
>
> * How big is the benefit in practice? How many use cases are there?
> * How bad are the costs? (Runtime overhead, rts complexity, ...)
>
> The details of how this would be exposed to a user would are important.
> But if the costs are too high for the drawbacks then it becomes a moot
> point.
>
>
> David Feuer schrieb am 14.10.2020 um 22:21:
>
> 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.
>
> ---------- Forwarded message ---------
> From: Andrew Martin <andrew.thaddeus at gmail.com>
> Date: Wed, Oct 14, 2020, 4:14 PM
> Subject: Re: Restricted sums in BoxedRep
> To: David Feuer <david.feuer at gmail.com>
>
>
> 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
> https://github.com/andrewthad/impure-containers/issues/12. Here's the
> relevant excerpt:
>
>> Relatedly, I was thinking the other day that after finishing implementing
>> https://github.com/ghc-proposals/ghc-proposals/blob/master/proposals/0203-pointer-rep.rst,
>> 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:
>>
>> data RuntimpRep
>>   = BoxedRep Levity
>>   | MaybeBoxedRep Levity
>>   | IntRep
>>   | ...
>>
>> data BuiltinMaybe :: forall (v :: Levity). TYPE v -> TYPE ('MaybeBoxedRep v)
>>
>> 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 Maybe.Unsafe and using unpacked-maybe 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.
>>
>
> On Tue, Oct 13, 2020 at 5:47 PM David Feuer <david.feuer at gmail.com> wrote:
>
>> 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
>>
>>     newtype TMVar a = TMVar (TVar (Maybe a))
>>
>> We don't, however, actually use the fact that (Maybe a) is lifted. So we
>> could represent this much more efficiently using something like
>>
>>     newtype TMVar a = TMVar (TVar a)
>>
>> where Nothing is represented by a distinguished "null" pointer.
>>
>> 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.
>>
>> 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.
>>
>> Anyone have thoughts on details for what the Levity constructor arguments
>> might look like?
>>
>
>
> --
> -Andrew Thaddeus Martin
>
>
> _______________________________________________
> ghc-devs mailing listghc-devs at haskell.orghttp://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/20201015/a145171e/attachment.html>