Details

Reviewers

goldfire
bgamari
simonmar
tdammers
monoidal

Commits

rGHC09c1d5afba65: Replace most occurences of foldl with foldl'.

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

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

Herald added a reviewer: goldfire. · View Herald TranscriptJul 3 2018, 7:12 AM

Herald added a reviewer: goldfire. · View Herald Transcript

Herald added a reviewer: bgamari. · View Herald Transcript

Herald added a reviewer: simonmar. · View Herald Transcript

Herald added subscribers: carter, thomie, rwbarton. · View Herald Transcript

Harbormaster failed remote builds in B21597: Diff 17170!Jul 3 2018, 9:03 AM

Remove redundant import

Harbormaster failed remote builds in B21600: Diff 17173!Jul 4 2018, 10:56 AM

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

tdammers mentioned this in D4847: UniqFM: Use foldl' instead of fold.Jul 4 2018, 3:22 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.

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?

In D4929#136546, @bgamari wrote:

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.

Layout

AndreasK marked 2 inline comments as done.Jul 12 2018, 6:22 PM

Harbormaster failed remote builds in B21767: Diff 17292!Jul 13 2018, 8:22 AM

Looks good!

Harbormaster completed remote builds in B21679: Diff 17244.Aug 2 2018, 7:16 PM

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

Closed by commit rGHC09c1d5afba65: Replace most occurences of foldl with foldl'. (authored by AndreasK, committed by bgamari). · Explain Why

This revision was automatically updated to reflect the committed changes.

			Path	Packages
M			compiler/basicTypes/Avail.hs (2 lines)
M			compiler/basicTypes/NameCache.hs (2 lines)
M			compiler/basicTypes/NameSet.hs (2 lines)
M			compiler/basicTypes/OccName.hs (2 lines)
M			compiler/basicTypes/RdrName.hs (4 lines)
M			compiler/basicTypes/VarEnv.hs (2 lines)
M			compiler/cmm/CmmContFlowOpt.hs (1 line)
M			compiler/cmm/CmmExpr.hs (1 line)
M			compiler/cmm/CmmSink.hs (1 line)
M			compiler/cmm/Hoopl/Dataflow.hs (1 line)
M			compiler/codeGen/StgCmmMonad.hs (2 lines)
M			compiler/coreSyn/CoreArity.hs (2 lines)
M			compiler/coreSyn/CoreMap.hs (4 lines)
M			compiler/coreSyn/CoreOpt.hs (4 lines)
M			compiler/coreSyn/CoreSyn.hs (8 lines)
M			compiler/deSugar/DsExpr.hs (2 lines)
M			compiler/deSugar/DsForeign.hs (2 lines)
M			compiler/deSugar/DsMeta.hs (2 lines)
M			compiler/deSugar/DsUtils.hs (2 lines)
M			compiler/deSugar/Match.hs (4 lines)
M			compiler/hsSyn/HsTypes.hs (3 lines)
M			compiler/hsSyn/HsUtils.hs (14 lines)
M			compiler/iface/MkIface.hs (2 lines)
M			compiler/iface/TcIface.hs (1 line)
M			compiler/iface/ToIface.hs (2 lines)
M			compiler/main/Ar.hs (2 lines)
M			compiler/main/DynFlags.hs (2 lines)
M			compiler/main/GhcMake.hs (2 lines)
M			compiler/main/HscTypes.hs (5 lines)
M			compiler/main/Packages.hs (4 lines)
M			compiler/nativeGen/AsmCodeGen.hs (4 lines)
M			compiler/nativeGen/RegAlloc/Graph/Coalesce.hs (2 lines)
M			compiler/nativeGen/RegAlloc/Graph/Main.hs (1 line)
M			compiler/nativeGen/RegAlloc/Graph/Stats.hs (3 lines)
M			compiler/nativeGen/RegAlloc/Linear/Stats.hs (1 line)
M			compiler/prelude/PrelInfo.hs (4 lines)
M			compiler/rename/RnNames.hs (2 lines)
M			compiler/simplCore/CallArity.hs (2 lines)
M			compiler/simplCore/FloatIn.hs (4 lines)
M			compiler/simplCore/OccurAnal.hs (2 lines)
M			compiler/simplCore/SetLevels.hs (18 lines)
M			compiler/simplCore/Simplify.hs (4 lines)
M			compiler/specialise/Rules.hs (4 lines)
M			compiler/specialise/Specialise.hs (2 lines)
M			compiler/stranal/DmdAnal.hs (4 lines)
M			compiler/typecheck/FunDeps.hs (2 lines)
M			compiler/typecheck/TcEvidence.hs (2 lines)
M			compiler/typecheck/TcExpr.hs (2 lines)
M			compiler/typecheck/TcGenDeriv.hs (4 lines)
M			compiler/typecheck/TcGenFunctor.hs (2 lines)
M			compiler/typecheck/TcInstDcls.hs (4 lines)
M			compiler/typecheck/TcPatSyn.hs (6 lines)
M			compiler/typecheck/TcRnTypes.hs (2 lines)
M			compiler/typecheck/TcSigs.hs (2 lines)
M			compiler/typecheck/TcSplice.hs (2 lines)
M			compiler/typecheck/TcType.hs (6 lines)
M			compiler/typecheck/TcValidity.hs (2 lines)
M			compiler/types/Coercion.hs (8 lines)
M			compiler/types/FamInstEnv.hs (2 lines)
M			compiler/types/InstEnv.hs (2 lines)
M			compiler/types/Type.hs (4 lines)
M			compiler/types/Unify.hs (2 lines)
M			compiler/utils/FiniteMap.hs (6 lines)
M			compiler/utils/GhcPrelude.hs (2 lines)
M			compiler/utils/ListSetOps.hs (2 lines)
M			compiler/utils/UnVarGraph.hs (1 line)
M			compiler/utils/UniqDFM.hs (12 lines)
M			compiler/utils/UniqDSet.hs (4 lines)
M			compiler/utils/UniqFM.hs (18 lines)

Diff	ID	Base	Description	Created	Lint	Unit
Base			Base
Diff 1	17170	b4e6483		Jul 3 2018, 7:12 AM	★	★
Diff 2	17173	b4e6483	- Remove redundant import	Jul 3 2018, 10:23 AM	★	★
Diff 3	17244	6595bee	- Remove redundant import(s)	Jul 9 2018, 12:24 PM	★	★
Diff 4	17292	6595bee	- Layout	Jul 12 2018, 6:21 PM	★	★
Diff 5	17726	02518f9	rGHC09c1d5afba655a2427a448a9933bebe7d13b696b	Aug 21 2018, 5:52 PM	★	★

Commit	Tree	Parents	Author	Summary	Date
6e39b8a00f0d	bb95cce7a3f6	740af7096ddd	klebinger.andreas@gmx.at	Layout	Jul 12 2018, 6:19 PM
740af7096ddd	3d51e37be275	6595bee749dd	klebinger.andreas@gmx.at	Replace most occurences of foldl with foldl'. (Show More…)	Jul 12 2018, 6:18 PM

Replace most occurences of foldl with foldl'.ClosedPublicActions

Details

Diff Detail

Revision ContentsChangeset List

Diff 17726

compiler/basicTypes/Avail.hs

compiler/basicTypes/NameCache.hs

compiler/basicTypes/NameSet.hs

compiler/basicTypes/OccName.hs

compiler/basicTypes/RdrName.hs

compiler/basicTypes/VarEnv.hs

compiler/cmm/CmmContFlowOpt.hs

compiler/cmm/CmmExpr.hs

compiler/cmm/CmmSink.hs

compiler/cmm/Hoopl/Dataflow.hs

compiler/codeGen/StgCmmMonad.hs

compiler/coreSyn/CoreArity.hs

compiler/coreSyn/CoreMap.hs

compiler/coreSyn/CoreOpt.hs

compiler/coreSyn/CoreSyn.hs

compiler/deSugar/DsExpr.hs

compiler/deSugar/DsForeign.hs

compiler/deSugar/DsMeta.hs

compiler/deSugar/DsUtils.hs

compiler/deSugar/Match.hs

compiler/hsSyn/HsTypes.hs

compiler/hsSyn/HsUtils.hs

compiler/iface/MkIface.hs

compiler/iface/TcIface.hs

compiler/iface/ToIface.hs

compiler/main/Ar.hs

compiler/main/DynFlags.hs

compiler/main/GhcMake.hs

compiler/main/HscTypes.hs

compiler/main/Packages.hs

compiler/nativeGen/AsmCodeGen.hs

compiler/nativeGen/RegAlloc/Graph/Coalesce.hs

compiler/nativeGen/RegAlloc/Graph/Main.hs

compiler/nativeGen/RegAlloc/Graph/Stats.hs

compiler/nativeGen/RegAlloc/Linear/Stats.hs

compiler/prelude/PrelInfo.hs

compiler/rename/RnNames.hs

compiler/simplCore/CallArity.hs

compiler/simplCore/FloatIn.hs

compiler/simplCore/OccurAnal.hs

compiler/simplCore/SetLevels.hs

compiler/simplCore/Simplify.hs

compiler/specialise/Rules.hs

compiler/specialise/Specialise.hs

compiler/stranal/DmdAnal.hs

compiler/typecheck/FunDeps.hs

compiler/typecheck/TcEvidence.hs

compiler/typecheck/TcExpr.hs

compiler/typecheck/TcGenDeriv.hs

compiler/typecheck/TcGenFunctor.hs

compiler/typecheck/TcInstDcls.hs

compiler/typecheck/TcPatSyn.hs

compiler/typecheck/TcRnTypes.hs

compiler/typecheck/TcSigs.hs

compiler/typecheck/TcSplice.hs

compiler/typecheck/TcType.hs

compiler/typecheck/TcValidity.hs

compiler/types/Coercion.hs

compiler/types/FamInstEnv.hs

compiler/types/InstEnv.hs

compiler/types/Type.hs

compiler/types/Unify.hs

compiler/utils/FiniteMap.hs

compiler/utils/GhcPrelude.hs

compiler/utils/ListSetOps.hs

compiler/utils/UnVarGraph.hs

compiler/utils/UniqDFM.hs

compiler/utils/UniqDSet.hs

compiler/utils/UniqFM.hs

Replace most occurences of foldl with foldl'.
ClosedPublic
Actions

Revision Contents
Changeset List