Replace most occurences of foldl with foldl'.
ClosedPublic

Authored by AndreasK on Jul 3 2018, 7:12 AM.

Details

Summary

This patch adds foldl' to GhcPrelude and changes must occurences
of foldl to foldl'. This leads to better performance especially
for quick builds where GHC does not perform strictness analysis.

It does change strictness behaviour when we use foldl' to turn
a argument list into function applications. But this is only a
drawback if code looks ONLY at the last argument but not at the first.
And as the benchmarks show leads to fewer allocations in practice
at O2.

Compiler performance for Nofib:

O2 Allocations:

-1 s.d.                -----            -0.0%
+1 s.d.                -----            -0.0%
Average                -----            -0.0%

O2 Compile Time:

-1 s.d.                -----            -2.8%
+1 s.d.                -----            +1.3%
Average                -----            -0.8%

O0 Allocations:

-1 s.d.                -----            -0.2%
+1 s.d.                -----            -0.1%
Average                -----            -0.2%
Test Plan

ci

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.
AndreasK created this revision.Jul 3 2018, 7:12 AM
AndreasK updated this revision to Diff 17173.Jul 3 2018, 10:23 AM
  • Remove redundant import
tdammers requested changes to this revision.Jul 4 2018, 10:59 AM
tdammers added a subscriber: tdammers.

Would it be possible to see the performance improvements reflected in the test suite somewhere? E.g., by adding a test that compiles a program that would benefit a lot from this in terms of compilation time?

compiler/codeGen/StgCmmEnv.hs
121 ↗(On Diff #17173)

This is one of the cases where I would abandon the Boy Scout Rule, and leave the original bad layout in place; and then maybe do the cleanup in a separate commit. Otherwise, the actual change (adding a single ') is easily obscured here.

compiler/deSugar/DsUtils.hs
86

necessary change?

compiler/utils/GhcPrelude.hs
22

Why not import foldl' into the X namespace here as well? Exposing this one name individually, while everything else gets wrapped up in X, seems a bit awkward.

This revision now requires changes to proceed.Jul 4 2018, 10:59 AM
AndreasK planned changes to this revision.Jul 4 2018, 4:46 PM

I plan to address the inline notes and incorporate the changes from the other foldl' patch.

Would it be possible to see the performance improvements reflected in the test suite somewhere? E.g., by adding a test that compiles a program that would benefit a lot from this in terms of compilation time?

Given that the difference is so small that seems unlikely. I've had to look at all of nofib for the allocations because for a single file there was enough noise to drown out the actual changes.
But if you have an idea feel free to just push it into this diff.

And thanks for taking the time to look this over!

compiler/codeGen/StgCmmEnv.hs
121 ↗(On Diff #17173)

Otherwise, the actual change (adding a single ') is easily obscured here.

I guess that's true. I will see to keep the layout.

maybe do the cleanup in a separate commit.

That will be a Nothing for me but maybe someone else will :)

compiler/deSugar/DsUtils.hs
86

A result of initially adding import for foldl' everywhere and removing them again later.
Will change this.

compiler/utils/GhcPrelude.hs
22

It's just more explicit. I don't have strong feels either way so I will change it.

AndreasK updated this revision to Diff 17244.Jul 9 2018, 12:24 PM
  • Remove redundant import(s)
  • Replace a few more foldl instances.
  • Use X namespace in GhcPrelude
  • Incorporate phab feedback
AndreasK marked 5 inline comments as done.Jul 9 2018, 12:27 PM

I'm not entirely sure what to think about this. Do you think that the compile time reduction at -O2 are real? I'm a bit suspicious given that allocations are unchanged. The change at -O0 is nice and the cost of merging is relatively low, I suppose

compiler/typecheck/TcPatSyn.hs
929–930

Indentation.

compiler/types/Coercion.hs
765–767

Can you fix the indentation here?

Do you think that the compile time reduction at -O2 are real? I'm a bit suspicious given that allocations are unchanged.

I do expect the compiler to get faster. But I think -0.8% is - for the most part - noise/luck.
But then again if it saves us one GC collection it might be true.

However I don't see a scenario where I would expect it to make performance worse.
So I did not go through the trouble to make an effort for good benchmarks.

Also there is a difference at O2, it's just so small that it gets rounded up to -0.0.
When there is zero difference nofib reports 0.0% (without sign) for the individual benchmarks and +0.0% for the total.

AndreasK marked 2 inline comments as done.Jul 12 2018, 6:22 PM
bgamari accepted this revision.Jul 16 2018, 10:34 AM

Looks good!

monoidal accepted this revision.Aug 12 2018, 3:56 PM
This revision was not accepted when it landed; it landed in state Needs Review.Aug 21 2018, 6:00 PM
This revision was automatically updated to reflect the committed changes.