[GHC] #9434: GHC.List.reverse does not fuse

[David Feuer]

I'm working on it, based on a discussion with Dan Doel. That said,
Haskell's supposed to be anti-pattern, and rewrite/transform/write-back is
definitely a pattern—and a somewhat painful one. Aside from having to use
forms that can be matched on (intentionally blinding the inliner) there's
the unfortunate fact that the written-back forms have to be hand-written
recursive definitions. That's what made me think about a CSE-like cleanup
pass, despite not knowing nearly enough to be able to write it myself just
yet. I wouldn't want full CSE, but rather just to merge identical top-level
lambda forms, which I *think* should avoid potential performance issues
caused by full CSE. Some challenges relating to the idea:

1. It would be very nice if named forms were given preference. So if there
are two copies of \foo -> bar, and the programmer has named one of them
baz, then they should ideally be merged to baz, rather than to quux17. No,
I have no idea what might be involved.

2. In a sufficiently large module, compilation speed could theoretically be
a problem. I don't think this is likely, however, especially since distinct
expressions usually diverge fairly high in their syntax trees.

3. If there are a *lot* of copies of some functions, the copies could make
the Core harder to read. I would conjecture that this will not happen often.
On Aug 17, 2014 6:13 PM, "Simon Peyton Jones" <simonpj at microsoft.com> wrote:

>  Well, I’d *much* rather avoid creating the duplication in the first
> place, than to create and try to CSE it away.  Others have suggested ways
> of doing so, following the pattern of existing RULES.
>
>
>
> Simon
>
>
>
> *From:* David Feuer [mailto:david.feuer at gmail.com]
> *Sent:* 15 August 2014 16:41
> *To:* ghc-devs; Simon Peyton Jones
> *Subject:* Re: [GHC] #9434: GHC.List.reverse does not fuse
>
>
>
> I'm having trouble when it doesn't fuse—it ends up with duplicate bindings
> at the top level, because build gets inlined n times, and the result lifted
> out. Nothing's *wrong* with the code, except that there are multiple copies
> of it.
>
> On Aug 15, 2014 10:58 AM, "GHC" <ghc-devs at haskell.org> wrote:
>
> #9434: GHC.List.reverse does not fuse
> -------------------------------------+-------------------------------------
>               Reporter:  dfeuer      |            Owner:
>                   Type:  bug         |           Status:  new
>               Priority:  normal      |        Milestone:
>              Component:              |          Version:  7.9
>   libraries/base                     |         Keywords:
>             Resolution:              |     Architecture:  Unknown/Multiple
>       Operating System:              |       Difficulty:  Easy (less than 1
>   Unknown/Multiple                   |  hour)
>        Type of failure:  Runtime     |       Blocked By:
>   performance bug                    |  Related Tickets:
>              Test Case:              |
>               Blocking:              |
> Differential Revisions:              |
> -------------------------------------+-------------------------------------
>
> Comment (by simonpj):
>
>  Great.  Just check that when fusion ''doesn't'' take place, the result is
>  good. And do a `nofib` comparison for good luck. Then submit a patch.
>
>  Thanks for doing all this work on fusion, David.
>
>  Simon
>
> --
> Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/9434#comment:2>
> GHC <http://www.haskell.org/ghc/>
> The Glasgow Haskell Compiler
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/ghc-devs/attachments/20140817/ad28218e/attachment.html>