[GHC] #9496: Simplify primitives for short cut fusion
#9496: Simplify primitives for short cut fusion -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: task | Status: new Priority: normal | Milestone: Component: libraries/base | Version: 7.8.3 Keywords: fusion | Operating System: Architecture: Unknown/Multiple | Unknown/Multiple Difficulty: Unknown | Type of failure: Other Blocked By: | Test Case: Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Currently, there appear to be two production primitives, `build` and `augment` (although I may have missed some). There are multiple consumption primitives (at least: `foldr`, `head`, `and`, `or`, `any`, and `all`). The rule sets for some producers seem to forget to handle `augment`, and the `augment/augment` rule is omitted as "true, but not, I think, useful". A number of other functions are instead rewritten into `foldr` forms, and then written back if they don't fuse. == What to do: == Personally, I'd be very tempted to start by saying `build g = augment g []` (or ''possibly'' even `build g = extend [] g []` if I can ever get that idea to work) and cut the problem in half. The main problem I see with this is if other people are importing `GHC.Exts` or `GHC.Base`, writing things with `build`, and expecting them to fuse. One way to deal with this, perhaps, is to hack a special rule into the RULES compiler to recognize `GHC.Base.build` on the LHS of RULES and replace it with the appropriate `augment` form, emitting a warning. Where to go after that: the question remains whether it's best in general to rewrite a form to `foldr` to make it fuse, or to fuse directly with `augment`. The answer presumably depends, at least in part, on whether there are additional `foldr`-based rules we may want to add that would take advantage of the effort put into the translation back from the `foldr` form. I would conjecture that most such rules we could want would go beyond what the RULES system actually can do. That said, if we can find a way to use `foldr` forms without the horrible pain of translating back from them, that would be a very good thing. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9496 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9496: Simplify primitives for short cut fusion -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: Component: | Version: 7.8.3 libraries/base | Keywords: fusion Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Other | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by dfeuer): * owner: => dfeuer -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9496#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9496: Simplify primitives for short cut fusion -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: Component: | Version: 7.8.3 libraries/base | Keywords: fusion Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Other | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by simonpj): I believe that there are good reasons for distinguishing build and augment. [http://research.microsoft.com/en-us/um/people/simonpj/papers /andy-thesis.ps.gz Andy Gill's thesis] would be a good place to look. But perhaps one could do everything in terms of augment; I'm not sure. Worth a try. I think there is really only one primitive consumer, foldr. I thought we rewrote into foldr and then back. If that is not done for or, any, etc, I'm not sure why. Again, perhaps worth investigation. Certainly the original goal of the foldr/build paper was to say "ONE rule, not n*m rules". Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9496#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9496: Simplify primitives for short cut fusion -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: Component: | Version: 7.8.3 libraries/base | Keywords: fusion Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Other | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:2 simonpj]:
I believe that there are good reasons for distinguishing build and augment. [http://research.microsoft.com/en-us/um/people/simonpj/papers /andy-thesis.ps.gz Andy Gill's thesis] would be a good place to look. But perhaps one could do everything in terms of augment; I'm not sure. Worth a try.
I think there is really only one primitive consumer, foldr. I thought we rewrote into foldr and then back. If that is not done for or, any, etc, I'm not sure why. Again, perhaps worth investigation.
Certainly the original goal of the foldr/build paper was to say "ONE rule, not n*m rules".
Simon
An aside: Just last night I saw a bit of the work Takano Akio has done on incorporating a worker/wrapper transformation into the framework (although I don't quite understand how it works yet). It doesn't seem to be quite ready for prime time (there were apparently some issues with one NoFib benchmark), but we might want to keep it in mind. I think the one rule concept is great. If that can be made to really work, that would be ''ideal''. Unfortunately, the need to wrangle the inliner as it currently works turns the one rule concept into an n*m-rule concept, where m is certainly at least 1, but currently 2 (the rewrite back rule clearly seems necessary for now—I don't yet understand things deeply enough to know for sure if the rewrite to rule is strictly necessary in all cases). I would speculate that the and/or/any/head/... rules came about because someone thought to themselves "There's only one [sic] consumer, `build`, so we can skip this difficult and invasive rewrite to/from process and just fuse with `build`. That's easy!" Well, they were a little wrong, but I'm not sure they were very wrong. I haven't had a chance to read the thesis yet, but from a purely practical perspective, I don't see any difference between `build g` and `augment g []`. I don't ''think'' anyone's tossing around partially applied `augment`s or anything. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9496#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#9496: Simplify primitives for short cut fusion -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: lowest | Milestone: ⊥ Component: Core | Version: 7.8.3 Libraries | Keywords: fusion Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Other | Related Tickets: Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Changes (by dfeuer): * cc: core-libraries-committee@… (added) * priority: normal => lowest * milestone: => ⊥ Comment: Duncan Coutts doesn't seem to think this is really a problem, per se. It even has an advantage: we avoid speculative rewrites that can be bad. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9496#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC