#9781: Make list monad operations fuse -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: 7.10.1 Component: Core | Version: 7.9 Libraries | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: performance bug | Test Case: | Blocking: | Differential Revisions: Phab:D455 | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:1 ekmett]:

I have no issues with improving fusion for do sugared lists, the question is if it is possible to achieve this change with just a libraries fix or if you need to go into the compiler.

There is a lot of crazy code down in the list comprehension module that gets used to make lists fast there. It isn't clear to me how we'd lean on it.

The easy way is to ''use'' the list comprehension desugaring, as in the linked code review. The hard way (because it makes us hide it in some imports) is to move `concatMap` from `GHC.List` into `GHC.Base` and use `xs >>= f = concatMap f xs`, etc. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9781#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9781: Make list monad operations fuse -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: patch Priority: normal | Milestone: 7.10.1 Component: Core | Version: 7.9 Libraries | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: performance bug | Test Case: | Blocking: | Differential Revisions: Phab:D455 | -------------------------------------+------------------------------------- Comment (by Herbert Valerio Riedel ): In [changeset:"4923cea56345060faaf77e4c475eac6aa3c77506/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="4923cea56345060faaf77e4c475eac6aa3c77506" Define list monad operations using comprehensions Define list monad operations using list comprehensions. Code using monad operations with lists did not fuse fully. Writing list code with `do` notation or `(>>=)` and `(>>)` operations could allocate more than equivalent code using list comprehensions. Define `mapM` directly, instead of using `sequence` and `map`. This leads to substantially less allocation in `cryptarithm2`. Addresses #9781 Reviewed By: ekmett, nomeata Differential Revision: https://phabricator.haskell.org/D455 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9781#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9781: Make list monad operations fuse -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: closed Priority: normal | Milestone: 7.10.1 Component: Core | Version: 7.9 Libraries | Keywords: Resolution: fixed | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: performance bug | Test Case: | Blocking: | Differential Revisions: Phab:D455 | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:5 nomeata]:

This showed some minor performance improvements, and one huge one, as you noticed already: cryptarithm2’s allocation went down by more than 50%!

(I just spent a few minutes looking for list monad operations in that benchmark until I noticed that your commit also had an unrelated(?) change to mapM.)

The change also improves cryptarithm2 without the `mapM` change, but not as much. So there must have been something else. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9781#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9781: Make list monad operations fuse -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: dfeuer Type: task | Status: closed Priority: normal | Milestone: 7.10.1 Component: Core | Version: 7.9 Libraries | Keywords: Resolution: fixed | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Runtime | Related Tickets: performance bug | Test Case: | Blocking: | Differential Revisions: Phab:D455 | -------------------------------------+------------------------------------- Comment (by dfeuer): Replying to [comment:7 schyler]:

It would be nice to understand why the `mapM` change did anything at all. That's an enormous difference. I wonder how much real code in the wild has similar properties (is it a lack of INLINEing?)

I believe it's either a lack of inlining or an unfortunate effect of full laziness. I haven't tried to dig into that particular one so deeply. Short cut fusion is great stuff, but it's on the finicky side; writing library functions so they don't themselves rely on it seems to be a good idea in many cases. The inliner will be less likely to over-estimate their cost, I believe. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9781#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler