Akio Takano | 11 Nov 10:18 2013
Picon

Giving function a larger arity

Hi,

I've been trying to get a certain type of programs compiled into efficient code, but I haven't been able to find a good way to do it, so I'm asking for help.

Specifically, it involves a library that defines a newtype whose representation is a function. Attached Lib.hs is an example of such a library. It defines a newtype (Builder), and functions (fromInt, mappend) that deal with it.

In user code I want to write a (often-recursive) function that produces a value of the newtype (the 'upto' function in arity.hs is an example). The problem is that I know that the resulting value will be used only once, and I'd like GHC to take advantage of it. In other words, I want the 'upto' function to get compiled into something that takes 4 arguments (Int#, Int#, Addr# and State#), rather than a binary function that returns a lambda.

I understand that GHC does not do this by default for a good reason. It avoids potentially calling 'slightlyExpensive' more than once. However I need some way to get the larger arity, because the performance difference can be rather large (for example, this problem can add a lot of boxing to an otherwise allocation-free loop).

One of my attempts was to have the library expose a function with which the user can tell GHC that re-computation is okay. Lib.rebuild is such a function, and the 'upto_rebuild' function demonstrates how to use it. Unfortunately this approach only worked when the full-laziness optimization was explicitly disabled.

This problem happened many times to me. In particular Reader and State monads often triggered it.

I'm using GHC 7.6.3.

Any advice?

Thank you,
Takano Akio
Attachment (Lib.hs): text/x-haskell, 648 bytes
Attachment (arity.hs): text/x-haskell, 701 bytes
_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Simon Peyton-Jones | 11 Nov 12:12 2013
Picon

RE: Giving function a larger arity

Strangely enough I’ve been thinking about eta expansion in the last day or two.  It’s one of GHC’s more delicate corners, because

1.       There can be big performance boosts

2.       If you push a redex inside a lambda

But as you point out (2) may be arbitrarily bad unless you know the lambda is called at most once (is “one-shot”).

 

There is really no good way to declare a lambda to be one-shot right now.  As you discovered, full laziness tends to defeat your attempts to do so!  (A workaround is to switch off full laziness, but that doesn’t feel right.)

 

What is a more general solution?  I can think of two.

 

A.      Declare one-shot-ness in the type.  Something like this:

newtype OneShot a = OS a

newtype Builder = Builder (OneShot (Ptr ()) -> IO (Ptr ()))

                plus telling GHC that anything with a OneShot type is a one-shot lambda.

 

B.      Declaring one-shot-ness in the terms.  Something like

..Builder (\x {-# ONESHOT #-} -> blah)…

                That would declare this particular lambda to be one-shot, but not any other.

 

Notes

·         Plan A would require a bit of fiddling to move your values in and out of the OneShot type.  And it’d make the terms a bit bigger at compile time.

·         Plan B is more explicit all the use sites.

·         Both plans would be vulnerable to user error.  I could imagine and analysis that would guarantee that you met the one-shot claim; but it would necessarily be quite conservative.  That might or might not be OK

·         GHC already embodies a version of (A): the “state hack” means that  a lambda whose binder is a state token (State# RealWorld#) is treated as one-shot.  We have many bug reports describing when this hack makes things bad, but it is such a huge win for more programs that it is on by default.    (Your “rebuild” idea might work better with (State# Realorld# -> Builder) rather than (() -> Builder) for that reason.)

 

Simon

 

From: Glasgow-haskell-users [mailto:glasgow-haskell-users-bounces <at> haskell.org] On Behalf Of Akio Takano
Sent: 11 November 2013 09:19
To: glasgow-haskell-users <at> haskell.org
Subject: Giving function a larger arity

 

Hi,

I've been trying to get a certain type of programs compiled into efficient code, but I haven't been able to find a good way to do it, so I'm asking for help.

Specifically, it involves a library that defines a newtype whose representation is a function. Attached Lib.hs is an example of such a library. It defines a newtype (Builder), and functions (fromInt, mappend) that deal with it.

In user code I want to write a (often-recursive) function that produces a value of the newtype (the 'upto' function in arity.hs is an example). The problem is that I know that the resulting value will be used only once, and I'd like GHC to take advantage of it. In other words, I want the 'upto' function to get compiled into something that takes 4 arguments (Int#, Int#, Addr# and State#), rather than a binary function that returns a lambda.

I understand that GHC does not do this by default for a good reason. It avoids potentially calling 'slightlyExpensive' more than once. However I need some way to get the larger arity, because the performance difference can be rather large (for example, this problem can add a lot of boxing to an otherwise allocation-free loop).

One of my attempts was to have the library expose a function with which the user can tell GHC that re-computation is okay. Lib.rebuild is such a function, and the 'upto_rebuild' function demonstrates how to use it. Unfortunately this approach only worked when the full-laziness optimization was explicitly disabled.

This problem happened many times to me. In particular Reader and State monads often triggered it.

I'm using GHC 7.6.3.

Any advice?

Thank you,
Takano Akio

_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
John Lato | 11 Nov 18:28 2013
Picon

RE: Giving function a larger arity

Originally I thought Plan B would make more sense, but if Plan A were implemented could this one-shot type annotation be unified with the state hack? I'm envisioning something like RULES, where if the type matches ghc knows it's a one-shot lambda.

I think it would be better to not do any analysis and leave this completely up to the user. My intention is to get a mechanism to tell ghc it's okay to recompute something in a lambda, essentially a manual state hack. I seem to recall wanting this, but I don't remember the exact use case. It's possible it was one-shot anyway.

John L.

On Nov 11, 2013 5:12 AM, "Simon Peyton-Jones" <simonpj <at> microsoft.com> wrote:

Strangely enough I’ve been thinking about eta expansion in the last day or two.  It’s one of GHC’s more delicate corners, because

1.       There can be big performance boosts

2.       If you push a redex inside a lambda

But as you point out (2) may be arbitrarily bad unless you know the lambda is called at most once (is “one-shot”).

 

There is really no good way to declare a lambda to be one-shot right now.  As you discovered, full laziness tends to defeat your attempts to do so!  (A workaround is to switch off full laziness, but that doesn’t feel right.)

 

What is a more general solution?  I can think of two.

 

A.      Declare one-shot-ness in the type.  Something like this:

newtype OneShot a = OS a

newtype Builder = Builder (OneShot (Ptr ()) -> IO (Ptr ()))

                plus telling GHC that anything with a OneShot type is a one-shot lambda.

 

B.      Declaring one-shot-ness in the terms.  Something like

..Builder (\x {-# ONESHOT #-} -> blah)…

                That would declare this particular lambda to be one-shot, but not any other.

 

Notes

·         Plan A would require a bit of fiddling to move your values in and out of the OneShot type.  And it’d make the terms a bit bigger at compile time.

·         Plan B is more explicit all the use sites.

·         Both plans would be vulnerable to user error.  I could imagine and analysis that would guarantee that you met the one-shot claim; but it would necessarily be quite conservative.  That might or might not be OK

·         GHC already embodies a version of (A): the “state hack” means that  a lambda whose binder is a state token (State# RealWorld#) is treated as one-shot.  We have many bug reports describing when this hack makes things bad, but it is such a huge win for more programs that it is on by default.    (Your “rebuild” idea might work better with (State# Realorld# -> Builder) rather than (() -> Builder) for that reason.)

 

Simon

 

From: Glasgow-haskell-users [mailto:glasgow-haskell-users-bounces <at> haskell.org] On Behalf Of Akio Takano
Sent: 11 November 2013 09:19
To: glasgow-haskell-users <at> haskell.org
Subject: Giving function a larger arity

 

Hi,

I've been trying to get a certain type of programs compiled into efficient code, but I haven't been able to find a good way to do it, so I'm asking for help.

Specifically, it involves a library that defines a newtype whose representation is a function. Attached Lib.hs is an example of such a library. It defines a newtype (Builder), and functions (fromInt, mappend) that deal with it.

In user code I want to write a (often-recursive) function that produces a value of the newtype (the 'upto' function in arity.hs is an example). The problem is that I know that the resulting value will be used only once, and I'd like GHC to take advantage of it. In other words, I want the 'upto' function to get compiled into something that takes 4 arguments (Int#, Int#, Addr# and State#), rather than a binary function that returns a lambda.

I understand that GHC does not do this by default for a good reason. It avoids potentially calling 'slightlyExpensive' more than once. However I need some way to get the larger arity, because the performance difference can be rather large (for example, this problem can add a lot of boxing to an otherwise allocation-free loop).

One of my attempts was to have the library expose a function with which the user can tell GHC that re-computation is okay. Lib.rebuild is such a function, and the 'upto_rebuild' function demonstrates how to use it. Unfortunately this approach only worked when the full-laziness optimization was explicitly disabled.

This problem happened many times to me. In particular Reader and State monads often triggered it.

I'm using GHC 7.6.3.

Any advice?

Thank you,
Takano Akio


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Simon Peyton-Jones | 11 Nov 22:29 2013
Picon

RE: Giving function a larger arity

Well, Plan A is indeed an extended version of the ”state hack”. Instead of just (State# RealWorld#) being magically considered one-shot, we’d also add (OneShot t).

 

Simon

 

From: John Lato [mailto:jwlato <at> gmail.com]
Sent: 11 November 2013 17:29
To: Simon Peyton-Jones
Cc: glasgow-haskell-users <at> haskell.org; Akio Takano
Subject: RE: Giving function a larger arity

 

Originally I thought Plan B would make more sense, but if Plan A were implemented could this one-shot type annotation be unified with the state hack? I'm envisioning something like RULES, where if the type matches ghc knows it's a one-shot lambda.

I think it would be better to not do any analysis and leave this completely up to the user. My intention is to get a mechanism to tell ghc it's okay to recompute something in a lambda, essentially a manual state hack. I seem to recall wanting this, but I don't remember the exact use case. It's possible it was one-shot anyway.

John L.

On Nov 11, 2013 5:12 AM, "Simon Peyton-Jones" <simonpj <at> microsoft.com> wrote:

Strangely enough I’ve been thinking about eta expansion in the last day or two.  It’s one of GHC’s more delicate corners, because

1.       There can be big performance boosts

2.       If you push a redex inside a lambda

But as you point out (2) may be arbitrarily bad unless you know the lambda is called at most once (is “one-shot”).

 

There is really no good way to declare a lambda to be one-shot right now.  As you discovered, full laziness tends to defeat your attempts to do so!  (A workaround is to switch off full laziness, but that doesn’t feel right.)

 

What is a more general solution?  I can think of two.

 

A.      Declare one-shot-ness in the type.  Something like this:

newtype OneShot a = OS a

newtype Builder = Builder (OneShot (Ptr ()) -> IO (Ptr ()))

                plus telling GHC that anything with a OneShot type is a one-shot lambda.

 

B.      Declaring one-shot-ness in the terms.  Something like

..Builder (\x {-# ONESHOT #-} -> blah)…

                That would declare this particular lambda to be one-shot, but not any other.

 

Notes

·         Plan A would require a bit of fiddling to move your values in and out of the OneShot type.  And it’d make the terms a bit bigger at compile time.

·         Plan B is more explicit all the use sites.

·         Both plans would be vulnerable to user error.  I could imagine and analysis that would guarantee that you met the one-shot claim; but it would necessarily be quite conservative.  That might or might not be OK

·         GHC already embodies a version of (A): the “state hack” means that  a lambda whose binder is a state token (State# RealWorld#) is treated as one-shot.  We have many bug reports describing when this hack makes things bad, but it is such a huge win for more programs that it is on by default.    (Your “rebuild” idea might work better with (State# Realorld# -> Builder) rather than (() -> Builder) for that reason.)

 

Simon

 

From: Glasgow-haskell-users [mailto:glasgow-haskell-users-bounces <at> haskell.org] On Behalf Of Akio Takano
Sent: 11 November 2013 09:19
To: glasgow-haskell-users <at> haskell.org
Subject: Giving function a larger arity

 

Hi,

I've been trying to get a certain type of programs compiled into efficient code, but I haven't been able to find a good way to do it, so I'm asking for help.

Specifically, it involves a library that defines a newtype whose representation is a function. Attached Lib.hs is an example of such a library. It defines a newtype (Builder), and functions (fromInt, mappend) that deal with it.

In user code I want to write a (often-recursive) function that produces a value of the newtype (the 'upto' function in arity.hs is an example). The problem is that I know that the resulting value will be used only once, and I'd like GHC to take advantage of it. In other words, I want the 'upto' function to get compiled into something that takes 4 arguments (Int#, Int#, Addr# and State#), rather than a binary function that returns a lambda.

I understand that GHC does not do this by default for a good reason. It avoids potentially calling 'slightlyExpensive' more than once. However I need some way to get the larger arity, because the performance difference can be rather large (for example, this problem can add a lot of boxing to an otherwise allocation-free loop).

One of my attempts was to have the library expose a function with which the user can tell GHC that re-computation is okay. Lib.rebuild is such a function, and the 'upto_rebuild' function demonstrates how to use it. Unfortunately this approach only worked when the full-laziness optimization was explicitly disabled.

This problem happened many times to me. In particular Reader and State monads often triggered it.

I'm using GHC 7.6.3.

Any advice?

Thank you,
Takano Akio


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Carter Schonwald | 11 Nov 22:38 2013
Picon

Re: Giving function a larger arity

and this would be a way of hinting / communicating that a lambda will be used  at most once? 


On Mon, Nov 11, 2013 at 4:29 PM, Simon Peyton-Jones <simonpj <at> microsoft.com> wrote:

Well, Plan A is indeed an extended version of the ”state hack”. Instead of just (State# RealWorld#) being magically considered one-shot, we’d also add (OneShot t).

 

Simon

 

From: John Lato [mailto:jwlato <at> gmail.com]

Sent: 11 November 2013 17:29
To: Simon Peyton-Jones
Cc: glasgow-haskell-users <at> haskell.org; Akio Takano
Subject: RE: Giving function a larger arity

 

Originally I thought Plan B would make more sense, but if Plan A were implemented could this one-shot type annotation be unified with the state hack? I'm envisioning something like RULES, where if the type matches ghc knows it's a one-shot lambda.

I think it would be better to not do any analysis and leave this completely up to the user. My intention is to get a mechanism to tell ghc it's okay to recompute something in a lambda, essentially a manual state hack. I seem to recall wanting this, but I don't remember the exact use case. It's possible it was one-shot anyway.

John L.

On Nov 11, 2013 5:12 AM, "Simon Peyton-Jones" <simonpj <at> microsoft.com> wrote:

Strangely enough I’ve been thinking about eta expansion in the last day or two.  It’s one of GHC’s more delicate corners, because

1.       There can be big performance boosts

2.       If you push a redex inside a lambda

But as you point out (2) may be arbitrarily bad unless you know the lambda is called at most once (is “one-shot”).

 

There is really no good way to declare a lambda to be one-shot right now.  As you discovered, full laziness tends to defeat your attempts to do so!  (A workaround is to switch off full laziness, but that doesn’t feel right.)

 

What is a more general solution?  I can think of two.

 

A.      Declare one-shot-ness in the type.  Something like this:

newtype OneShot a = OS a

newtype Builder = Builder (OneShot (Ptr ()) -> IO (Ptr ()))

                plus telling GHC that anything with a OneShot type is a one-shot lambda.

 

B.      Declaring one-shot-ness in the terms.  Something like

..Builder (\x {-# ONESHOT #-} -> blah)…

                That would declare this particular lambda to be one-shot, but not any other.

 

Notes

·         Plan A would require a bit of fiddling to move your values in and out of the OneShot type.  And it’d make the terms a bit bigger at compile time.

·         Plan B is more explicit all the use sites.

·         Both plans would be vulnerable to user error.  I could imagine and analysis that would guarantee that you met the one-shot claim; but it would necessarily be quite conservative.  That might or might not be OK

·         GHC already embodies a version of (A): the “state hack” means that  a lambda whose binder is a state token (State# RealWorld#) is treated as one-shot.  We have many bug reports describing when this hack makes things bad, but it is such a huge win for more programs that it is on by default.    (Your “rebuild” idea might work better with (State# Realorld# -> Builder) rather than (() -> Builder) for that reason.)

 

Simon

 

From: Glasgow-haskell-users [mailto:glasgow-haskell-users-bounces <at> haskell.org] On Behalf Of Akio Takano
Sent: 11 November 2013 09:19
To: glasgow-haskell-users <at> haskell.org
Subject: Giving function a larger arity

 

Hi,

I've been trying to get a certain type of programs compiled into efficient code, but I haven't been able to find a good way to do it, so I'm asking for help.

Specifically, it involves a library that defines a newtype whose representation is a function. Attached Lib.hs is an example of such a library. It defines a newtype (Builder), and functions (fromInt, mappend) that deal with it.

In user code I want to write a (often-recursive) function that produces a value of the newtype (the 'upto' function in arity.hs is an example). The problem is that I know that the resulting value will be used only once, and I'd like GHC to take advantage of it. In other words, I want the 'upto' function to get compiled into something that takes 4 arguments (Int#, Int#, Addr# and State#), rather than a binary function that returns a lambda.

I understand that GHC does not do this by default for a good reason. It avoids potentially calling 'slightlyExpensive' more than once. However I need some way to get the larger arity, because the performance difference can be rather large (for example, this problem can add a lot of boxing to an otherwise allocation-free loop).

One of my attempts was to have the library expose a function with which the user can tell GHC that re-computation is okay. Lib.rebuild is such a function, and the 'upto_rebuild' function demonstrates how to use it. Unfortunately this approach only worked when the full-laziness optimization was explicitly disabled.

This problem happened many times to me. In particular Reader and State monads often triggered it.

I'm using GHC 7.6.3.

Any advice?

Thank you,
Takano Akio


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
John Lato | 12 Nov 01:11 2013
Picon

Re: Giving function a larger arity

Yes, that's what I meant.  I was thinking that from an implementation perspective, it would be nice if all the one-shot hacks were in a single place, and if plan A facilitated that it would be a good reason to support that approach.  But I suppose checking an annotation is no harder than checking a type, so it's probably irrelevant.


On Mon, Nov 11, 2013 at 3:29 PM, Simon Peyton-Jones <simonpj <at> microsoft.com> wrote:

Well, Plan A is indeed an extended version of the ”state hack”. Instead of just (State# RealWorld#) being magically considered one-shot, we’d also add (OneShot t).

 

Simon

 

From: John Lato [mailto:jwlato <at> gmail.com]

Sent: 11 November 2013 17:29
To: Simon Peyton-Jones
Cc: glasgow-haskell-users <at> haskell.org; Akio Takano
Subject: RE: Giving function a larger arity

 

Originally I thought Plan B would make more sense, but if Plan A were implemented could this one-shot type annotation be unified with the state hack? I'm envisioning something like RULES, where if the type matches ghc knows it's a one-shot lambda.

I think it would be better to not do any analysis and leave this completely up to the user. My intention is to get a mechanism to tell ghc it's okay to recompute something in a lambda, essentially a manual state hack. I seem to recall wanting this, but I don't remember the exact use case. It's possible it was one-shot anyway.

John L.

On Nov 11, 2013 5:12 AM, "Simon Peyton-Jones" <simonpj <at> microsoft.com> wrote:

Strangely enough I’ve been thinking about eta expansion in the last day or two.  It’s one of GHC’s more delicate corners, because

1.       There can be big performance boosts

2.       If you push a redex inside a lambda

But as you point out (2) may be arbitrarily bad unless you know the lambda is called at most once (is “one-shot”).

 

There is really no good way to declare a lambda to be one-shot right now.  As you discovered, full laziness tends to defeat your attempts to do so!  (A workaround is to switch off full laziness, but that doesn’t feel right.)

 

What is a more general solution?  I can think of two.

 

A.      Declare one-shot-ness in the type.  Something like this:

newtype OneShot a = OS a

newtype Builder = Builder (OneShot (Ptr ()) -> IO (Ptr ()))

                plus telling GHC that anything with a OneShot type is a one-shot lambda.

 

B.      Declaring one-shot-ness in the terms.  Something like

..Builder (\x {-# ONESHOT #-} -> blah)…

                That would declare this particular lambda to be one-shot, but not any other.

 

Notes

·         Plan A would require a bit of fiddling to move your values in and out of the OneShot type.  And it’d make the terms a bit bigger at compile time.

·         Plan B is more explicit all the use sites.

·         Both plans would be vulnerable to user error.  I could imagine and analysis that would guarantee that you met the one-shot claim; but it would necessarily be quite conservative.  That might or might not be OK

·         GHC already embodies a version of (A): the “state hack” means that  a lambda whose binder is a state token (State# RealWorld#) is treated as one-shot.  We have many bug reports describing when this hack makes things bad, but it is such a huge win for more programs that it is on by default.    (Your “rebuild” idea might work better with (State# Realorld# -> Builder) rather than (() -> Builder) for that reason.)

 

Simon

 

From: Glasgow-haskell-users [mailto:glasgow-haskell-users-bounces <at> haskell.org] On Behalf Of Akio Takano
Sent: 11 November 2013 09:19
To: glasgow-haskell-users <at> haskell.org
Subject: Giving function a larger arity

 

Hi,

I've been trying to get a certain type of programs compiled into efficient code, but I haven't been able to find a good way to do it, so I'm asking for help.

Specifically, it involves a library that defines a newtype whose representation is a function. Attached Lib.hs is an example of such a library. It defines a newtype (Builder), and functions (fromInt, mappend) that deal with it.

In user code I want to write a (often-recursive) function that produces a value of the newtype (the 'upto' function in arity.hs is an example). The problem is that I know that the resulting value will be used only once, and I'd like GHC to take advantage of it. In other words, I want the 'upto' function to get compiled into something that takes 4 arguments (Int#, Int#, Addr# and State#), rather than a binary function that returns a lambda.

I understand that GHC does not do this by default for a good reason. It avoids potentially calling 'slightlyExpensive' more than once. However I need some way to get the larger arity, because the performance difference can be rather large (for example, this problem can add a lot of boxing to an otherwise allocation-free loop).

One of my attempts was to have the library expose a function with which the user can tell GHC that re-computation is okay. Lib.rebuild is such a function, and the 'upto_rebuild' function demonstrates how to use it. Unfortunately this approach only worked when the full-laziness optimization was explicitly disabled.

This problem happened many times to me. In particular Reader and State monads often triggered it.

I'm using GHC 7.6.3.

Any advice?

Thank you,
Takano Akio


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Simon Peyton-Jones | 12 Nov 09:36 2013
Picon

RE: Giving function a larger arity

There is a difference between plan A and B.  For example, if

                f :: (OneShot a -> b) -> [a] -> [b]

then EVERY function passed to f would have to be one-shot (Plan A).  But under plan B you could have two calls

 

                …f (\x. blah)….. f (\y{-#ONESHOT#-}. blah2)….

 

and only the second would be a one-shot lambda. 

 

So if anything plan B seems more flexible.

 

Simon

 

 

From: John Lato [mailto:jwlato <at> gmail.com]
Sent: 12 November 2013 00:12
To: Simon Peyton-Jones
Cc: glasgow-haskell-users <at> haskell.org; Akio Takano
Subject: Re: Giving function a larger arity

 

Yes, that's what I meant.  I was thinking that from an implementation perspective, it would be nice if all the one-shot hacks were in a single place, and if plan A facilitated that it would be a good reason to support that approach.  But I suppose checking an annotation is no harder than checking a type, so it's probably irrelevant.

 

On Mon, Nov 11, 2013 at 3:29 PM, Simon Peyton-Jones <simonpj <at> microsoft.com> wrote:

Well, Plan A is indeed an extended version of the ”state hack”. Instead of just (State# RealWorld#) being magically considered one-shot, we’d also add (OneShot t).

 

Simon

 

From: John Lato [mailto:jwlato <at> gmail.com]

Sent: 11 November 2013 17:29

To: Simon Peyton-Jones
Cc: glasgow-haskell-users <at> haskell.org; Akio Takano
Subject: RE: Giving function a larger arity

 

Originally I thought Plan B would make more sense, but if Plan A were implemented could this one-shot type annotation be unified with the state hack? I'm envisioning something like RULES, where if the type matches ghc knows it's a one-shot lambda.

I think it would be better to not do any analysis and leave this completely up to the user. My intention is to get a mechanism to tell ghc it's okay to recompute something in a lambda, essentially a manual state hack. I seem to recall wanting this, but I don't remember the exact use case. It's possible it was one-shot anyway.

John L.

On Nov 11, 2013 5:12 AM, "Simon Peyton-Jones" <simonpj <at> microsoft.com> wrote:

Strangely enough I’ve been thinking about eta expansion in the last day or two.  It’s one of GHC’s more delicate corners, because

1.       There can be big performance boosts

2.       If you push a redex inside a lambda

But as you point out (2) may be arbitrarily bad unless you know the lambda is called at most once (is “one-shot”).

 

There is really no good way to declare a lambda to be one-shot right now.  As you discovered, full laziness tends to defeat your attempts to do so!  (A workaround is to switch off full laziness, but that doesn’t feel right.)

 

What is a more general solution?  I can think of two.

 

A.      Declare one-shot-ness in the type.  Something like this:

newtype OneShot a = OS a

newtype Builder = Builder (OneShot (Ptr ()) -> IO (Ptr ()))

                plus telling GHC that anything with a OneShot type is a one-shot lambda.

 

B.      Declaring one-shot-ness in the terms.  Something like

..Builder (\x {-# ONESHOT #-} -> blah)…

                That would declare this particular lambda to be one-shot, but not any other.

 

Notes

·         Plan A would require a bit of fiddling to move your values in and out of the OneShot type.  And it’d make the terms a bit bigger at compile time.

·         Plan B is more explicit all the use sites.

·         Both plans would be vulnerable to user error.  I could imagine and analysis that would guarantee that you met the one-shot claim; but it would necessarily be quite conservative.  That might or might not be OK

·         GHC already embodies a version of (A): the “state hack” means that  a lambda whose binder is a state token (State# RealWorld#) is treated as one-shot.  We have many bug reports describing when this hack makes things bad, but it is such a huge win for more programs that it is on by default.    (Your “rebuild” idea might work better with (State# Realorld# -> Builder) rather than (() -> Builder) for that reason.)

 

Simon

 

From: Glasgow-haskell-users [mailto:glasgow-haskell-users-bounces <at> haskell.org] On Behalf Of Akio Takano
Sent: 11 November 2013 09:19
To: glasgow-haskell-users <at> haskell.org
Subject: Giving function a larger arity

 

Hi,

I've been trying to get a certain type of programs compiled into efficient code, but I haven't been able to find a good way to do it, so I'm asking for help.

Specifically, it involves a library that defines a newtype whose representation is a function. Attached Lib.hs is an example of such a library. It defines a newtype (Builder), and functions (fromInt, mappend) that deal with it.

In user code I want to write a (often-recursive) function that produces a value of the newtype (the 'upto' function in arity.hs is an example). The problem is that I know that the resulting value will be used only once, and I'd like GHC to take advantage of it. In other words, I want the 'upto' function to get compiled into something that takes 4 arguments (Int#, Int#, Addr# and State#), rather than a binary function that returns a lambda.

I understand that GHC does not do this by default for a good reason. It avoids potentially calling 'slightlyExpensive' more than once. However I need some way to get the larger arity, because the performance difference can be rather large (for example, this problem can add a lot of boxing to an otherwise allocation-free loop).

One of my attempts was to have the library expose a function with which the user can tell GHC that re-computation is okay. Lib.rebuild is such a function, and the 'upto_rebuild' function demonstrates how to use it. Unfortunately this approach only worked when the full-laziness optimization was explicitly disabled.

This problem happened many times to me. In particular Reader and State monads often triggered it.

I'm using GHC 7.6.3.

Any advice?

Thank you,
Takano Akio


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

 

_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Johan Tibell | 12 Nov 10:18 2013
Picon

Re: Giving function a larger arity

And plan 2 doesn't require a magic data type. :)


On Tue, Nov 12, 2013 at 9:36 AM, Simon Peyton-Jones <simonpj <at> microsoft.com> wrote:

There is a difference between plan A and B.  For example, if

                f :: (OneShot a -> b) -> [a] -> [b]

then EVERY function passed to f would have to be one-shot (Plan A).  But under plan B you could have two calls

 

                …f (\x. blah)….. f (\y{-#ONESHOT#-}. blah2)….

 

and only the second would be a one-shot lambda. 

 

So if anything plan B seems more flexible.

 

Simon

 

 

From: John Lato [mailto:jwlato <at> gmail.com]
Sent: 12 November 2013 00:12


To: Simon Peyton-Jones
Cc: glasgow-haskell-users <at> haskell.org; Akio Takano
Subject: Re: Giving function a larger arity

 

Yes, that's what I meant.  I was thinking that from an implementation perspective, it would be nice if all the one-shot hacks were in a single place, and if plan A facilitated that it would be a good reason to support that approach.  But I suppose checking an annotation is no harder than checking a type, so it's probably irrelevant.

 

On Mon, Nov 11, 2013 at 3:29 PM, Simon Peyton-Jones <simonpj <at> microsoft.com> wrote:

Well, Plan A is indeed an extended version of the ”state hack”. Instead of just (State# RealWorld#) being magically considered one-shot, we’d also add (OneShot t).

 

Simon

 

From: John Lato [mailto:jwlato <at> gmail.com]

Sent: 11 November 2013 17:29

To: Simon Peyton-Jones
Cc: glasgow-haskell-users <at> haskell.org; Akio Takano
Subject: RE: Giving function a larger arity

 

Originally I thought Plan B would make more sense, but if Plan A were implemented could this one-shot type annotation be unified with the state hack? I'm envisioning something like RULES, where if the type matches ghc knows it's a one-shot lambda.

I think it would be better to not do any analysis and leave this completely up to the user. My intention is to get a mechanism to tell ghc it's okay to recompute something in a lambda, essentially a manual state hack. I seem to recall wanting this, but I don't remember the exact use case. It's possible it was one-shot anyway.

John L.

On Nov 11, 2013 5:12 AM, "Simon Peyton-Jones" <simonpj <at> microsoft.com> wrote:

Strangely enough I’ve been thinking about eta expansion in the last day or two.  It’s one of GHC’s more delicate corners, because

1.       There can be big performance boosts

2.       If you push a redex inside a lambda

But as you point out (2) may be arbitrarily bad unless you know the lambda is called at most once (is “one-shot”).

 

There is really no good way to declare a lambda to be one-shot right now.  As you discovered, full laziness tends to defeat your attempts to do so!  (A workaround is to switch off full laziness, but that doesn’t feel right.)

 

What is a more general solution?  I can think of two.

 

A.      Declare one-shot-ness in the type.  Something like this:

newtype OneShot a = OS a

newtype Builder = Builder (OneShot (Ptr ()) -> IO (Ptr ()))

                plus telling GHC that anything with a OneShot type is a one-shot lambda.

 

B.      Declaring one-shot-ness in the terms.  Something like

..Builder (\x {-# ONESHOT #-} -> blah)…

                That would declare this particular lambda to be one-shot, but not any other.

 

Notes

·         Plan A would require a bit of fiddling to move your values in and out of the OneShot type.  And it’d make the terms a bit bigger at compile time.

·         Plan B is more explicit all the use sites.

·         Both plans would be vulnerable to user error.  I could imagine and analysis that would guarantee that you met the one-shot claim; but it would necessarily be quite conservative.  That might or might not be OK

·         GHC already embodies a version of (A): the “state hack” means that  a lambda whose binder is a state token (State# RealWorld#) is treated as one-shot.  We have many bug reports describing when this hack makes things bad, but it is such a huge win for more programs that it is on by default.    (Your “rebuild” idea might work better with (State# Realorld# -> Builder) rather than (() -> Builder) for that reason.)

 

Simon

 

From: Glasgow-haskell-users [mailto:glasgow-haskell-users-bounces <at> haskell.org] On Behalf Of Akio Takano
Sent: 11 November 2013 09:19
To: glasgow-haskell-users <at> haskell.org
Subject: Giving function a larger arity

 

Hi,

I've been trying to get a certain type of programs compiled into efficient code, but I haven't been able to find a good way to do it, so I'm asking for help.

Specifically, it involves a library that defines a newtype whose representation is a function. Attached Lib.hs is an example of such a library. It defines a newtype (Builder), and functions (fromInt, mappend) that deal with it.

In user code I want to write a (often-recursive) function that produces a value of the newtype (the 'upto' function in arity.hs is an example). The problem is that I know that the resulting value will be used only once, and I'd like GHC to take advantage of it. In other words, I want the 'upto' function to get compiled into something that takes 4 arguments (Int#, Int#, Addr# and State#), rather than a binary function that returns a lambda.

I understand that GHC does not do this by default for a good reason. It avoids potentially calling 'slightlyExpensive' more than once. However I need some way to get the larger arity, because the performance difference can be rather large (for example, this problem can add a lot of boxing to an otherwise allocation-free loop).

One of my attempts was to have the library expose a function with which the user can tell GHC that re-computation is okay. Lib.rebuild is such a function, and the 'upto_rebuild' function demonstrates how to use it. Unfortunately this approach only worked when the full-laziness optimization was explicitly disabled.

This problem happened many times to me. In particular Reader and State monads often triggered it.

I'm using GHC 7.6.3.

Any advice?

Thank you,
Takano Akio


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

 


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Akio Takano | 13 Nov 00:51 2013
Picon

Re: Giving function a larger arity

Using State# RealWorld for rebuild worked fine for the particular problem I had. Thank you very much!

I'd appreciate either solution because it would make it possible to solve the issue without much change in the user code.

A few months ago I tried something similar to the approach B (I used a built-in rule rather than a pragma), in order to re-implement foldl' in terms of foldr. It didn't work very well, but I don't remember what the problem was. Sadly I don't have access to the patch right now. Probably I made a mistake somewhere.

On Mon, Nov 11, 2013 at 8:12 PM, Simon Peyton-Jones <simonpj <at> microsoft.com> wrote:

Strangely enough I’ve been thinking about eta expansion in the last day or two.  It’s one of GHC’s more delicate corners, because

1.       There can be big performance boosts

2.       If you push a redex inside a lambda

But as you point out (2) may be arbitrarily bad unless you know the lambda is called at most once (is “one-shot”).

 

There is really no good way to declare a lambda to be one-shot right now.  As you discovered, full laziness tends to defeat your attempts to do so!  (A workaround is to switch off full laziness, but that doesn’t feel right.)

 

What is a more general solution?  I can think of two.

 

A.      Declare one-shot-ness in the type.  Something like this:

newtype OneShot a = OS a

newtype Builder = Builder (OneShot (Ptr ()) -> IO (Ptr ()))

                plus telling GHC that anything with a OneShot type is a one-shot lambda.

 

B.      Declaring one-shot-ness in the terms.  Something like

..Builder (\x {-# ONESHOT #-} -> blah)…

                That would declare this particular lambda to be one-shot, but not any other.

 

Notes

·         Plan A would require a bit of fiddling to move your values in and out of the OneShot type.  And it’d make the terms a bit bigger at compile time.

·         Plan B is more explicit all the use sites.

·         Both plans would be vulnerable to user error.  I could imagine and analysis that would guarantee that you met the one-shot claim; but it would necessarily be quite conservative.  That might or might not be OK

·         GHC already embodies a version of (A): the “state hack” means that  a lambda whose binder is a state token (State# RealWorld#) is treated as one-shot.  We have many bug reports describing when this hack makes things bad, but it is such a huge win for more programs that it is on by default.    (Your “rebuild” idea might work better with (State# Realorld# -> Builder) rather than (() -> Builder) for that reason.)

 

Simon

 

From: Glasgow-haskell-users [mailto:glasgow-haskell-users-bounces <at> haskell.org] On Behalf Of Akio Takano
Sent: 11 November 2013 09:19
To: glasgow-haskell-users <at> haskell.org
Subject: Giving function a larger arity

 

Hi,

I've been trying to get a certain type of programs compiled into efficient code, but I haven't been able to find a good way to do it, so I'm asking for help.

Specifically, it involves a library that defines a newtype whose representation is a function. Attached Lib.hs is an example of such a library. It defines a newtype (Builder), and functions (fromInt, mappend) that deal with it.

In user code I want to write a (often-recursive) function that produces a value of the newtype (the 'upto' function in arity.hs is an example). The problem is that I know that the resulting value will be used only once, and I'd like GHC to take advantage of it. In other words, I want the 'upto' function to get compiled into something that takes 4 arguments (Int#, Int#, Addr# and State#), rather than a binary function that returns a lambda.

I understand that GHC does not do this by default for a good reason. It avoids potentially calling 'slightlyExpensive' more than once. However I need some way to get the larger arity, because the performance difference can be rather large (for example, this problem can add a lot of boxing to an otherwise allocation-free loop).

One of my attempts was to have the library expose a function with which the user can tell GHC that re-computation is okay. Lib.rebuild is such a function, and the 'upto_rebuild' function demonstrates how to use it. Unfortunately this approach only worked when the full-laziness optimization was explicitly disabled.

This problem happened many times to me. In particular Reader and State monads often triggered it.

I'm using GHC 7.6.3.

Any advice?

Thank you,
Takano Akio


_______________________________________________
Glasgow-haskell-users mailing list
Glasgow-haskell-users <at> haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

Gmane