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" 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@haskell.org] *On Behalf Of *Akio Takano *Sent:* 11 November 2013 09:19 *To:* glasgow-haskell-users@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@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

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 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@gmail.com] *Sent:* 11 November 2013 17:29 *To:* Simon Peyton-Jones *Cc:* glasgow-haskell-users@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" 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@haskell.org] *On Behalf Of *Akio Takano *Sent:* 11 November 2013 09:19 *To:* glasgow-haskell-users@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@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

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

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@gmail.com] Sent: 12 November 2013 00:12 To: Simon Peyton-Jones Cc: glasgow-haskell-users@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 mailto:simonpj@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@gmail.commailto:jwlato@gmail.com] Sent: 11 November 2013 17:29 To: Simon Peyton-Jones Cc: glasgow-haskell-users@haskell.orgmailto:glasgow-haskell-users@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" mailto:simonpj@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@haskell.orgmailto:glasgow-haskell-users-bounces@haskell.org] On Behalf Of Akio Takano Sent: 11 November 2013 09:19 To: glasgow-haskell-users@haskell.orgmailto:glasgow-haskell-users@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@haskell.orgmailto:Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

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 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@haskell.org] *On Behalf Of *Akio Takano *Sent:* 11 November 2013 09:19 *To:* glasgow-haskell-users@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