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-boun...@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
