Ryan: would an unboxed value Mvar, Eg to write StrictMvar (), avoid creating extra gc pressure / traversal a?
On Thu, Oct 15, 2020 at 4:23 PM Ryan Yates <fryguy...@gmail.com> wrote: > 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. > > > > On Thu, Oct 15, 2020 at 4:08 PM David Feuer <david.fe...@gmail.com> wrote: > >> 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. >> >> On Thu, Oct 15, 2020, 1:10 PM Ryan Yates <fryguy...@gmail.com> wrote: >> >>> 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. >>> >>> On Thu, Oct 15, 2020 at 12:59 PM David Feuer <david.fe...@gmail.com> >>> wrote: >>> >>>> 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. >>>> >>>> On Thu, Oct 15, 2020, 12:50 PM Carter Schonwald < >>>> carter.schonw...@gmail.com> wrote: >>>> >>>>> 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. >>>>> >>>>> On Thu, Oct 15, 2020 at 11:58 AM David Feuer <david.fe...@gmail.com> >>>>> wrote: >>>>> >>>>>> Sorry, unlifted, not unboxed... >>>>>> >>>>>> On Thu, Oct 15, 2020, 11:57 AM David Feuer <david.fe...@gmail.com> >>>>>> wrote: >>>>>> >>>>>>> Putting unboxed things in TVar, MVar, etc., is part of Andrew >>>>>>> Martin's accepted BoxedRep proposal. >>>>>>> >>>>>>> On Thu, Oct 15, 2020, 11:44 AM Carter Schonwald < >>>>>>> carter.schonw...@gmail.com> wrote: >>>>>>> >>>>>>>> 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.andr...@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.thadd...@gmail.com> >>>>>>>>> Date: Wed, Oct 14, 2020, 4:14 PM >>>>>>>>> Subject: Re: Restricted sums in BoxedRep >>>>>>>>> To: David Feuer <david.fe...@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.fe...@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@haskell.orghttp://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs >>>>>>>>> >>>>>>>>> >>>>>>>>> _______________________________________________ >>>>>>>>> ghc-devs mailing list >>>>>>>>> ghc-devs@haskell.org >>>>>>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs >>>>>>>>> >>>>>>>> _______________________________________________ >>>> ghc-devs mailing list >>>> ghc-devs@haskell.org >>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs >>>> >>>
_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs