Giving function a larger arity

Simon Peyton-Jones simonpj at microsoft.com
Tue Nov 12 08:36:31 UTC 2013


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<mailto: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<mailto:jwlato at gmail.com>]
Sent: 11 November 2013 17:29
To: Simon Peyton-Jones
Cc: glasgow-haskell-users at haskell.org<mailto: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<mailto: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<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<mailto: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<mailto:Glasgow-haskell-users at haskell.org>
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20131112/9b6d2dbe/attachment-0001.html>


More information about the Glasgow-haskell-users mailing list