Re: Restricted sums in BoxedRep

[Spiwack, Arnaud]

I may have misunderstood, but my understanding is the following:

- Since a is a boxed type, it can never be the null pointer
- So I can use a null pointer unambiguously

Let's call this null-pointer expanded type, `Nullable# a`, it is now a
different sort than `a`, since it can have the null pointer in it. Is that
still what you wish for? The risk being that combining such a `Nullable# a`
with another data structure may very well require an additional boxing,
which is what, I believe, you were trying to avoid.

/Arnaud

On Tue, Oct 13, 2020 at 11:47 PM David Feuer  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?
> ___
> 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

Re: Restricted sums in BoxedRep

[Sebastian Graf]

I believe Simon told me once that NULL pointers in places we assume
BoxedRep things are not an option, because the GC assumes it is free to
follow that pointer. It won't check if it's NULL or not.
That's also the reason why we lower `LitRubbish` (which we use for absent
BoxedRep literals) as `()` when going to STG

-- We can't use NULL, so supply an arbitrary (untyped!) closure that we
know can be followed by the GC.

Am Mi., 14. Okt. 2020 um 13:46 Uhr schrieb Spiwack, Arnaud <
arnaud.spiw...@tweag.io>:

> I may have misunderstood, but my understanding is the following:
>
> - Since a is a boxed type, it can never be the null pointer
> - So I can use a null pointer unambiguously
>
> Let's call this null-pointer expanded type, `Nullable# a`, it is now a
> different sort than `a`, since it can have the null pointer in it. Is that
> still what you wish for? The risk being that combining such a `Nullable# a`
> with another data structure may very well require an additional boxing,
> which is what, I believe, you were trying to avoid.
>
> /Arnaud
>
> On Tue, Oct 13, 2020 at 11:47 PM David Feuer 
> 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?
>> ___
>> 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

Re: Restricted sums in BoxedRep

[Spiwack, Arnaud]

I don't imagine it would be hard for the GC to check that a pointer is null
before following it. The argument may be, though, that it's too high a
price to pay for the occasional use of a null pointer. (I must add that I
have no opinion, or idea really, on this)

On Wed, Oct 14, 2020 at 1:54 PM Sebastian Graf  wrote:

> I believe Simon told me once that NULL pointers in places we assume
> BoxedRep things are not an option, because the GC assumes it is free to
> follow that pointer. It won't check if it's NULL or not.
> That's also the reason why we lower `LitRubbish` (which we use for absent
> BoxedRep literals) as `()` when going to STG
> 
> -- We can't use NULL, so supply an arbitrary (untyped!) closure that we
> know can be followed by the GC.
>
> Am Mi., 14. Okt. 2020 um 13:46 Uhr schrieb Spiwack, Arnaud <
> arnaud.spiw...@tweag.io>:
>
>> I may have misunderstood, but my understanding is the following:
>>
>> - Since a is a boxed type, it can never be the null pointer
>> - So I can use a null pointer unambiguously
>>
>> Let's call this null-pointer expanded type, `Nullable# a`, it is now a
>> different sort than `a`, since it can have the null pointer in it. Is that
>> still what you wish for? The risk being that combining such a `Nullable# a`
>> with another data structure may very well require an additional boxing,
>> which is what, I believe, you were trying to avoid.
>>
>> /Arnaud
>>
>> On Tue, Oct 13, 2020 at 11:47 PM David Feuer 
>> 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?
>>> ___
>>> 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

Re: Restricted sums in BoxedRep

[David Feuer]

I don't know your terminology, sorry. By "null" I'm referring to something
distinguished, of which there can be more than one. These can be pointers
to statically allocated objects if necessary, though pointers in an unused
address range would probably be nicer. My goal is to be able to shove a
compact representation of something like (# (##) | (##) | (##) | a #) into
an array/MutVar/etc., rather than needing to box it to do so.

On Wed, Oct 14, 2020, 7:45 AM Spiwack, Arnaud 
wrote:

> I may have misunderstood, but my understanding is the following:
>
> - Since a is a boxed type, it can never be the null pointer
> - So I can use a null pointer unambiguously
>
> Let's call this null-pointer expanded type, `Nullable# a`, it is now a
> different sort than `a`, since it can have the null pointer in it. Is that
> still what you wish for? The risk being that combining such a `Nullable# a`
> with another data structure may very well require an additional boxing,
> which is what, I believe, you were trying to avoid.
>
> /Arnaud
>
> On Tue, Oct 13, 2020 at 11:47 PM David Feuer 
> 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?
>> ___
>> 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

Re: Restricted sums in BoxedRep

[Spiwack, Arnaud]

Ok, I believe get it now,

Let's imagine (to take only the simplest case) that we have a `Nullable# a`
type, such that `Nullable# a = (# (##) | a #)`. What would be the kind of
`Nullable#`? I imagine that it would be something like `TYPE (BoxedRep
Lifted) -> TYPE (BoxedRep Nullable)`.

Then you would want to abstract the type of arrays/tvars/whatnot from `Type
-> Type` to `forall r. TYPE (BoxRep r) -> Type`.

Is that a correct interpretation of your suggestion?

If so, my guess would be that all the above is fine, but I suspect (and I'm
quite a bit out of my comfort zone here) that there can be considerable
difficulties in implementing pattern-matching for such a type.
___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Re: Restricted sums in BoxedRep

[David Feuer]

Yes, I think you're getting the gist. Pattern matching with one or two
nulls is just an equality test or three. In practice, we'd want a fixed
number of evenly spaced nulls, allowing jump table techniques to be used
when there are more cases. We'd presumably have a hard limit for the number
of nulls a type is allowed to have.

On Wed, Oct 14, 2020, 10:29 AM Spiwack, Arnaud 
wrote:

> Ok, I believe get it now,
>
> Let's imagine (to take only the simplest case) that we have a `Nullable#
> a` type, such that `Nullable# a = (# (##) | a #)`. What would be the kind
> of `Nullable#`? I imagine that it would be something like `TYPE (BoxedRep
> Lifted) -> TYPE (BoxedRep Nullable)`.
>
> Then you would want to abstract the type of arrays/tvars/whatnot from
> `Type -> Type` to `forall r. TYPE (BoxRep r) -> Type`.
>
> Is that a correct interpretation of your suggestion?
>
> If so, my guess would be that all the above is fine, but I suspect (and
> I'm quite a bit out of my comfort zone here) that there can be considerable
> difficulties in implementing pattern-matching for such a type.
>
___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Perf test viewer

[Sylvain Henry]

Hello everyone,

Since testsuite performance results are stored into Git notes, they are 
more difficult to visualize. At least with values in .T files we could 
see the changes over time, but now increase/decrease are only indicated 
into commit messages (but not necessarily by how much). The only tool we 
have afaik is the perf_notes.py script [1] but it's not very interactive.


So, long story short, I've started another one which is more interactive 
(in the browser). An instance is running on my server: http://hsyl20.fr:4222


It should be updated every 2 hours with newer metrics/commits from CI. 
Sources are here: https://github.com/hsyl20/had


Any feedback/PR is welcome!

Cheers,
Sylvain

[1] 
https://gitlab.haskell.org/ghc/ghc/-/wikis/building/running-tests/performance-tests#comparing-commits



___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Fwd: Restricted sums in BoxedRep

[David Feuer]

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 
Date: Wed, Oct 14, 2020, 4:14 PM
Subject: Re: Restricted sums in BoxedRep
To: David Feuer 


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  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 list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

Re: Perf test viewer

[Ben Gamari]

Sylvain Henry  writes:

> Hello everyone,
>
> Since testsuite performance results are stored into Git notes, they are 
> more difficult to visualize. At least with values in .T files we could 
> see the changes over time, but now increase/decrease are only indicated 
> into commit messages (but not necessarily by how much). The only tool we 
> have afaik is the perf_notes.py script [1] but it's not very interactive.
>
> So, long story short, I've started another one which is more interactive 
> (in the browser). An instance is running on my server: http://hsyl20.fr:4222
>
Hi Sylvain,

This looks great!

I would also note that all of the performance metrics produced by the
testsuite, nofib, and (soon) head.hackage are preserved in a PostgreSQL
database on gitlab.haskell.org which can be accessed by way of Postgrest
[1]. The schema can be found here [2]. You will also find the import
tools in the same repository (but they are quite rough around the edges;
you have been warned).

The schema is probably most conveniently used via the `results_view`
view. For instance, one can request all metrics for commits in the last
month with:

$ curl 
https://perf.ghc.haskell.org/db/results_view?commit_date=gt.2020-09-01

Another useful view is `deltas`, which provides compares metrics for
pairs of commits. This I have found quite useful in spotting
regressions.

Apart from curl, there are a few other options for consuming this
information:

 * I have an Python notebook which has some convenient helpers for
   quickly plotting things in `ghc-utils` [3]. I find this option to
   have the greatest power/weight ratio for most use-cases.

 * There is an incredibly hacky attempt at a web interface here [4]
   (source here [5]) although it's probably best to bury this sad effort
  
 * Sometimes I have needed to fall back to SQL for some queries; if
   someone would find this useful we can arrange read-only SQL access on
   an individual basis.

Regardless, this project has been gradually evolving as the need arises
for the last few years. It's been quite useful but I think it's
potential is quite under-realized.

Cheers,

- Ben


[1] https://postgrest.org/
[2] https://github.com/bgamari/ghc-perf-import/blob/master/import/schema.sql
[3] https://github.com/bgamari/ghc-perf-import/blob/master/plot.ipynb
[4] http://home.smart-cactus.org/ghc-perf/
[5] https://github.com/bgamari/ghc-perf-import/tree/master/web


signature.asc
Description: PGP signature
___
ghc-devs mailing list
ghc-devs@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs