Revise list fusion for and, or, all, any, elem, notElem (#13351)
Needs RevisionPublic

Authored by nomeata on Feb 28 2017, 3:42 PM.

Details

Summary

to make sure their list fusion is implemented in terms of foldr (and not
build directly), with proper writing-back rules.

This ensures that, for example,

c `elem` "!@#$%^&*()"

works without actual list code.

Also, for good measure, add foldr fusion rules for short lists, and
make the comment there more useful.

Test Plan

run validate

nomeata created this revision.Feb 28 2017, 3:42 PM

If this all works out okay, it will also make @bgamari's cheapBuild considerably easier to handle, since it will only have to fuse with foldr.

simonpj accepted this revision.Mar 1 2017, 3:09 AM
simonpj added a subscriber: simonpj.

Looks good. Obviously check perf carefully

If this all works out okay, it will also make @bgamari's cheapBuild considerably easier to handle, since it will only have to fuse with foldr.

Not sure what this means. What else did it need to fuse with before??

This revision is now accepted and ready to land.Mar 1 2017, 3:09 AM
dfeuer added a comment.Mar 1 2017, 6:31 AM

If this all works out okay, it will also make @bgamari's cheapBuild considerably easier to handle, since it will only have to fuse with foldr.

Not sure what this means. What else did it need to fuse with before??

and, or, all, any, elem, and notElem, at least.

dfeuer added a comment.Mar 1 2017, 6:32 AM

Well, maybe not and and or, but the rest.

dfeuer requested changes to this revision.Mar 1 2017, 11:49 AM

Can you indicate what results you get from nofib?

This revision now requires changes to proceed.Mar 1 2017, 11:49 AM
nomeata updated this revision to Diff 11465.Mar 1 2017, 12:15 PM

Try to make T2110 more robust

and, or, all, any, elem, and notElem, at least.

We have never done ad-hoc fusion rules. We've always expressed things in terms for foldr and buld, and let the fold/build rule do the hard work.

Should be the same with cheapBuild

dfeuer added a comment.Mar 1 2017, 5:17 PM

and, or, all, any, elem, and notElem, at least.

We have never done ad-hoc fusion rules. We've always expressed things in terms for foldr and buld, and let the fold/build rule do the hard work.

Should be the same with cheapBuild

Our rules have (I believe) all included either foldr or build. If you look at the rules that change here, you'll see, for example, that we currently have

"any/build"     forall p (g::forall b.(a->b->b)->b->b) .
                any p (build g) = g ((||) . p) False

I believe what @nomeata is trying to do is to make a much more stringent policy: that everything must go through foldr. This seems to make good sense, because there seem to be more interesting variations on the production side than the consumption side: build, augment, cheapBuild (?), and perhaps the special cases for short lists. The big question is whether the inliner will be sufficiently happy with these expansions.

If you look at the rules that change here, you'll see, for example, that we currently have

Crumbs! That's terrible! Of course we should be using foldr for 'any', 'all' etc.

nomeata updated this revision to Diff 11475.Mar 1 2017, 8:32 PM

Test suite update

Gipeda results are in: https://perf.haskell.org/ghc/#revision/b112f4604811faa6f5aeb399d8b5ee575f413bb7.

It definitely looks like there is more work to do here.

Gipeda results are in: https://perf.haskell.org/ghc/#revision/b112f4604811faa6f5aeb399d8b5ee575f413bb7.

It definitely looks like there is more work to do here.

Indeed. Let me split the patch into the the one for small lists and the one about the library functions.

bgamari requested changes to this revision.Mar 3 2017, 4:47 PM

Bumping out of the review queue for now.

This revision now requires changes to proceed.Mar 3 2017, 4:47 PM

Bumping out of the review queue for now.

Thanks. perf.haskell.org is currently having trouble to keep up with GHC development. I guess that is a good sign :-)

Ok, all reported performance changes are due to the changes to the list functions, and not due to fusing short lists.

We have a runtime improvement for cryptarithm, but allocation increases for fluid and prolog.

Don’t have time to look into them immoderately.

bgamari requested changes to this revision.Mar 19 2017, 10:13 AM

Bumping out of review queue due to apparent nofib regressions. Let me know when you would like a review, @nomeata!

This revision now requires changes to proceed.Mar 19 2017, 10:13 AM
austin resigned from this revision.Nov 9 2017, 9:43 AM