Giving function a larger arity

John Lato jwlato at gmail.com
Mon Nov 11 17:28:42 UTC 2013


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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20131111/b2925d49/attachment.html>


More information about the Glasgow-haskell-users mailing list