Extending fold/build fusion

[Akio Takano]

Hi Joachim,

On Wed, Jan 29, 2014 at 3:06 AM, Joachim Breitner
<mail at joachim-breitner.de> wrote:
> Dear Akio,
>
> Am Freitag, den 03.01.2014, 23:20 +0900 schrieb Akio Takano:
>> 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.
>
> I'd like to evaluate your approach, but let me first note that I had
> been working on #7994 (make foldl a good consumer), and with my patches
> the compiler is smart enough to eta-expand go in all cases covered by
> nofib, using the existing foldr/build-fusion.

Nice.

>
> That said, I do like your idea of making the worker/wrapper a bit more
> explicit, instead of relying on the compiler to do the transformation
> for us. So let's see in what ways your proposal surpasses a smarter GHC.
>
>
> The Tree example is a good one, because there any form of eta expansion,
> just as you write, will not help. And I find that that Simons's solution
> of using a foldr-based sum for Trees unsatisfying: We should indeed aim
> for "sum $ toList tree" to produce good results. Given that Data.Map is
> a tree, and that is a common data structure and it's toList a good
> producer, this is relevant.

I agree. In fact, my original motivation was that I wanted to
efficiently serialize a IntMap into a ByteString.

>
>
> Can you implement build via buildW, so that existing code like
>   "map"  [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
> can be used unmodified? But probably not... but that would mean a
> noticeable incompatibility and a burden on library authors using list
> fusion.

You can implement build in terms of buildW. However any list producer
defined using that definition of build would produce good code if the
final consumer is a left fold. The resulting code will be in CPS. On
the other hand, I imagine that if we also annotate foldl with oneShot,
this problem may become less severe.

>
>
> In any case, I suggest you just dig in, create a branch of
> libraries/base and replace everything related to foldr/builder with your
> approach. First, do not actually change the definition of foldl. Then
> compare the nofib testruns (probably best with two separate working repo
> clones, starting from "make distclean"): Do the results differ? A lot of
> work went into foldr/build-fusion, so we want to be sure that we are not
> losing anything anywhere (or if we are, we want to know why).
>
> Then make foldl and foldl' a good consumer, as in the patch at the
> beginning of #7994. How large are the gains? How do they compare with
> the gains from the smarter GHC (numbers also in the ticket).
>
> If by then we have not found any regression, things look promising.

Thank you for the advice, I'll have a try.

- Akio

>
> Greetings, and I hope the delayed responses do not lesen your
> motivation,
> Joachim
>
> PS: I'm subscribed to the mailinglist, no need to CC me explicitly.
>
> --
> Joachim "nomeata" Breitner
>   mail at joachim-breitner.de * http://www.joachim-breitner.de/
>   Jabber: nomeata at joachim-breitner.de  * GPG-Key: 0x4743206C
>   Debian Developer: nomeata at debian.org