Opened 5 years ago

Closed 5 years ago

Last modified 5 years ago

#9781 closed task (fixed)

Make list monad operations fuse

Reported by: dfeuer Owned by: dfeuer
Priority: normal Milestone: 7.10.1
Component: Core Libraries Version: 7.9
Keywords: Cc: core-libraries-committee@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s): Phab:D455
Wiki Page:

Description

We like to think that do {x <- xs; y <- f x ; return g y} is the same as [g y | x <- xs, y <- f x], but the former does not fuse nearly as well. Let's fix that.

Change History (8)

comment:1 Changed 5 years ago by 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.

comment:2 in reply to:  1 Changed 5 years ago by dfeuer

Replying to 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.

comment:3 Changed 5 years ago by dfeuer

Status: newpatch

comment:4 Changed 5 years ago by Herbert Valerio Riedel <hvr@…>

In 4923cea56345060faaf77e4c475eac6aa3c77506/ghc:

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

comment:5 Changed 5 years ago by nomeata

Resolution: fixed
Status: patchclosed

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.)

comment:6 in reply to:  5 Changed 5 years ago by dfeuer

Replying to 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.

comment:7 Changed 5 years ago by 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?)

comment:8 in reply to:  7 Changed 5 years ago by dfeuer

Replying to 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.

Note: See TracTickets for help on using tickets.