Huge increase of compile time and memory use from 8.0.2 to 8.2.2 or 8.4.2
I am the author of the cl3 library on Hackage. I have noticed a huge increase of compile time and memory use when testing 8.2.2 and 8.4.2. ghc-8.0.2 compiled in 4:17.33 using 3.5 GB. ghc-8.2.2 compiled in 26:40.15 using 32.8 GB. This is an increase of 6x in time and 9x in memory. This is not all bad, my nbody benchmark has improved about 35% between ghc-8.0.2 and ghc-8.4.2 so the increased compilation time and memory usage are producing much better runtime performance. I am interested if you could suggest some workarounds to help others compile on systems with less resources. I have 64GB memory in my system and would like to test out some -fno-* GHC Options. Could you point me in the right direction? The library is almost entirely pure functions. I am also interested in other options, like if there are ways to rewrite things to make it easier on the compiler or using NOINLINE on a trouble spot and how to find that trouble spot.
Trac metadata
| Trac field | Value |
|---|---|
| Version | 8.4.2 |
| Type | Bug |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | Compiler |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture |
Activity
changed milestone to %8.6.1
added Tbug Trac import labels
Attached file
ghc-8.2.2-v.txt(download).verbose output of ghc-8.2.2
Attached file
ghc-8.0.2-v.txt(download).verbose output of ghc-8.0.2
I have now been able to analyze the differences between ghc-8.0.2 to ghc-8.2.2.
Here is a table of the growth of the number of terms per iteration of the Simplifier for the module Algebra.Geometric.Cl3:
Simplifier Iteration 1 2 3 4 ghc-8.0.2 118,835 138,330 172,291 516,767 ghc-8.2.2 149,046 185,066 15,190,006 12,310,166 Apparently the largest difference occurs in Simplifier Iteration 3 between the Worker Wrapper and Float Out.
What is going on with Simplifier Iteration 3?
The other module, Algebra.Geometric.Cl3.JonesCalculus, actually has fewer terms in ghc-8.2.2 than ghc-8.0.2.
Attached file
ghc-8.4.2-v.txt(download).Attached verbose output of ghc-8.4.2. Noticed that while compiling the memory usage increased from 10GB to 32GB during CodeGen.
assigned to @tdammers
Steps to reproduce:
- Check out from git:
git clone https://github.com/waivio/cl3.git; cd cl3 - Install the
randompackage (e.g.cabal install random) cd cl3ghc -c Algebra/Geometric/Cl3.hs -fforce-recomp -O2
Without
-O2, things compile in under .1 seconds on my machine; adding-O2makes it take minutes.- Check out from git:
It seems that the
Eqinstance is at the core of the problem: replacing it with the following allows GHC to compile the module in a timely fashion, and compilation succeeds even with a heap limit of only 128M:instance Eq Cl3 where (==) = undefinedThis instance also compiles fast:
instance Eq Cl3 where (R a0) == (R b0) = True _ == _ = undefinedBut this one seems to blow up:
instance Eq Cl3 where (R a0) == (R b0) = a0 == b0 _ == _ = undefinedFurther investigation reveals that it's not necessarily the
Eqinstance itself that causes trouble; commenting out various parts of the module allows me to make it blow up or not blow up even with the full originalEqin place. It seems that multiple factors contribute to the blowup, and removing enough of them "fixes" the problem.Here's
-dshow-passeswith HEAD-dshow-passes output
simonpj@cam-05-unx:~/tmp/cl3$ ~/5builds/HEAD-5/inplace/bin/ghc-stage2 -c -dshow-passes src/Algebra/Geometric/Cl3.hs -O2 Glasgow Haskell Compiler, Version 8.7.20180710, stage 2 booted by GHC version 8.2.2 Using binary package database: /home/simonpj/5builds/HEAD-5/inplace/lib/package.conf.d/package.cache Using binary package database: /home/simonpj/.ghc/x86_64-linux-8.7.20180710/package.conf.d/package.cache package flags [] loading package database /home/simonpj/5builds/HEAD-5/inplace/lib/package.conf.d loading package database /home/simonpj/.ghc/x86_64-linux-8.7.20180710/package.conf.d wired-in package ghc-prim mapped to ghc-prim-0.5.3 wired-in package integer-gmp mapped to integer-gmp-1.0.2.0 wired-in package base mapped to base-4.12.0.0 wired-in package rts mapped to rts wired-in package template-haskell mapped to template-haskell-2.14.0.0 wired-in package ghc mapped to ghc-8.7 *** Checking old interface for Algebra.Geometric.Cl3 (use -ddump-hi-diffs for more details): *** Parser [Algebra.Geometric.Cl3]: !!! Parser [Algebra.Geometric.Cl3]: finished in 281.59 milliseconds, allocated 124.657 megabytes *** Renamer/typechecker [Algebra.Geometric.Cl3]: !!! Renamer/typechecker [Algebra.Geometric.Cl3]: finished in 1729.18 milliseconds, allocated 582.499 megabytes *** Desugar [Algebra.Geometric.Cl3]: Result size of Desugar (before optimization) = {terms: 46,524, types: 55,087, coercions: 2,210, joins: 0/9,539} Result size of Desugar (after optimization) = {terms: 26,825, types: 34,697, coercions: 4,390, joins: 1/660} !!! Desugar [Algebra.Geometric.Cl3]: finished in 463.17 milliseconds, allocated 198.217 megabytes *** Simplifier [Algebra.Geometric.Cl3]: Result size of Simplifier iteration=1 = {terms: 29,453, types: 35,248, coercions: 7,271, joins: 1/982} Result size of Simplifier iteration=2 = {terms: 26,430, types: 32,412, coercions: 5,036, joins: 1/207} Result size of Simplifier iteration=3 = {terms: 26,370, types: 32,315, coercions: 4,924, joins: 1/198} Result size of Simplifier = {terms: 26,370, types: 32,315, coercions: 4,924, joins: 1/198} !!! Simplifier [Algebra.Geometric.Cl3]: finished in 1478.89 milliseconds, allocated 532.541 megabytes *** Specialise [Algebra.Geometric.Cl3]: Result size of Specialise = {terms: 27,077, types: 33,084, coercions: 4,924, joins: 1/226} !!! Specialise [Algebra.Geometric.Cl3]: finished in 34.41 milliseconds, allocated 20.874 megabytes *** Float out(FOS {Lam = Just 0, Consts = True, OverSatApps = False}) [Algebra.Geometric.Cl3]: Result size of Float out(FOS {Lam = Just 0, Consts = True, OverSatApps = False}) = {terms: 29,888, types: 35,057, coercions: 4,924, joins: 1/217} !!! Float out(FOS {Lam = Just 0, Consts = True, OverSatApps = False}) [Algebra.Geometric.Cl3]: finished in 303.86 milliseconds, allocated 133.719 megabytes *** Simplifier [Algebra.Geometric.Cl3]: Result size of Simplifier iteration=1 = {terms: 109,632, types: 50,922, coercions: 4,826, joins: 183/7,875} Result size of Simplifier iteration=2 = {terms: 93,026, types: 52,819, coercions: 4,899, joins: 185/1,646} Result size of Simplifier iteration=3 = {terms: 135,959, types: 55,173, coercions: 4,892, joins: 99/2,772} Result size of Simplifier iteration=4 = {terms: 131,354, types: 52,485, coercions: 4,892, joins: 53/529} Result size of Simplifier = {terms: 131,354, types: 52,485, coercions: 4,892, joins: 53/529} !!! Simplifier [Algebra.Geometric.Cl3]: finished in 4415.46 milliseconds, allocated 1573.215 megabytes *** Simplifier [Algebra.Geometric.Cl3]: Result size of Simplifier iteration=1 = {terms: 130,205, types: 52,159, coercions: 4,892, joins: 37/519} Result size of Simplifier iteration=2 = {terms: 128,591, types: 51,440, coercions: 4,892, joins: 37/513} Result size of Simplifier = {terms: 128,591, types: 51,440, coercions: 4,892, joins: 37/513} !!! Simplifier [Algebra.Geometric.Cl3]: finished in 3285.00 milliseconds, allocated 1248.401 megabytes *** Simplifier [Algebra.Geometric.Cl3]: Result size of Simplifier iteration=1 = {terms: 129,119, types: 51,615, coercions: 4,892, joins: 37/538} Result size of Simplifier iteration=2 = {terms: 129,068, types: 51,555, coercions: 4,892, joins: 37/533} Result size of Simplifier = {terms: 129,068, types: 51,555, coercions: 4,892, joins: 37/533} !!! Simplifier [Algebra.Geometric.Cl3]: finished in 3415.70 milliseconds, allocated 1218.423 megabytes *** Float inwards [Algebra.Geometric.Cl3]: Result size of Float inwards = {terms: 129,068, types: 51,555, coercions: 4,892, joins: 37/533} !!! Float inwards [Algebra.Geometric.Cl3]: finished in 218.06 milliseconds, allocated 143.267 megabytes *** Called arity analysis [Algebra.Geometric.Cl3]: Result size of Called arity analysis = {terms: 129,068, types: 51,555, coercions: 4,892, joins: 37/533} !!! Called arity analysis [Algebra.Geometric.Cl3]: finished in 160.66 milliseconds, allocated 86.793 megabytes *** Simplifier [Algebra.Geometric.Cl3]: Result size of Simplifier = {terms: 129,068, types: 51,555, coercions: 4,892, joins: 37/533} !!! Simplifier [Algebra.Geometric.Cl3]: finished in 943.43 milliseconds, allocated 405.961 megabytes *** Demand analysis [Algebra.Geometric.Cl3]: Result size of Demand analysis = {terms: 129,068, types: 51,555, coercions: 4,892, joins: 37/533} !!! Demand analysis [Algebra.Geometric.Cl3]: finished in 1513.03 milliseconds, allocated 552.224 megabytes *** Worker Wrapper binds [Algebra.Geometric.Cl3]: Result size of Worker Wrapper binds = {terms: 130,487, types: 54,247, coercions: 4,892, joins: 38/701} !!! Worker Wrapper binds [Algebra.Geometric.Cl3]: finished in 36.37 milliseconds, allocated 10.774 megabytes *** Simplifier [Algebra.Geometric.Cl3]: Result size of Simplifier iteration=1 = {terms: 143,685, types: 58,766, coercions: 4,815, joins: 96/1,750} Result size of Simplifier iteration=2 = {terms: 175,579, types: 63,298, coercions: 4,815, joins: 173/1,293} C-c C-c*** Deleting temp files: *** Deleting temp dirs:I had to stop it with ctrl-C
Edited by Ömer Sinan AğacanAttached file
Cl3.hs(download).Based on ticket:15304#comment:156492, I attached a bit smaller version without dependency on random.
On my machine:
-
ghc-8.0.2 -O -c Cl3.hs -fforce-recomptakes 2 secs -
ghc-8.2.1 -O -c Cl3.hs -fforce-recomptakes 57 secs -
ghc-8.4.3 -O -c Cl3.hs -fforce-recomptakes 95 secs
If I don't add
-O, every version takes 2 secs.-
This is very useful. The reduced
Cl3.hswith allFloatingmethods exceptexpandlogremoved gives a much cleaner result. Looking at-ddump-rule-firingsoutput, here's counters of how often each rule fired on 8.0.2 and 8.4.3:rule | 8.0 8.4 --------------------------+------------ *## | 127 44 +## | 26 372 ^2/Integer | 55 55 Class op - | 419 417 Class op / | 15 8 Class op * | 1698 1693 Class op ** | 3 2 Class op + | 737 734 Class op abs | 5 5 Class op atan2 | 1 1 Class op cos | 7 5 Class op cosh | 3 2 Class op exp | 14 10 Class op fromInteger | 13 8 Class op fromRational | 4 2 Class op log | 20 14 Class op log1p | 6 4 Class op negate | 109 106 Class op $p1Floating | 25 16 Class op $p1Fractional | 20 12 Class op pi | 1 1 Class op recip | 4 3 Class op sin | 7 5 Class op sinh | 3 2 Class op sqrt | 14 14 doubleFromInteger | 9 7 SC:$clog0 | 6 0 SC:$w$catan20 | 1 0So it looks like a change to the way
SpecConstrs are handled is preventing either specializations, orRULESthat follow from them.OK, next experiment: compile with
-fno-specialise, and diff-ddump-simpl-statsoutput (minus the PreInline and PostInline parts). Which gives us:Diff
--- stats-8.0.2/Cl3.dump-simpl-stats 2018-07-12 16:25:23.219578828 +0200 +++ stats-8.4.3/Cl3.dump-simpl-stats 2018-07-12 16:42:41.644219237 +0200 @@ -1,74 +1,78 @@ ==================== FloatOut stats: ==================== -2018-07-12 13:46:13.85196043 UTC +2018-07-12 14:25:41.716397419 UTC -140 Lets floated to top level; 0 Lets floated elsewhere; from 35 Lambda groups +131 Lets floated to top level; 0 Lets floated elsewhere; from 22 Lambda groups ==================== FloatOut stats: ==================== -2018-07-12 13:46:17.767931325 UTC +2018-07-12 14:26:18.231633767 UTC -24 Lets floated to top level; 0 Lets floated elsewhere; from 42 Lambda groups +1 Lets floated to top level; 0 Lets floated elsewhere; from 25 Lambda groups ==================== Grand total simplifier statistics ==================== -2018-07-12 13:46:19.653844196 UTC +2018-07-12 14:26:39.421166819 UTC -Total ticks: 44196 +Total ticks: 91304 -6609 UnfoldingDone - 1681 GHC.Float.$fNumDouble_$c* +5077 UnfoldingDone 1681 GHC.Float.timesDouble - 729 GHC.Float.$fNumDouble_$c+ 729 GHC.Float.plusDouble - 415 GHC.Float.$fNumDouble_$c- 415 GHC.Float.minusDouble + 177 $j_s6gs + 177 $j_s6kx 137 Algebra.Geometric.Cl3.$WAPS + 132 $j_s6gn + 132 $j_s6gq + 132 $j_s6ks + 132 $j_s6kv + 121 $j_s6cS + 121 $j_s6gX + 110 $j_s6PQ + 110 $j_s71Q 102 GHC.Base.$ - 102 GHC.Float.$fNumDouble_$cnegate 102 GHC.Float.negateDouble - 62 $j_s5Li - 62 $j_s5LN + 44 $j_s6gm + 44 $j_s6gr + 44 $j_s6kr + 44 $j_s6kw + 25 Algebra.Geometric.Cl3.$WR + 22 $j_s6gi + 22 $j_s6go + 22 $j_s6kn + 22 $j_s6kt 19 Algebra.Geometric.Cl3.$WH 19 Algebra.Geometric.Cl3.$WODD - 17 Algebra.Geometric.Cl3.$WR 17 Algebra.Geometric.Cl3.$WBPV - 15 $c/_a1Af - 14 GHC.Float.$fFloatingDouble_$csqrt + 17 $j_s6cc 14 GHC.Float.sqrtDouble 14 Algebra.Geometric.Cl3.$WC - 12 $j_s5Le - 12 $j_s5Lg - 12 $j_s5LJ - 12 $j_s5LL 11 Algebra.Geometric.Cl3.$WPV 11 Algebra.Geometric.Cl3.$WTPV - 10 $j_s5Lf - 10 $j_s5LK - 9 $cfromInteger_a3eU - 8 $c*_a1He - 7 $c+_a1Az - 6 $clog1p_a1zz - 6 $s$clog_s614 - 5 $cnegate_a36c + 8 $c*_a2h6 + 8 GHC.Float.$fNumDouble_$cfromInteger + 7 $cfromInteger_a3OM + 7 $j_s6gp + 7 $j_s6ku + 6 $c/_a2ad + 6 $c+_a2at 5 Algebra.Geometric.Cl3.$WV3 5 Algebra.Geometric.Cl3.$WBV - 5 lvl_s5VO - 5 lvl_s5VP - 4 $c-_a1H7 - 4 GHC.Float.$fNumDouble_$cabs - 4 $j_s5Lb - 4 $j_s5Lc - 4 $j_s5Ld - 4 $j_s5Lh - 4 $j_s5LG - 4 $j_s5LH - 4 $j_s5LI - 4 $j_s5LM - 3 $c**_a1yF + 4 $clog1p_a29F + 4 $cnegate_a3G4 + 4 GHC.Float.fabsDouble + 4 $j_s6c8 + 4 $j_s6ca + 4 $j_s6gj + 4 $j_s6gk + 4 $j_s6ko + 4 $j_s6kp + 3 Algebra.Geometric.Cl3.projEigs 3 Algebra.Geometric.Cl3.$WI - 3 $j_s5J8 - 3 $j_s5Jo + 2 $c**_a28T + 2 $crecip_a2ak + 2 $c-_a2h1 2 GHC.Base.$! 2 GHC.Float.$dm** 2 GHC.Float.$dmexpm1 @@ -82,318 +86,359 @@ 2 GHC.Real.$dm/ 2 GHC.Real.$dmrecip 2 GHC.Num.$dm- + 2 Algebra.Geometric.Cl3.spectraldcmp 2 Algebra.Geometric.Cl3.reduce - 2 $dNum_s5Id - 2 $dNum_s5It - 2 lvl_s5VK - 1 $cabs_a36g - 1 GHC.Float.$fRealFloatDouble_$catan2 - 1 GHC.Float.$fNumDouble_$cfromInteger - 1 GHC.Float.$fFractionalDouble_$crecip - 1 GHC.Float.$fFloatingDouble_$ccos - 1 GHC.Float.$fFloatingDouble_$csin - 1 GHC.Float.$fFloatingDouble_$clog - 1 GHC.Float.$fFloatingDouble_$cexp - 1 GHC.Float.sinDouble - 1 GHC.Float.logDouble - 1 GHC.Float.expDouble + 2 $j_s6gl + 2 $j_s6kq + 1 $cabs_a3G8 1 GHC.Float.cosDouble - 1 Algebra.Geometric.Cl3.projEigs - 1 $s$dmlog1pexp_s5Ge - 1 lvl_s5I8 - 1 lvl_s5I9 - 1 $dFractional_s5Ib - 1 lvl_s5Ik - 1 lvl_s5Il - 1 lvl_s5Im - 1 lvl_s5In - 1 lvl_s5Io - 1 lvl_s5Ip - 1 $dFractional_s5Ir - 1 lvl_s5Iw - 1 lvl_s5W0 -3337 RuleFired - 1695 Class op * - 737 Class op + - 419 Class op - - 127 *## - 109 Class op negate + 1 GHC.Float.expDouble + 1 GHC.Float.logDouble + 1 GHC.Float.sinDouble + 1 GHC.Float.$fFractionalDouble_$crecip + 1 GHC.Float.$fRealFloatDouble_$catan2 + 1 lvl_s6br + 1 lvl_s6bs + 1 lvl_s6bu + 1 lvl_s6bv + 1 lvl_s6bx + 1 $j_s6c9 + 1 lvl_s7OD + 1 lvl_s7OE +3532 RuleFired + 1691 Class op * + 734 Class op + + 417 Class op - + 372 +## + 106 Class op negate 55 ^2/Integer - 26 +## - 25 Class op $p1Floating - 20 Class op $p1Fractional - 15 Class op / - 14 Class op exp - 14 Class op log + 44 *## + 16 Class op $p1Floating 14 Class op sqrt - 13 Class op fromInteger - 9 doubleFromInteger - 6 Class op log1p - 6 SC:$clog0 + 12 Class op $p1Fractional + 10 Class op exp + 10 Class op log + 8 Class op / + 8 Class op fromInteger + 7 doubleFromInteger 5 Class op abs - 4 Class op cos - 4 Class op fromRational - 4 Class op recip - 4 Class op sin - 3 Class op ** - 3 Class op cosh - 3 Class op sinh + 4 Class op log1p + 3 Class op cos + 3 Class op recip + 3 Class op sin + 2 Class op ** + 2 Class op cosh + 2 Class op fromRational + 2 Class op sinh 1 Class op atan2 1 Class op pi - 1 SC:$w$catan20 -25 LetFloatFromLet 25 -1 EtaReduction 1 x_a5bv -9652 BetaReduction - 1681 ds_a5IW - 1681 ds1_a5IX - 729 ds_a5IM - 729 ds1_a5IN - 415 ds_a5Jb - 415 ds1_a5Jc - 137 dt_a1fe - 137 dt_a1ff - 137 dt_a1fg - 137 dt_a1fh - 137 dt_a1fi - 137 dt_a1fj - 137 dt_a1fk - 137 dt_a1fl - 124 dt_d5iD - 124 dt_d5iE - 124 dt_d5iF - 124 dt_d5iG - 124 dt_d5iH - 124 dt_d5iI - 124 dt_d5iJ - 124 dt_d5iK - 102 a_12 - 102 b_13 - 102 r_1j - 102 tpl_B1 - 102 tpl_B2 - 102 ds_a5JB - 55 a_a5nS - 55 $dNum_a5nT - 55 $dIntegral_a5nU - 55 x_a5nV - 24 dt_d5iP - 24 dt_d5iQ - 24 dt_d5iR - 24 dt_d5iS - 24 dt_d5j1 - 24 dt_d5j2 - 24 dt_d5j3 - 24 dt_d5j4 - 20 dt_d5iT - 20 dt_d5iU - 20 dt_d5iV - 20 dt_d5iW - 20 dt_d5iX - 20 dt_d5iY - 19 dt_a1eq - 19 dt_a1er - 19 dt_a1es - 19 dt_a1et - 19 dt_a1eU - 19 dt_a1eV - 19 dt_a1eW - 19 dt_a1eX - 17 dt_a1dS - 17 dt_a1eG - 17 dt_a1eH - 17 dt_a1eI - 17 dt_a1eJ - 17 dt_a1eK - 17 dt_a1eL - 16 eta_a53E - 16 eta1_a53F - 14 dt_a1eA - 14 dt_a1eB - 14 ds_a5IH - 12 sc_s60u - 12 sc_s60v - 11 dt_a1eg - 11 dt_a1eh - 11 dt_a1ei - 11 dt_a1ej - 11 dt_a1f4 - 11 dt_a1f5 - 11 dt_a1f6 - 11 dt_a1f7 - 9 int_a1bM - 8 ds_d4ON - 8 ds_d4OO - 8 dt_d5iL - 8 dt_d5iM - 8 dt_d5iN - 8 dt_d5iO - 8 dt_d5j5 - 8 dt_d5j6 - 8 dt_d5j7 - 8 dt_d5j8 - 8 dt_d5ja - 8 dt_d5jb - 8 dt_d5jc - 8 dt_d5jd - 8 dt_d5je - 8 dt_d5jf - 7 eta_a53o - 7 ds_d4CK - 7 ds_d4CL - 6 y_X5Nf - 5 x_a1bN - 5 dt_a1dW - 5 dt_a1dX - 5 dt_a1dY - 5 dt_a1e4 - 5 dt_a1e5 - 5 dt_a1e6 - 5 x_a5bv - 5 y_a5bw - 4 eta_a53a - 4 eta1_a53b - 4 x_a5mY - 3 dt_a1ec - 2 cliffor_aIx - 2 r_aIz - 2 a_a533 - 2 $dFloating_a534 - 2 a_a538 - 2 $dFloating_a539 - 2 a_a53c - 2 $dFloating_a53d - 2 a_a53g - 2 $dFloating_a53h - 2 a_a53j - 2 $dFloating_a53k - 2 a_a53m - 2 $dFloating_a53n - 2 a_a53r - 2 $dFloating_a53s - 2 a_a53w - 2 $dFloating_a53x - 2 a_a53z - 2 $dFloating_a53A - 2 a_a53C - 2 $dFractional_a53D - 2 a_a53G - 2 $dFractional_a53H - 2 a_a5bt - 2 $dNum_a5bu - 2 a_a5mH - 2 b_a5mI - 2 f_a5mJ - 2 x_a5mK - 2 dt_d5et - 2 dt_d5eu - 1 eta_a535 - 1 eta_a53e - 1 eta1_a53f - 1 eta_a53i - 1 eta_a53l - 1 eta_a53t - 1 x_a53y - 1 eta_a53B - 1 eta_a53I - 1 i_a5mT - 1 x_a5oJ - 1 w_a5p8 - 1 w1_a5p9 - 1 ds_a5K6 - 1 ds_a5Kc - 1 ds_a5Kh - 1 ds_a5Kp - 1 sc_a5PU - 1 sc1_a5PV - 1 ds_d4AC - 1 ds_d4BO - 1 ds_d4CI - 1 ds_d50R - 1 ds_d52M - 1 w_s5RT -9 CaseOfCase - 2 wild_X9 - 2 wild_XV - 2 dt_X1dU - 2 wild1_a5J2 - 1 ww_s5RV -7664 KnownBranch - 1685 wild1_a5J2 - 1681 wild_a5IY - 729 wild_a5IO - 729 wild1_a5IS - 415 wild_a5Jd - 415 wild1_a5Jh - 248 wild_X9 - 137 dt_X1fn - 137 dt_X1fq - 137 dt_X1ft - 137 dt_X1fw - 137 dt_X1fz - 137 dt_X1fC - 137 dt_X1fF - 137 dt_X1fI - 102 wild_a5JC - 36 dt_X1eZ - 36 dt_X1f2 - 25 wild_XV - 21 dt_X1dU - 19 dt_X1ev - 19 dt_X1ey - 19 dt_X1eB - 19 dt_X1eE - 19 dt_X1f5 - 19 dt_X1f8 - 19 ww_s5RV - 17 dt_X1eN - 17 dt_X1eQ - 17 dt_X1eT - 17 dt_X1eW - 14 dt_X1eD - 14 dt_X1eG - 14 wild_a5II - 12 wild_Xf - 11 dt_X1el - 11 dt_X1eo - 11 dt_X1er - 11 dt_X1eu - 11 dt_X1f9 - 11 dt_X1fc - 11 dt_X1ff - 11 dt_X1fi - 9 wild_a5mU - 8 wild_Xg - 8 dt_X1ee - 6 wild_Xd - 5 wild_Xb - 5 wild_XW - 5 dt_X1e0 - 5 dt_X1e3 - 5 dt_X1e6 - 5 dt_X1e8 - 5 dt_X1eb - 4 wild_Xa +687 LetFloatFromLet 687 +2 EtaReduction + 1 eta_B2 + 1 x_a5TK +14750 BetaReduction + 1681 ds_a65p + 1681 ds1_a65q + 729 ds_a64o + 729 ds1_a64p + 415 ds_a65z + 415 ds1_a65A + 354 dt_d5SW + 354 dt_d5SX + 354 dt_d5SY + 354 dt_d5SZ + 354 dt_d5T0 + 354 dt_d5T1 + 354 dt_d5T2 + 354 dt_d5T3 + 264 dt_d5Po + 264 dt_d5Pp + 264 dt_d5Pq + 264 dt_d5Pr + 264 dt_d5Rw + 264 dt_d5Rx + 264 dt_d5Ry + 264 dt_d5Rz + 242 vx_a63F + 226 ds_d5kP + 137 dt_a1Gh + 137 dt_a1Gi + 137 dt_a1Gj + 137 dt_a1Gk + 137 dt_a1Gl + 137 dt_a1Gm + 137 dt_a1Gn + 137 dt_a1Go + 102 a_11 + 102 b_12 + 102 r_1i + 102 v_B1 + 102 v_B2 + 102 ds_a65W + 88 dt_d5OG + 88 dt_d5OH + 88 dt_d5OI + 88 dt_d5OJ + 88 dt_d5Se + 88 dt_d5Sf + 88 dt_d5Sg + 88 dt_d5Sh + 55 a_a64W + 55 $dNum_a64X + 55 $dIntegral_a64Y + 55 x_a64Z + 44 dt_d5LY + 44 dt_d5Q6 + 44 dt_d5Q7 + 25 dt_a1EV + 19 dt_a1Ft + 19 dt_a1Fu + 19 dt_a1Fv + 19 dt_a1Fw + 19 dt_a1FX + 19 dt_a1FY + 19 dt_a1FZ + 19 dt_a1G0 + 17 dt_a1FJ + 17 dt_a1FK + 17 dt_a1FL + 17 dt_a1FM + 17 dt_a1FN + 17 dt_a1FO + 17 dt_d5Uj + 17 dt_d5Uk + 17 dt_d5Ul + 17 dt_d5Um + 17 dt_d5Un + 17 dt_d5Uo + 17 dt_d5Up + 17 dt_d5Uq + 14 dt_a1FD + 14 dt_a1FE + 14 ds_a64j + 14 dt_d5QM + 14 dt_d5QN + 14 dt_d5QO + 14 dt_d5QP + 14 dt_d5QQ + 14 dt_d5QR + 11 dt_a1Fj + 11 dt_a1Fk + 11 dt_a1Fl + 11 dt_a1Fm + 11 dt_a1G7 + 11 dt_a1G8 + 11 dt_a1G9 + 11 dt_a1Ga + 8 i_a63N + 8 ds_d5wR + 8 ds_d5wS + 8 dt_d5MD + 8 dt_d5ME + 8 dt_d5MF + 8 dt_d5Nk + 8 dt_d5Nl + 8 dt_d5Nm + 7 int_a1BT + 6 ds_d5kO + 6 w_s6Mj + 6 w_s6Mk + 5 dt_a1EZ + 5 dt_a1F0 + 5 dt_a1F1 + 5 dt_a1F7 + 5 dt_a1F8 + 5 dt_a1F9 + 5 x_a5LB + 4 x_a1BU + 4 ds_a63S + 4 dt_d5O1 + 4 dt_d5TZ + 4 dt_d5U0 + 4 dt_d5U1 + 4 dt_d5U2 + 4 dt_d5Ub + 4 dt_d5Uc + 4 dt_d5Ud + 4 dt_d5Ue + 3 dt_a1Ff + 3 x_a5Li + 3 y_a5Lj + 3 x_a5LX + 3 w_s6Mz + 2 function_a1BV + 2 cliffor_a1BW + 2 r_a1C1 + 2 a_a5L7 + 2 $dFloating_a5L8 + 2 a_a5Le + 2 $dFloating_a5Lf + 2 a_a5Lk + 2 $dFloating_a5Ll + 2 a_a5Lp + 2 $dFloating_a5Lq + 2 a_a5Lt + 2 $dFloating_a5Lu + 2 a_a5Lx + 2 $dFloating_a5Ly + 2 a_a5LC + 2 $dFloating_a5LD + 2 a_a5LH + 2 $dFloating_a5LI + 2 a_a5LK + 2 $dFloating_a5LL + 2 a_a5LP + 2 $dFractional_a5LQ + 2 a_a5LU + 2 $dFractional_a5LV + 2 a_a5TI + 2 $dNum_a5TJ + 2 a_a63B + 2 b_a63C + 2 f_a63D + 2 x_a63E + 1 x_a5La + 1 x_a5Ln + 1 y_a5Lo + 1 x_a5Ls + 1 x_a5Lw + 1 x_a5LG + 1 x_a5LJ + 1 x_a5LO + 1 x_a5LS + 1 y_a5LT + 1 x_a5TK + 1 y_a5TL + 1 x_a66T + 1 ds_a67a + 1 ds_a67g + 1 ds_a67l + 1 ds_a67s + 1 w_a67O + 1 w1_a67P + 1 dt_d5TO + 1 dt_d5TP + 1 dt_d5TQ + 1 dt_d5TR + 1 dt_d5TS + 1 dt_d5TT + 1 dt_d5TV + 1 dt_d5TW + 1 dt_d5TX + 1 dt_d5TY + 1 dt_d5U5 + 1 dt_d5U6 + 1 dt_d5U7 + 1 dt_d5U8 + 1 dt_d5U9 + 1 dt_d5Ua + 1 dt_d5Uf + 1 dt_d5Ug + 1 dt_d5Uh + 1 dt_d5Ui + 1 dt_d5XU + 1 dt_d5XV + 1 w_s6M9 +7 CaseOfCase + 2 wild_X16 + 2 vx_a63F + 1 wild_X9 + 1 wild_X15 + 1 ww_s6Mb +13525 KnownBranch + 1681 wild_a65r + 1681 wild1_a65v + 1211 wild_Xo + 888 wild_Xf + 884 wild_Xg + 729 wild_a64q + 729 wild1_a64u + 565 wild_X9 + 444 wild_Xd + 415 wild_a65B + 415 wild1_a65F + 266 wild_Xa + 242 wild_X1i + 242 vx_a63F + 223 wild_Xb + 223 wild_X16 + 222 wild_Xj + 222 wild_Xn + 221 wild_Xc + 178 wild_Xe + 155 wild_Xk + 137 dt_X1Gq + 137 dt_X1Gt + 137 dt_X1Gw + 137 dt_X1Gz + 137 dt_X1GC + 137 dt_X1GF + 137 dt_X1GI + 137 dt_X1GL + 102 wild_a65X + 36 dt_X1G2 + 36 dt_X1G5 + 25 dt_X1EX + 19 dt_X1Fy + 19 dt_X1FB + 19 dt_X1FE + 19 dt_X1FH + 19 dt_X1G8 + 19 dt_X1Gb + 17 dt_X1FQ + 17 dt_X1FT + 17 dt_X1FW + 17 dt_X1FZ + 14 dt_X1FG + 14 dt_X1FJ + 14 wild_a64k + 12 wild_X15 + 11 dt_X1Fo + 11 dt_X1Fr + 11 dt_X1Fu + 11 dt_X1Fx + 11 dt_X1Gc + 11 dt_X1Gf + 11 dt_X1Gi + 11 dt_X1Gl + 11 ww_s6Mb + 8 dt_X1Fh + 7 wild_a63O + 5 dt_X1F3 + 5 dt_X1F6 + 5 dt_X1F9 + 5 dt_X1Fb + 5 dt_X1Fe + 4 wild_X2i + 4 wild_a63T + 1 wild_X2a + 1 wild_a66U + 1 wild_a67b + 1 wild_a67h + 1 wild_a67m + 1 wild_a67t + 1 ww_a67Q + 1 ds_d5JX + 1 ww_s6MB + 1 ww_s6MH + 1 ww_s6Ne +18 SimplifierDone 18 +76 AltMerge + 8 wild_X4B + 8 wild_X4C + 8 wild_X4E + 8 wild_X4F + 8 wild_X4G + 6 wild_X4D 4 wild_Xe - 4 wild_a5mZ - 3 wild_Xj - 3 wild_Xn + 4 wild_Xg + 4 wild_X4H + 3 wild_X4x + 3 wild_X4y + 3 wild_X4I + 2 wild_Xa 2 wild_Xc - 2 wild_Xk - 2 wild_Xo - 1 wild_X1C - 1 wild_X1M - 1 wild_X1O - 1 wild_a5oK - 1 ww_a5pa - 1 wild_a5K7 - 1 wild_a5Kd - 1 wild_a5Ki - 1 wild_a5Kq - 1 ds_d4AR - 1 ds_d4AS - 1 ds_d51T - 1 ww_s5Sj -2 CaseMerge 2 vx_a5mL -1 CaseIdentity 1 wild_X9 -21 SimplifierDone 21 + 2 wild_X4z + 2 wild_X4A + 1 wild_X4J(Left / before / red: GHC 8.0.2; right / after / green: GHC 8.4.3).
Edited by Ömer Sinan AğacanI have found an undocumented flag: "-fno-worker-wrapper". When enabled the original code compiles in 43.20 seconds (37x improvement in time), and uses 660MB max (48x improvement in space) with GHC 8.4.2. All of the tests pass for the library and the benchmark still performs at the improved speed. It seems like the Worker/Wrapper Transformation is causing issues with this code. Why is that? Perhaps Worker/Wrapper shouldn't be run in certain circumstances. What do you think?
Sounds like a promising lead, if not the key to figuring this out. Worker/wrapper is generally a good thing to do; in theory, all it should do is turn arguments to recursive function calls closures, thus reducing the argument-passing overhead. But I can imagine that this would also get in the way of inlinings and
RULES.So what we're looking for is code that follows the pattern that makes it a candidate for worker/wrapper optimization (parameters passed through recursive calls unchanged), such that the worker/wrapper optimization breaks up expressions that might otherwise trigger useful inlinings or rewrites.
mentioned in issue #15455 (closed)
added compiler perf label
added Phigh label
Since this program is tiny (my slightly simplified version has 1339 lines of code) and reports pretty bad numbers I wanted to give this a try, and I think I may have accidentally found a bug in GHC HEAD (a regression from 8.8.2). However I couldn't reproduce the original issue reported here (numbers below).
For GHC HEAD I used a build without build.mk.
My code (with the script I used) is here.
Build times
(There are two modules in this program, first number in each cell is for the first, second number is for the second)
O0 O1 O2 7.10.3 0:02.26 + 0:00.14 0:06.87 + 1:04.06 0:07.91 + 1:07.27 8.0.2 0:02.39 + 0:00.20 0:07.40 + 1:11.35 0:08.04 + 1:15.14 8.2.2 0:02.14 + 0:00.14 0:08.06 + 0:20.93 0:08.21 + 0:21.92 8.4.3 0:02.09 + 0:00.16 0.05.90 + 0:18.06 0:05.82 + 0:19.04 8.6.4 0:02.16 + 0:00.18 0:05.50 + 0:08.76 0:06.96 + 0:09.43 8.8.2 0:02.21 + 0:00.16 0:05.40 + 0:08.58 0:06.06 + 0:09.79 HEAD 0:02.24 + 0:00.15 0:05.60 + 28:29.66 0:05.99 + ??? While build times vary between versions until GHC HEAD it's still possible to build this program even with optimizations. Starting with GHC HEAD it becomes impossible to build this with GHC HEAD with -O1 and -O2.
Max residency
Note that I couldn't use the flags for more accurate max. residency generation like
-i0 -A256k -hbecause the process takes forever with those flags.O0 O1 O2 7.10.3 61,450,496 + 16,328,992 175,227,848 + 1,043,963,296 178,227,848 + 1,184,121,656 8.0.2 75,040,232 + 23,291,632 187,169,120 + 1,178,903,625 207,405,512 + 1,274,237,376 8.2.2 66,634,928 + 12,522,160 155,637,520 + 388,455,400 153,829,288 + 369,651,232 8.4.3 60,512,912 + 21,139,800 115,509,920 + 357,125,808 104,963,224 + 324,197,224 8.6.4 78,645,816 + 20,654,504 133,772,968 + 164,819,488 121,994,368 + 169,405,352 8.8.2 62,489,576 + 14,364,224 136,131,096 + 144,275,584 153,169,016 + 170,175,712 HEAD 55,104,744 + 13,785,664 148,848,096 + more than 16G ??? So unlike the original report, I get worse residency in 7.10 and 8.0 than in newer versions.
And yes, we need to fix GHC HEAD before the next release.
It'd be good if someone else would try to reproduce the numbers. I made two GHC HEAD builds because I couldn't believe these numbers are real, but it's still possible that I've made a mistake in my benchmarking.
What is happening is this.
When deciding to inline a function we compute:
- size: the size of its body
- discount; a "discount" based on its calling context
Then we compute (size - (discount * unfolding-keeness-factor)) and see if that is less than unfolding-use-threshold. Its default value is 1.5.
By itself that makes sense. The unfolding-keeness-factor multiplies up the discount, and makes GHC more eager to inline.
But the discount is computed like this. Suppose the function has firsr argument x, and the call looks like
f (K7 a b), where K7 is a data constructor from type with many constructors. Then, suppose inside f's body we havecase x of K1 -> e1 K2 -> e2 .. K100 -> e100Knowing that the argument is
K7would dramatically shrink the code! Suppose the size of e1 is s1, of e2 is s2, etc. Then we give a discount for x equal todiscount(x) = (s1 + s2 + ... + s100) - smaxwhere smax is the size of the largest of the ei.
The idea is that, if we know the contructor x is buidl with, the expression will shrink to smax at worst, maybe less. So that's a good discount to apply.
ALAS, the reasoning is utterly bogus if you first multiply the dicount by 1.5! In this particular example I saw
guidance IF_ARGS [4354 4454] 5122 8430 discounted size = -1454That is, function body has size 5122, with a discount of 4354 if you know the first argument. That's OK: many case alternatives will be discarded within that 5122-sized body, if we know the first arg. That still leaves a large residual body of size 750 or so.
But if we multiply the discount by 1.5, it becomes way bigger than 5122, and we inline this vast function. This happens many times. Disaster.
What to do about it
It is clearly wrong to multiply the argument discounts; they are absolute sizes. Better to say
(size - discount) <= threshold * keenessBut that's no different to setting a different threshold.
My conclusion: let's kill off
-funfolding-keeness-factorentirely and (to maintain something like the status quo) bump up the default unfolding-use threshold a bit.Of course that doesn't maintain exactly the status quo; the calculation is different. So we need to do some experimentation.
@bgamari @omer, over to you.
added inlining label
assigned to @bgamari
mentioned in commit 599d1a51
I'll admit, I am a bit concerned about how this will affect simplification of existing, hand-optimised code. However, let's see what happens on head.hackage.
The point is that currently we are manifestly doing something ridiculously stupid. We must stop doing that. It is difficult to do so in a way that guarantees not to affect anything sensible. Let's just try and see -- and advertise the change so that users can re-check their inner loops.
mentioned in merge request !2608 (closed)
mentioned in commit a1bf9faf
mentioned in commit c845aeea
mentioned in commit 3d4c598e
mentioned in commit 3abe30e9
mentioned in commit ac5e96c3
mentioned in commit 927bb39b
mentioned in commit 9adec18f
mentioned in commit 7505cde8
mentioned in commit b33cac73
mentioned in issue #17951 (closed)
mentioned in issue #18004 (closed)
