Unpacking coercions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Unpacking coercions

David Feuer
I had an idea for how we might be able to unpack coercions in a limited and conservative way that doesn't get into the general problems of unpacking constraints. Would this make sense?

1. Move the definition of Coercion from Data.Type.Coercion to GHC.Magic

2. Magically change the type of the Coercion constructor from

  Coercion :: Coercible a b => Coercion a b

to

  Coercion :: a ~R# b => Coercion a b

Now a strict Coercion field will unpack to nothing.

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Unpacking coercions

Ryan Scott
If we can gain some performance from this, then I'm generally supportive of this idea.

I'm still of the belief that we could teach GHC to unpack boxed equality constraints, but your idea would definitely be the simpler one to implement.

Ryan S.

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

RE: Unpacking coercions

GHC - devs mailing list

It would be good to have a clear problem statement, plus an example of a program that runs more slowly than it “should”.

 

Simon

 

From: ghc-devs <[hidden email]> On Behalf Of Ryan Scott
Sent: 04 September 2018 14:02
To: [hidden email]
Subject: Re: Unpacking coercions

 

If we can gain some performance from this, then I'm generally supportive of this idea.

 

I'm still of the belief that we could teach GHC to unpack boxed equality constraints, but your idea would definitely be the simpler one to implement.

 

Ryan S.


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Unpacking coercions

Ryan Scott
In reply to this post by David Feuer
In case this wasn't clear, the context of this discussion in this GHC proposal [1], where David is trying to work around the fact that data types with existential Coercible constraints do not support unpacking. (By "unpacking", I mean putting an {-# UNPACK #-} pragma in front of a field of that type does what you would expect.)

An example program which demonstrates the performance issue can be found here [2]. That comment concerns unboxed equality vs. boxed equality, but the same unpacking problems that affect boxed equality also affect Coercible.

Ryan S.
-----

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

RE: Unpacking coercions

GHC - devs mailing list

Ah yes thanks.

 

As I suggest on that thread, I’d really like (someone) to try the “let’s make all evidence strict” idea.  I think it could be a perf win all round. 

 

And if so, we’d get what David wants for free.

 

Simon

 

From: ghc-devs <[hidden email]> On Behalf Of Ryan Scott
Sent: 04 September 2018 17:15
To: [hidden email]
Subject: Re: Unpacking coercions

 

In case this wasn't clear, the context of this discussion in this GHC proposal [1], where David is trying to work around the fact that data types with existential Coercible constraints do not support unpacking. (By "unpacking", I mean putting an {-# UNPACK #-} pragma in front of a field of that type does what you would expect.)

 

An example program which demonstrates the performance issue can be found here [2]. That comment concerns unboxed equality vs. boxed equality, but the same unpacking problems that affect boxed equality also affect Coercible.

 

Ryan S.

-----


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Unpacking coercions

Ryan Scott
In reply to this post by David Feuer
These aren't mutually exclusive ideas. While I'm sure there's many ways we could solve this problem, David's idea has the distinct advantage of being dead simple. I'd rather not block his vision on some other large refactor that may never materialize. (And if it _does_ materialize, we could revert any wiring-in of Coercible quite easily.)

Ryan S.

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

RE: Unpacking coercions

GHC - devs mailing list

Simple is good.  But what is this dead simple idea?

 

Perhaps: https://github.com/ghc-proposals/ghc-proposals/pull/116

But that proposal lists several possible alternatives.  Which one did you mean?

 

And all of them are language changes. Making evidence strict would require no language changes to solve the original problem.

 

Maybe this thread belongs with the proposal, unless I’m misunderstanding.

 

Simon

 

From: ghc-devs <[hidden email]> On Behalf Of Ryan Scott
Sent: 05 September 2018 15:15
To: [hidden email]
Subject: Re: Unpacking coercions

 

These aren't mutually exclusive ideas. While I'm sure there's many ways we could solve this problem, David's idea has the distinct advantage of being dead simple. I'd rather not block his vision on some other large refactor that may never materialize. (And if it _does_ materialize, we could revert any wiring-in of Coercible quite easily.)

 

Ryan S.


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Unpacking coercions

Ryan Scott
> Simple is good.  But what is this dead simple idea?

I'm referring to David's first e-mail on this thread: https://mail.haskell.org/pipermail/ghc-devs/2018-September/016191.html

All that would take is putting Coercion in TysWiredIn, and moving Coercion from Data.Type.Coercion to somewhere in ghc-prim.

> Maybe this thread belongs with the proposal, unless I’m misunderstanding.

I think the intention is to have that proposal (which proposes a language change) be superseded by this idea (which does not change the language).

Ryan S.


On Wed, Sep 5, 2018 at 10:20 AM, Simon Peyton Jones <[hidden email]> wrote:

Simple is good.  But what is this dead simple idea?

 

Perhaps: https://github.com/ghc-proposals/ghc-proposals/pull/116

But that proposal lists several possible alternatives.  Which one did you mean?

 

And all of them are language changes. Making evidence strict would require no language changes to solve the original problem.

 

Maybe this thread belongs with the proposal, unless I’m misunderstanding.

 

Simon

 

From: ghc-devs <[hidden email]> On Behalf Of Ryan Scott
Sent: 05 September 2018 15:15
To: [hidden email]
Subject: Re: Unpacking coercions

 

These aren't mutually exclusive ideas. While I'm sure there's many ways we could solve this problem, David's idea has the distinct advantage of being dead simple. I'd rather not block his vision on some other large refactor that may never materialize. (And if it _does_ materialize, we could revert any wiring-in of Coercible quite easily.)

 

Ryan S.



_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

RE: Unpacking coercions

GHC - devs mailing list

I think the intention is to have that proposal (which proposes a language change) be superseded by this idea (which does not change the language).

Oh, I did not know that.   I’ll ignore the proposal for now, in that case.

 

All that would take is putting Coercion in TysWiredIn, and moving Coercion from Data.Type.Coercion to somewhere in ghc-prim.

 

I don’t think it’s quite as simple as that.  Yes, we can wire it into the compiler; but we still need a module that defines the info table, curried data constructor etc for the type.  And we have no way to do that.

 

We could utterly lie and say

              data Coercion a b where

                  Coercion :: Coercion a a

 

That would generate the right bits in in the .o file, and we’d totally ignore the .hi file.  Gruesome but I think it would work.

 

 

But rather than all this circumlocution, why don’t we just make it possible to write ~# and ~R# directly.  Even if we dodge the need right now, it’ll surely come back.

 

If that is lexically tiresome, we could I suppose provide builtin-aliases for them, as if we had

              type NomEq# = (~#)

             type ReprEq# = (~R#)

 

Simon

 

From: Ryan Scott <[hidden email]>
Sent: 05 September 2018 15:26
To: Simon Peyton Jones <[hidden email]>
Cc: [hidden email]
Subject: Re: Unpacking coercions

 

> Simple is good.  But what is this dead simple idea?

 

I'm referring to David's first e-mail on this thread: https://mail.haskell.org/pipermail/ghc-devs/2018-September/016191.html

 

All that would take is putting Coercion in TysWiredIn, and moving Coercion from Data.Type.Coercion to somewhere in ghc-prim.

 

> Maybe this thread belongs with the proposal, unless I’m misunderstanding.

 

I think the intention is to have that proposal (which proposes a language change) be superseded by this idea (which does not change the language).

 

Ryan S.

 

 

On Wed, Sep 5, 2018 at 10:20 AM, Simon Peyton Jones <[hidden email]> wrote:

Simple is good.  But what is this dead simple idea?

 

Perhaps: https://github.com/ghc-proposals/ghc-proposals/pull/116

But that proposal lists several possible alternatives.  Which one did you mean?

 

And all of them are language changes. Making evidence strict would require no language changes to solve the original problem.

 

Maybe this thread belongs with the proposal, unless I’m misunderstanding.

 

Simon

 

From: ghc-devs <[hidden email]> On Behalf Of Ryan Scott
Sent: 05 September 2018 15:15
To: [hidden email]
Subject: Re: Unpacking coercions

 

These aren't mutually exclusive ideas. While I'm sure there's many ways we could solve this problem, David's idea has the distinct advantage of being dead simple. I'd rather not block his vision on some other large refactor that may never materialize. (And if it _does_ materialize, we could revert any wiring-in of Coercible quite easily.)

 

Ryan S.

 


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Unpacking coercions

Ryan Scott
> We could utterly lie and say
>
>               data Coercion a b where
>
>                   Coercion :: Coercion a a
>

>
> That would generate the right bits in in the .o file, and we’d totally ignore the .hi file.  Gruesome but I think it would work.

This was precisely what I had in mind. We already perform this trick for several things defined in ghc-prim (e.g., the (~) and (~~) classes), so this would just be another example of that.

> But rather than all this circumlocution, why don’t we just make it possible to write ~# and ~R# directly.  Even if we dodge the need right now, it’ll surely come back.

Hah, the reason David is suggesting his idea in the first place is to avoid having to do this! My understanding is that making it possible to write (~#) and (~R#) directly would involve quite a number of complications, as Richard's wiki entry on the subject [1] demonstrates.

That's not to say that I wouldn't like to see that happen some day. But a mere mortal like myself couldn't possibly implement this, whereas David's idea is actually within reach.

Ryan S.
-----

On Wed, Sep 5, 2018 at 10:45 AM, Simon Peyton Jones <[hidden email]> wrote:

I think the intention is to have that proposal (which proposes a language change) be superseded by this idea (which does not change the language).

Oh, I did not know that.   I’ll ignore the proposal for now, in that case.

 

All that would take is putting Coercion in TysWiredIn, and moving Coercion from Data.Type.Coercion to somewhere in ghc-prim.

 

I don’t think it’s quite as simple as that.  Yes, we can wire it into the compiler; but we still need a module that defines the info table, curried data constructor etc for the type.  And we have no way to do that.

 

We could utterly lie and say

              data Coercion a b where

                  Coercion :: Coercion a a

 

That would generate the right bits in in the .o file, and we’d totally ignore the .hi file.  Gruesome but I think it would work.

 

 

But rather than all this circumlocution, why don’t we just make it possible to write ~# and ~R# directly.  Even if we dodge the need right now, it’ll surely come back.

 

If that is lexically tiresome, we could I suppose provide builtin-aliases for them, as if we had

              type NomEq# = (~#)

             type ReprEq# = (~R#)

 

Simon

 

From: Ryan Scott <[hidden email]>
Sent: 05 September 2018 15:26
To: Simon Peyton Jones <[hidden email]>
Cc: [hidden email]
Subject: Re: Unpacking coercions

 

> Simple is good.  But what is this dead simple idea?

 

I'm referring to David's first e-mail on this thread: https://mail.haskell.org/pipermail/ghc-devs/2018-September/016191.html

 

All that would take is putting Coercion in TysWiredIn, and moving Coercion from Data.Type.Coercion to somewhere in ghc-prim.

 

> Maybe this thread belongs with the proposal, unless I’m misunderstanding.

 

I think the intention is to have that proposal (which proposes a language change) be superseded by this idea (which does not change the language).

 

Ryan S.

 

 

On Wed, Sep 5, 2018 at 10:20 AM, Simon Peyton Jones <[hidden email]> wrote:

Simple is good.  But what is this dead simple idea?

 

Perhaps: https://github.com/ghc-proposals/ghc-proposals/pull/116

But that proposal lists several possible alternatives.  Which one did you mean?

 

And all of them are language changes. Making evidence strict would require no language changes to solve the original problem.

 

Maybe this thread belongs with the proposal, unless I’m misunderstanding.

 

Simon

 

From: ghc-devs <[hidden email]> On Behalf Of Ryan Scott
Sent: 05 September 2018 15:15
To: [hidden email]
Subject: Re: Unpacking coercions

 

These aren't mutually exclusive ideas. While I'm sure there's many ways we could solve this problem, David's idea has the distinct advantage of being dead simple. I'd rather not block his vision on some other large refactor that may never materialize. (And if it _does_ materialize, we could revert any wiring-in of Coercible quite easily.)

 

Ryan S.

 



_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

Re: Unpacking coercions

Richard Eisenberg-4
I don't think that wiki reference is really about this problem.

Instead, I think that we'd need Constraint# to be able to offer users ~# and ~R#. The problem, then, is that there is no answer to this question: Constraint is to Type as Constraint# is to what? Currently, if ~# and ~R# are the only two generators of Constraint#, then Constraint# is like TYPE (TupleRep '[]). But I think wiring that in would be short-sighted.

Instead, this road leads to CONSTRAINT :: RuntimeRep -> Type, which is like TYPE. Today's Constraint would be CONSTRAINT LiftedRep. And we would have (~#), (~R#) :: forall k1 k2. k1 -> k2 -> CONSTRAINT (TupleRep '[]). In the Glorious Future, we'll have CONSTRAINT ~R TYPE, but we're not there yet. 

This all feel like the Right Answer to me, but it's unclear if we should start down this road before we have roles in kinds.

Richard
 
On Sep 5, 2018, at 10:54 AM, Ryan Scott <[hidden email]> wrote:

> We could utterly lie and say
>
>               data Coercion a b where
>
>                   Coercion :: Coercion a a
>

>
> That would generate the right bits in in the .o file, and we’d totally ignore the .hi file.  Gruesome but I think it would work.

This was precisely what I had in mind. We already perform this trick for several things defined in ghc-prim (e.g., the (~) and (~~) classes), so this would just be another example of that.

> But rather than all this circumlocution, why don’t we just make it possible to write ~# and ~R# directly.  Even if we dodge the need right now, it’ll surely come back.

Hah, the reason David is suggesting his idea in the first place is to avoid having to do this! My understanding is that making it possible to write (~#) and (~R#) directly would involve quite a number of complications, as Richard's wiki entry on the subject [1] demonstrates.

That's not to say that I wouldn't like to see that happen some day. But a mere mortal like myself couldn't possibly implement this, whereas David's idea is actually within reach.

Ryan S.
-----

On Wed, Sep 5, 2018 at 10:45 AM, Simon Peyton Jones <[hidden email]> wrote:

I think the intention is to have that proposal (which proposes a language change) be superseded by this idea (which does not change the language).

Oh, I did not know that.   I’ll ignore the proposal for now, in that case.

 

All that would take is putting Coercion in TysWiredIn, and moving Coercion from Data.Type.Coercion to somewhere in ghc-prim.

 

I don’t think it’s quite as simple as that.  Yes, we can wire it into the compiler; but we still need a module that defines the info table, curried data constructor etc for the type.  And we have no way to do that.

 

We could utterly lie and say

              data Coercion a b where

                  Coercion :: Coercion a a

 

That would generate the right bits in in the .o file, and we’d totally ignore the .hi file.  Gruesome but I think it would work.

 

 

But rather than all this circumlocution, why don’t we just make it possible to write ~# and ~R# directly.  Even if we dodge the need right now, it’ll surely come back.

 

If that is lexically tiresome, we could I suppose provide builtin-aliases for them, as if we had

              type NomEq# = (~#)

             type ReprEq# = (~R#)

 

Simon

 

From: Ryan Scott <[hidden email]>
Sent: 05 September 2018 15:26
To: Simon Peyton Jones <[hidden email]>
Cc: [hidden email]
Subject: Re: Unpacking coercions

 

> Simple is good.  But what is this dead simple idea?

 

I'm referring to David's first e-mail on this thread: https://mail.haskell.org/pipermail/ghc-devs/2018-September/016191.html

 

All that would take is putting Coercion in TysWiredIn, and moving Coercion from Data.Type.Coercion to somewhere in ghc-prim.

 

> Maybe this thread belongs with the proposal, unless I’m misunderstanding.

 

I think the intention is to have that proposal (which proposes a language change) be superseded by this idea (which does not change the language).

 

Ryan S.

 

 

On Wed, Sep 5, 2018 at 10:20 AM, Simon Peyton Jones <[hidden email]> wrote:

Simple is good.  But what is this dead simple idea?

 

Perhaps: https://github.com/ghc-proposals/ghc-proposals/pull/116

But that proposal lists several possible alternatives.  Which one did you mean?

 

And all of them are language changes. Making evidence strict would require no language changes to solve the original problem.

 

Maybe this thread belongs with the proposal, unless I’m misunderstanding.

 

Simon

 

From: ghc-devs <[hidden email]> On Behalf Of Ryan Scott
Sent: 05 September 2018 15:15
To: [hidden email]
Subject: Re: Unpacking coercions

 

These aren't mutually exclusive ideas. While I'm sure there's many ways we could solve this problem, David's idea has the distinct advantage of being dead simple. I'd rather not block his vision on some other large refactor that may never materialize. (And if it _does_ materialize, we could revert any wiring-in of Coercible quite easily.)

 

Ryan S.

 


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Reply | Threaded
Open this post in threaded view
|

RE: Unpacking coercions

GHC - devs mailing list

OK – a good thread.   From it I have learned

 

  • What the goal is
  • That exposing (~#) and (~R#) is not just lexically tricky; it’s deeper than that (Richard’s note below).
  • That there is a viable, implementation plan; not a thing of beauty perhaps, but ok if carefully documented

 

Sounds good to me!

 

My suggestion, if someone is motivated enough to pursue this:

  • write a wiki page to summarise the above points
  • plus a ticket to track progress
  • implement the design

 

Happy to help review.


Sorry to have been slow to understand.

 

Simon

 

 

 

From: Richard Eisenberg <[hidden email]>
Sent: 05 September 2018 16:26
To: Ryan Scott <[hidden email]>
Cc: Simon Peyton Jones <[hidden email]>; [hidden email]
Subject: Re: Unpacking coercions

 

I don't think that wiki reference is really about this problem.

 

Instead, I think that we'd need Constraint# to be able to offer users ~# and ~R#. The problem, then, is that there is no answer to this question: Constraint is to Type as Constraint# is to what? Currently, if ~# and ~R# are the only two generators of Constraint#, then Constraint# is like TYPE (TupleRep '[]). But I think wiring that in would be short-sighted.

 

Instead, this road leads to CONSTRAINT :: RuntimeRep -> Type, which is like TYPE. Today's Constraint would be CONSTRAINT LiftedRep. And we would have (~#), (~R#) :: forall k1 k2. k1 -> k2 -> CONSTRAINT (TupleRep '[]). In the Glorious Future, we'll have CONSTRAINT ~R TYPE, but we're not there yet. 

 

This all feel like the Right Answer to me, but it's unclear if we should start down this road before we have roles in kinds.

 

Richard

 

On Sep 5, 2018, at 10:54 AM, Ryan Scott <[hidden email]> wrote:

 

> We could utterly lie and say
>
>               data Coercion a b where
>
>                   Coercion :: Coercion a a
>

>
> That would generate the right bits in in the .o file, and we’d totally ignore the .hi file.  Gruesome but I think it would work.

 

This was precisely what I had in mind. We already perform this trick for several things defined in ghc-prim (e.g., the (~) and (~~) classes), so this would just be another example of that.

 

> But rather than all this circumlocution, why don’t we just make it possible to write ~# and ~R# directly.  Even if we dodge the need right now, it’ll surely come back.

 

Hah, the reason David is suggesting his idea in the first place is to avoid having to do this! My understanding is that making it possible to write (~#) and (~R#) directly would involve quite a number of complications, as Richard's wiki entry on the subject [1] demonstrates.

 

That's not to say that I wouldn't like to see that happen some day. But a mere mortal like myself couldn't possibly implement this, whereas David's idea is actually within reach.

 

Ryan S.

-----

 

On Wed, Sep 5, 2018 at 10:45 AM, Simon Peyton Jones <[hidden email]> wrote:

I think the intention is to have that proposal (which proposes a language change) be superseded by this idea (which does not change the language).

Oh, I did not know that.   I’ll ignore the proposal for now, in that case.

 

All that would take is putting Coercion in TysWiredIn, and moving Coercion from Data.Type.Coercion to somewhere in ghc-prim.

 

I don’t think it’s quite as simple as that.  Yes, we can wire it into the compiler; but we still need a module that defines the info table, curried data constructor etc for the type.  And we have no way to do that.

 

We could utterly lie and say

              data Coercion a b where

                  Coercion :: Coercion a a

 

That would generate the right bits in in the .o file, and we’d totally ignore the .hi file.  Gruesome but I think it would work.

 

 

But rather than all this circumlocution, why don’t we just make it possible to write ~# and ~R# directly.  Even if we dodge the need right now, it’ll surely come back.

 

If that is lexically tiresome, we could I suppose provide builtin-aliases for them, as if we had

              type NomEq# = (~#)

             type ReprEq# = (~R#)

 

Simon

 

From: Ryan Scott <[hidden email]>
Sent: 05 September 2018 15:26
To: Simon Peyton Jones <[hidden email]>
Cc: [hidden email]
Subject: Re: Unpacking coercions

 

> Simple is good.  But what is this dead simple idea?

 

I'm referring to David's first e-mail on this thread: https://mail.haskell.org/pipermail/ghc-devs/2018-September/016191.html

 

All that would take is putting Coercion in TysWiredIn, and moving Coercion from Data.Type.Coercion to somewhere in ghc-prim.

 

> Maybe this thread belongs with the proposal, unless I’m misunderstanding.

 

I think the intention is to have that proposal (which proposes a language change) be superseded by this idea (which does not change the language).

 

Ryan S.

 

 

On Wed, Sep 5, 2018 at 10:20 AM, Simon Peyton Jones <[hidden email]> wrote:

Simple is good.  But what is this dead simple idea?

 

Perhaps: https://github.com/ghc-proposals/ghc-proposals/pull/116

But that proposal lists several possible alternatives.  Which one did you mean?

 

And all of them are language changes. Making evidence strict would require no language changes to solve the original problem.

 

Maybe this thread belongs with the proposal, unless I’m misunderstanding.

 

Simon

 

From: ghc-devs <[hidden email]> On Behalf Of Ryan Scott
Sent: 05 September 2018 15:15
To: [hidden email]
Subject: Re: Unpacking coercions

 

These aren't mutually exclusive ideas. While I'm sure there's many ways we could solve this problem, David's idea has the distinct advantage of being dead simple. I'd rather not block his vision on some other large refactor that may never materialize. (And if it _does_ materialize, we could revert any wiring-in of Coercible quite easily.)

 

Ryan S.

 

 

_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs

 


_______________________________________________
ghc-devs mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs