Extending fold/build fusion

[Dan Doel]

I've been looking into this a bit in the past day or so, and I feel like
some of the stuff in the repository doesn't make sense (to me, at least).

For instance, if you start examining the generated code, you'll see quirks
like, taking map as an example:

    map f xs = go xs []
      where
      go xs n = case xs of
        [] -> n
        y:ys -> f y : go ys n

In other words, the loop passes along the empty list in an argument for the
base case, which is a waste. This stems from the definition of foldrW:

    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'

Specifically, the z' becomes this extra threaded argument, and never
disappears. It is possible to fix this by changing the definition of foldrW
to be:

    ...
        [] -> z0
    ...

And ghc then recognizes that the z' being threaded is useless and
eliminates it. But this raises the question of why it's being threaded this
way in the first place. It seems like the types in Wrap are inappropriate
in some way, at least for the general case. But I'm not yet certain what
they should be.

There are also fusion problems with the current implementation that neither
I nor David have fully figured out yet. For instance:

    bar = map (+1) (eft 0 1000)

does not fuse, even after trying many tweaks to the definitions (due to the
eft 0 1000 being pulled out into a let for reasons we don't yet understand;
it even happens with -fno-full-laziness). However:

    bar = foldl (+) 0 (map (+1) (eft 0 1000))

fuses fully. The only way to fix the former I've yet found is making buildW
CONLIKE, but that may not be appropriate in general (probably isn't). I
have a sneaking suspicion that the strangeness mentioned in the first part
of this mail may be a contributing factor to this latter issue, too.

-- Dan


On Wed, Sep 3, 2014 at 3:47 PM, Joachim Breitner <mail at joachim-breitner.de>
wrote:

> Dear Akio,
>
>
> Am Mittwoch, den 12.03.2014, 19:36 +0100 schrieb Joachim Breitner:
> > Dear Akio,
> >
> > Am Dienstag, den 11.02.2014, 08:04 +0900 schrieb Akio Takano:
> > > I modified the base library to use foldrW/buildW, with no changes to
> > > foldl yet. nofib showed a very big regression in cryptarithm2, so I'm
> > > looking into it.
> >
> > any news on this front? Did you find out what happened in cryptarithm2?
> > Do you need help with that?
>
> I haven’t heard from you in quite some time. Are you still on this
> project?
>
> Recent investigations into fusion by David Feuer has increased interest
> in your approach (https://ghc.haskell.org/trac/ghc/ticket/9545).
>
> Greetings,
> Joachim
>
>
> --
> Joachim “nomeata” Breitner
>   mail at joachim-breitner.de • http://www.joachim-breitner.de/
>   Jabber: nomeata at joachim-breitner.de  • GPG-Key: 0xF0FBF51F
>   Debian Developer: nomeata at debian.org
>
>
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://www.haskell.org/mailman/listinfo/ghc-devs
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20140904/2123d353/attachment.html>