Extending fold/build fusion

[Akio Takano]

Thank you for looking at this!


On Tue, Jan 14, 2014 at 1:27 AM, Simon Peyton Jones
<simonpj at microsoft.com>wrote:

>  I’ve hesitated to reply, because I have lots of questions but no time to
> investigate in.  I’m looking at your wiki page
> https://github.com/takano-akio/ww-fusion
>
>
>
> ·         Does your proposed new fold’ run faster than the old one?  You
> give no data.
>

No, it runs just equally fast as the old one. At the Core level they are
the same. I ran some criterion benchmarks:

source: https://github.com/takano-akio/ww-fusion/blob/master/benchmarks.hs
results:
http://htmlpreview.github.io/?https://github.com/takano-akio/ww-fusion/blob/master/foldl.html

The point was not to make foldl' faster, but to make it fuse well with good
producers.


>  ·         The new foldl’ is not a “good consumer” in the foldr/build
> sense, which a big loss.  What if you say fold’ k z [1..n]; you want the
> intermediate list to vanish.
>
For my idea to work, enumFromTo and all other good producers need to be
redefined in terms of buildW, which fuses with foldrW. The definition of
buildW and the relevant rules are here:

https://github.com/takano-akio/ww-fusion/blob/master/WWFusion.hs



>  ·         My brain is too small to truly understand your idea.  But
> since foldrW is non-recursive, what happens if you inline foldrW into
> fold’, and then simplify?  I’m betting you get something pretty similar to
> the old foldl’.  Try in by hand, and with GHC and let’s see the final
> optimised code.
>
I checked this and I see the same code as the old foldl', modulo order of
arguments. This is what I expected.


>  ·         Under “motivation” you say “GHC generates something
> essentially like…” and then give some code.  Now, if GHC would only
> eta-expand ‘go’ with a second argument, you’d get brilliant code. And maybe
> that would help lots of programs, not just this one.  It’s a slight
> delicate transformation but I’ve often thought we should try it; c.f #7994,
> #5809
>
I agree that it would be generally useful if GHC did this transformation.
However I don't think it's good enough for this particular goal of making
foldl' fuse well.

Consider a function that flattens a binary tree into a list:

data Tree = Tip {-# UNPACK #-} !Int | Bin Tree Tree

toList :: Tree -> [Int]
toList tree = build (toListFB tree)
{-# INLINE toList #-}

toListFB :: Tree -> (Int -> r -> r) -> r -> r
toListFB root cons nil = go root nil
  where
    go (Tip x) rest = cons x rest
    go (Bin x y) rest = go x (go y rest)

Let's say we want to eliminate the intermediate list in the expression (sum
(toList t)). Currently sum is not a good consumer, but if it were, after
fusion we'd get something like:

sumList :: Tree -> Int
sumList root = go0 root id 0

go0 :: Tree -> (Int -> Int) -> Int -> Int
go0 (Tip x) k = (k $!) .  (x+)
go0 (Bin x y) k = go0 x (go0 y k)

Now, merely eta-expanding go0 is not enough to get efficient code, because
the function will still build a partial application every time it sees a
Bin constructor. For this recursion to work in an allocation-free way, it
must be rather like:

go1 :: Tree -> Int -> Int
go1 (Tip x) n = x + n
go1 (Bin x y) n = go1 y (go1 x n)

And this is what we get if we define foldl' and toList in terms of foldrW
and buildW.

I think a similar problem arises whenever you define a good consumer that
traverses a tree-like structure, and you want to use a strict fold to
consume a list produced by that producer.

Thank you,
Takano Akio

>
>
> Simon
>
>
>
> *From:* ghc-devs [mailto:ghc-devs-bounces at haskell.org] *On Behalf Of *Akio
> Takano
> *Sent:* 09 January 2014 13:25
> *To:* ghc-devs
> *Subject:* Re: Extending fold/build fusion
>
>
>
> Any input on this is appreciated. In particular, I'd like to know: if I
> implement the idea as a patch to the base package, is there a chance it is
> considered for merge?
>
>
> -- Takano Akio
>
> On Fri, Jan 3, 2014 at 11:20 PM, Akio Takano <tkn.akio at gmail.com> wrote:
>
>  Hi,
>
> I have been thinking about how foldl' can be turned into a good consumer,
> and I came up with something that I thought would work. So I'd like to ask
> for opinions from the ghc devs: if this idea looks good, if it is a known
> bad idea, if there is a better way to do it, etc.
>
> The main idea is to have an extended version of foldr:
>
> -- | A mapping between @a@ and @b at .
> data Wrap a b = Wrap (a -> b) (b -> a)
>
> foldrW
>   :: (forall e. Wrap (f e) (e -> b -> b))
>   -> (a -> b -> b) -> b -> [a] -> b
> foldrW (Wrap wrap unwrap) f z0 list0 = wrap go list0 z0
>   where
>     go = unwrap $ \list z' -> case list of
>       [] -> z'
>       x:xs -> f x $ wrap go xs z'
>
> This allows the user to apply an arbitrary "worker-wrapper" transformation
> to the loop.
>
> Using this, foldl' can be defined as
>
> newtype Simple b e = Simple { runSimple :: e -> b -> b }
>
> foldl' :: (b -> a -> b) -> b -> [a] -> b
> foldl' f initial xs = foldrW (Wrap wrap unwrap) g id xs initial
>   where
>     wrap (Simple s) e k a = k $ s e a
>     unwrap u = Simple $ \e -> u e id
>     g x next acc = next $! f acc x
>
> The wrap and unwrap functions here ensure that foldl' gets compiled into a
> loop that returns a value of 'b', rather than a function  'b -> b',
> effectively un-CPS-transforming the loop.
>
> I put preliminary code and some more explanation on Github:
>
> https://github.com/takano-akio/ww-fusion
>
> Thank you,
> Takano Akio
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20140114/ce893cb8/attachment-0001.html>