Giving function a larger arity

[Simon Peyton-Jones]

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