Add fusion rules for the zipWith functions in base (#15263)
ClosedPublic

Authored by TDecki on Oct 18 2018, 6:10 PM.

Details

Summary

This patch will allow zip3 and zipWith3 in GHC.List as well
as zipWith4, zipWith5, zipWith6 and zipWith7 in Data.OldList to fuse.

These rules are kept in a similar style as the rules for zip and zipWith.

Added a corresponding test case.

Test Plan

validate

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
TDecki created this revision.Oct 18 2018, 6:10 PM
Harbormaster edited this Differential Revision.Oct 19 2018, 5:04 AM
TDecki edited the summary of this revision. (Show Details)Oct 23 2018, 9:34 AM

Is this in any way related to D5249?

Sorry for the delay in review.

No, this work is independent from it and is dealing with a different ticket.
The ticket of D5249 however has the addition of these fusion rules as a goal,
and I'm sorry to say that I was unaware of that.

I related those two tickets.

I was unaware of this ticket. I do not mind removing these changes from D5249 so the two differentials do not collide. You've also added comments and a performance test, whereas I did neither.

@bgamari When can I expect a review?

Shouldn't we update the documentation of these to reflect the fact that the first argument is subject to fusion?

Otherwise looks reasonable to me.

TDecki updated this revision to Diff 18576.EditedNov 2 2018, 2:29 PM

Updated release notes.

They now mention the new fusion rules
for zipWith3 and related

bgamari requested changes to this revision.Nov 2 2018, 2:54 PM

My apologies, @TDecki; I should have been clearer. The release notes reference is great too but I originally meant the Haddocks of zip3 and friends.

This revision now requires changes to proceed.Nov 2 2018, 2:54 PM
TDecki updated this revision to Diff 18578.EditedNov 2 2018, 3:30 PM

Updated documentation.

Readers will now be informed about zip fusion,
as well as its limitations.

When this is done, I'll update D5249 to reflect these changes.

rockbmb added inline comments.Thu, Nov 15, 4:22 PM
libraries/base/GHC/List.hs
991

Since this issue is on the topic of improving zipping functions, I have a suggestion to make here: can the order of these pattern matches be changed so that this clause comes first?

When lists have relatively large lengths, the two first clauses (to check whether the first or second lists are empty) will be repeatedly matched until one is exhausted, meaning each iteration of zip do 3 pattern matches instead of one. Reordering clauses might be a performance improvement.

TDecki added inline comments.Fri, Nov 16, 9:48 AM
libraries/base/GHC/List.hs
991

I decided to test this and examined the core output of both variants.
Apparrently, passing any optimisation flag causes both variants to compile to the exact same code,
so I'm not inclined to make a change here.

@bgamari The documentation has been updated for a while now. Can you please take a look at the changes?

simonpj accepted this revision.Mon, Dec 3, 5:35 AM
simonpj added a subscriber: simonpj.

generally looks ok to me, thank you. (Although I have not checked every line.) Ben: merge this?

rockbmb added inline comments.Mon, Dec 3, 11:26 AM
libraries/base/GHC/List.hs
991

Alright, I was not aware it would compile to the same code, thanks.

bgamari accepted this revision.Thu, Dec 6, 2:34 PM

Looks good to me.

This revision is now accepted and ready to land.Thu, Dec 6, 2:34 PM
This revision was automatically updated to reflect the committed changes.