Replace most occurences of foldl with foldl'.
Needs ReviewPublic

Authored by AndreasK on Tue, Jul 3, 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
Branch
arcpatch-D4929
Lint
Lint WarningsExcuse: preserve layout
SeverityLocationCodeMessage
Warningcompiler\hsSyn\HsUtils.hs:424TXT3Line Too Long
Warningcompiler\simplCore\Simplify.hs:298TXT3Line Too Long
Warningcompiler\typecheck\TcExpr.hs:2744TXT3Line Too Long
Warningcompiler\typecheck\TcGenDeriv.hs:1365TXT3Line Too Long
Warningcompiler\typecheck\TcPatSyn.hs:721TXT3Line Too Long
Warningcompiler\typecheck\TcValidity.hs:1776TXT3Line Too Long
Unit
No Unit Test Coverage
Build Status
Buildable 21767
Build 49837: [GHC] Linux/amd64: Continuous Integration
Build 49836: [GHC] OSX/amd64: Continuous Integration
Build 49835: [GHC] Windows/amd64: Continuous Integration
Build 49834: arc lint + arc unit
AndreasK created this revision.Tue, Jul 3, 7:12 AM
AndreasK updated this revision to Diff 17173.Tue, Jul 3, 10:23 AM
  • Remove redundant import
tdammers requested changes to this revision.Wed, Jul 4, 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
85

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.Wed, Jul 4, 10:59 AM
AndreasK planned changes to this revision.Wed, Jul 4, 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
85

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.Mon, Jul 9, 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.Mon, Jul 9, 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
700–702

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.Thu, Jul 12, 6:22 PM