CPR optimisation for sum types if only one constructor is used
Inspired by #3138, it might be useful for StrAnal to detect functions such as the following where only one of the data constructors for a sum type are CPRed:
loop x = case x < 10 of True -> Left x; False -> loop (x*2)We can usefully transform to:
$wloop x = case (case x < 10 of True -> Left x; False -> loop (x*2)) of Left y -> (# y #)
loop x = case loop x of (# y #) -> Left yAttached patch implements this behaviour. Most of the complication in the new code occurs because adding a DataCon field to the Demand data type means that we have to define a separate IfaceDemand type for storage in interface files.
The patch validates but I haven't done any tests on nofib. I have confirmed that the new optimisation hits on some examples, though.
Trac metadata
| Trac field | Value |
|---|---|
| Version | 7.0.3 |
| Type | FeatureRequest |
| TypeOfFailure | OtherFailure |
| Priority | normal |
| Resolution | Unresolved |
| Component | Compiler |
| Test case | |
| Differential revisions | |
| BlockedBy | |
| Related | |
| Blocking | |
| CC | |
| Operating system | |
| Architecture |
Is blocked by
Relates to
Related merge requests 7
When these merge requests are accepted, this issue will be closed automatically.
Activity
mentioned in issue #3138
added Tfeature request Trac import labels
Attached file
5075.dpatch(download).Attached file
5075-testsuite.dpatch(download).assigned to @simonpj
changed milestone to %7.4.1
changed milestone to %7.6.1
mentioned in issue #6087
changed milestone to %7.6.2
mentioned in issue #7511
Trac metadata
Trac field Value CC → tkn.akio@gmail.com mentioned in commit d3b8991b
Still to come: the sum-CPR stuff is switched off for nested functions because it turns some let-no-escape functions into non-let-no-escape ones, which increases allocation. I'm hopeful that Nick F's work on late-lambda-lifting may solve this, in which case we can switch it on more vigorously. Hence leaving open for now.
I noticed that sum CPR does not trigger for this function, when it seems like it should:
loop :: Int -> Maybe Int -> Maybe Int loop n x = case n of 0 -> x _ -> loop (n-1) (fmap (+1) x)The specializations that the SpecConstr pass creates for this function seem to be perfect candidates for sum CPR:
Rec { loop_$s$wloop loop_$s$wloop = \ sc_sop sc1_sor -> case sc_sop of ds_Xmj { __DEFAULT -> loop_$s$wloop (-# ds_Xmj 1) (case sc1_sor of _ { I# x_amE -> I# (+# x_amE 1) }); 0 -> Just sc1_sor } end Rec } Rec { loop_$s$wloop1 loop_$s$wloop1 = \ sc_soq -> case sc_soq of ds_Xmj { __DEFAULT -> loop_$s$wloop1 (-# ds_Xmj 1); 0 -> Nothing } end Rec }Or am I mistaken?
Indeed. But the opportunity only arises after
SpecConstr, and we don't currently run the demand/CPR analyser afterSpecConstr, we run it before.Several other tickets (#6087, #5302 (closed), #6070 (closed)) identify other opportunities that could be exploited by running the demand analyser again, late in the optimisation pipeline.
Nick Frisby is planning to experiment with this. Thanks for a new example.
Simon
Confirmed: the Just gets ww'd-away with this core2core pipeline: SpecConstr, simpl, stranal, wwsplit, simpl.
Rec { $w$s$wloop $w$s$wloop = \ w_sqX w1_sqY -> case w_sqX of ds_Xng { __DEFAULT -> $w$s$wloop (-# ds_Xng 1) (case w1_sqY of _ { I# x_anM -> I# (+# x_anM 1) }); 0 -> (# w1_sqY #) } end Rec } loop_$s$wloop [InlPrag=INLINE[0]] :: ... [... Str=DmdType <S,U><L,U(U)>m2, Unf=Unf{Src=Worker=$w$s$wloop,...}] loop_$s$wloop = \ w_sqX w1_sqY -> case $w$s$wloop w_sqX w1_sqY of _ { (# ww1_sr4 #) -> Just ww1_sr4 } Rec { loop_$s$wloop1 loop_$s$wloop1 = \ sc_sqe -> case sc_sqe of ds_Xng { __DEFAULT -> loop_$s$wloop1 (-# ds_Xng 1); 0 -> Nothing } end Rec }That's an impressive prefix, "
s$w".In case any reader is wondering, the second argument to the loop gets unboxed if a strict variant of Maybe is used.
Thanks again for the compact example.
unassigned @simonpj
assigned to @simonpj
Just to be clear: This ticket is left open because of ticket:5075#comment:68711, right?
Also, in case someone looks here: The branch cpr-sum-types is considered dead; Its last commit ([9b0d70e/ghc]) is from October 2011, while CPR for sum types has hit master in January 2013 ([d3b8991b/ghc]). (Maybe we should rename dead branches to dead/...?)
In that case, let me add some numbers related to sum type CPR in local functions.
With current master [4d70840d/ghc], enabling CPR for sum types has this effect:
-------------------------------------------------------------------------------- Program Size Allocs Runtime Elapsed TotalMem -------------------------------------------------------------------------------- ansi +8.6% +0.5% 0.00 0.00 +0.0% awards +8.6% +0.2% 0.00 0.00 +0.0% cacheprof +8.0% +0.2% -3.1% -3.1% +0.0% calendar +8.6% +0.2% 0.00 0.00 +0.0% circsim +8.5% +1.1% -8.7% -8.7% -2.0% cryptarithm1 +8.7% -3.8% +0.5% +0.5% +0.0% cse +8.6% +0.2% 0.00 0.00 +0.0% fibheaps +8.6% -0.3% 0.02 0.02 +0.0% fluid +7.7% +3.4% 0.01 0.01 +0.0% fulsom +8.3% +0.1% 0.19 0.19 -31.2% hidden +8.3% +1.8% +3.4% +6.2% +0.0% kahan +8.1% +0.1% 0.17 0.17 +0.0% listcompr +8.6% +0.4% 0.06 0.05 +0.0% listcopy +8.6% +0.4% 0.07 0.06 +0.0% mandel +7.5% +0.3% 0.05 0.05 +0.0% mandel2 +8.7% +33.8% 0.00 0.00 +0.0% parser +8.1% +1.7% 0.02 0.02 +0.0% primetest +8.7% -0.2% 0.07 0.07 +0.0% reptile +8.5% +0.2% 0.01 0.01 +0.0% rewrite +8.5% +0.1% 0.02 0.02 +0.0% rfib +8.7% +0.6% 0.02 0.02 +0.0% spectral-norm +8.5% +0.7% -0.6% -0.6% +0.0% symalg +8.3% +0.2% 0.01 0.01 +0.0% tak +8.6% +1.3% 0.01 0.01 +0.0% transform +8.3% +0.1% +0.0% +0.0% +0.0% -------------------------------------------------------------------------------- Min +6.8% -3.8% -11.3% -11.3% -31.2% Max +8.7% +33.8% +3.9% +6.2% +6.1% Geometric Mean +8.4% +0.4% -1.8% -1.8% -0.4%So one quite extreme degradation, and otherwise minor losses.
If I make sure that join points do not get the CPR information unless the expression they are a join point for does, we get this change (relative to the same baseline):
-------------------------------------------------------------------------------- Program Size Allocs Runtime Elapsed TotalMem -------------------------------------------------------------------------------- cacheprof +8.0% +0.3% -4.7% -4.7% +1.8% calendar +8.6% +0.1% 0.00 0.00 +0.0% circsim +8.5% +0.2% -8.4% -8.4% -2.0% cryptarithm1 +8.6% -3.8% +1.5% +1.5% +0.0% cse +8.6% +0.2% 0.00 0.00 +0.0% fibheaps +8.5% -0.3% 0.03 0.03 +0.0% fulsom +8.2% -3.7% 0.19 0.19 -31.2% kahan +8.1% -0.2% 0.17 0.17 +0.0% listcompr +8.6% +0.4% 0.07 0.06 +0.0% listcopy +8.6% +0.4% 0.07 0.06 +0.0% maillist +8.6% +0.0% 0.04 0.04 +16.0% mandel +7.4% +0.2% 0.05 0.05 +0.0% parser +8.1% +1.7% 0.02 0.02 +0.0% primetest +8.6% -0.2% 0.07 0.07 +0.0% rewrite +8.5% +0.1% 0.01 0.01 +0.0% -------------------------------------------------------------------------------- Min +6.8% -3.8% -8.4% -8.4% -31.2% Max +8.7% +1.7% +3.2% +3.4% +16.0% Geometric Mean +8.3% -0.0% -2.0% -1.9% -0.2%This looks quite different now: A few losses, but much smaller than before. A mean of zero, and more gains than before. Unfortunately, the code size increase is still there...
If it were not for the code size increase, I’d suggest to merge these changes: Fewer special cases in transformations is a good thing. But it is probably not worth the code size increase, is it?
(Just for the record: In theory it is possible that CPR’ing a non-sum-type can destroy the join-point-property of a let. But it does not seem to happen: If I enable the cpr-join-point-fix, but keep CPR for sum types disabled, nofib does not record any change whatsoever.)
changed milestone to %7.10.1
changed milestone to %8.0.1
Related: D2436
added CPR/boxity analysis label
Is this still an issue? The logic from the OP is implemented and I think https://gitlab.haskell.org//ghc/ghc/issues/5075#note_68711 is a non-issue since we differentiate join points syntactically.
Do we do this for "nested functions", now, too? I think so, or at least I can't find the code path that checks for that.
Or is this ticket tracking the code size increase of 8%?
I'm not sure what the status is here
- What happens for the program in the Description? Do we have a regression test?
- Do we have a regression test for the program in this comment?
- Is sum-CPR switched off for nested functions? Apparently this was because "it turns some let-no-escape functions into non-let-no-escape ones, which increases allocation.", and as you say that's no longer necessary because we know which functions are join points. But let's double check.
- Does switching on/off sum-CPR (how?) make allocation go up in some programs? If so it'd be good to know why, even if we agree to accept it.
-
Short answers first, explanations below.
What happens for the program in the Description? Do we have a regression test?
When we give it the type signature
loop :: Int -> Either Int Int, it works. I couldn't find a regression test with that exact condition (x < 10).Do we have a regression test for the program in this comment?
I presume you mean this program:
loop :: Int -> Maybe Int -> Maybe Int loop n x = case n of 0 -> x _ -> loop (n-1) (fmap (+1) x)I grepped for the type signature and couldn't find it.
Is sum-CPR switched off for nested functions?
Yes, see the binding for
trim_sumsand Note [CPR for sum types]. More details below.Does switching on/off sum-CPR (how?) make allocation go up in some programs?
TBD, I'm on it.
Interestingly, the example from the Description does not get WW'd. Here it is, for completeness (note the lack of a type signature):
loop x = case x < 10 of True -> Left x False -> loop (x*2)This will be turned into the following Core before Demand Analysis:
loop = \ (@ t_a2e5) (@ b_a2e3) ($dOrd_a2ty :: Ord t_a2e5) ($dNum_a2tz :: Num t_a2e5) (eta_B1 :: t_a2e5) -> let { lvl_s2uU = fromInteger @ t_a2e5 $dNum_a2tz lvl_s2uT } in let { lvl_s2uW = fromInteger @ t_a2e5 $dNum_a2tz lvl_s2uV } in joinrec { loop_s2uR (x_atn :: t_a2e5) = case < @ t_a2e5 $dOrd_a2ty x_atn lvl_s2uU of { False -> jump loop_s2uR (* @ t_a2e5 $dNum_a2tz x_atn lvl_s2uW); True -> Data.Either.Left @ t_a2e5 @ b_a2e3 x_atn }; } in jump loop_s2uR eta_B1The inner loop is now actually a local binding, for which we historically trim CPR information in order not to spoil potential join points. This is detailed in Note [CPR for sum types] in DmdAnal and hinted at by https://gitlab.haskell.org//ghc/ghc/issues/5075#note_68711.
We really don't want to spoil the join point in this particular example, but there are probably plenty of cases when the heuristic
not . isTopLevel(seetrim_sums) is too broad: First, we unnecessarily penalise any local non-join binding. Second, when a join point has the CPR property, we can give it to the whole expression that defines the join point.When we give loop a proper type signature, like
loop :: Int -> Either Int Int, everything is well, though:Test.$wloop = \ (ww_s2gr :: GHC.Prim.Int#) -> case GHC.Prim.<# ww_s2gr 10# of { __DEFAULT -> Test.$wloop (GHC.Prim.*# ww_s2gr 2#); 1# -> (# GHC.Types.I# ww_s2gr #) } loop = \ (w_s2go :: Int) -> case w_s2go of { GHC.Types.I# ww1_s2gr -> case Test.$wloop ww1_s2gr of { (# ww3_s2gx #) -> Data.Either.Left @ Int @ Int ww3_s2gx } }So, I'm going to try to get rid of
trim_sums, which should propagate CPR from join points rather automatically by virtue of the different code path join points already take in LetDown.I'll evaluate the resulting version against HEAD and a modified version of HEAD where I set
trim_sums = True, effectively removing all sum CPR info. I think this whole thing about sum-CPR may be rendered moot by
Note [Don't CPR join points]inWorkWrap. It seems that we compute CPR info for join points, but do not use that info for w/w, regardless of whether it's a sum type. The example in that Note is great.I think that's all we need. Maybe we can kill off the special case in
DmdAnal?Edited by Simon Peyton Jones-
My job for benchmarking the baseline got stuck, but here's the comparison of no CPR for sums (i.e.,
trim_sums = True) vs CPR for all sums (i.e.,trim_sums = False):NoFib Results -------------------------------------------------------------------------------- Program Allocs Instrs -------------------------------------------------------------------------------- binary-trees -0.8% +3.8% digits-of-e2 -5.4% -1.5% fibheaps -0.3% -1.2% fish 0.0% +1.9% genfft -0.1% +1.1% integer 0.0% +1.0% last-piece +0.0% +2.0% mkhprog -1.3% -0.8% parser -0.4% -4.0% parstof -6.8% -4.0% reptile +25.9% +22.4% -------------------------------------------------------------------------------- Min -6.8% -4.0% Max +25.9% +22.4% Geometric Mean +0.1% +0.2%So there are regressions, most notably in
reptile. Binary sizes increased by 2.5% on average. Will investigate some time next week or so. -
Here is a testcase btw.:
-- | The resulting program should not contain any Just constructor -- top-level loop1 :: Int -> Maybe Int loop1 x | x > 10 = Just x | otherwise = loop1 (x*2) {-# NOINLINE loop1 #-} -- nested loop2 :: Int -> Maybe Int loop2 x = go x +? go (x+1) where Just x +? Just y = Just (x + y) _ +? _ = Nothing go z | z > 10 = Just (x + z) | otherwise = go (z*2) {-# NOINLINE loop2 #-} main = do let Just y = loop1 2 print y let Just z = loop2 2 print zThe resulting simplifier output should not contain any mentions of
Just(checkable bycheck_errmsg).loop2currently does contain mentions even after simplification. -
Interestingly, deactivating CPR for sums altogether makes things faster:
NoFib Results -------------------------------------------------------------------------------- Program Allocs Allocs Instrs Instrs no-cpr-su cpr-all-s no-cpr-su cpr-all-s -------------------------------------------------------------------------------- parstof +7.3% -0.0% +4.2% -0.0% reptile -20.6% 0.0% -18.3% 0.0% -------------------------------------------------------------------------------- Min -20.6% -0.3% -18.3% -1.0% Max +7.3% +0.4% +4.2% +2.0% Geometric Mean -0.1% +0.0% -0.2% +0.1%All wrt. to a recent HEAD commit. Doing no CPR for sums (i.e., always trimming sum CPR,
no-cpr-sums) has a huge win inreptile, which is probably the reason it's a win at all. Excludingreptile, doing sum CPR is a marginal win. Also note that doing CPR for all sums (i.e., never trim sum CPR,cpr-all-sums) makes things marginally slower.Binary sizes go down by 1.7% if we deactivate CPR for sums.
-
I believe that the regression in
reptileis due to the following spin-off of thehashfunction we now use throughout Nofib:lvl9 :: Int -> Int [GblId] lvl9 = case Mgrfuns.$wescom Mgrfuns.shapewindow1 lvl8 of { (# ww1, ww2 #) -> go3 (GHC.Types.: @ Char ww1 ww2) } Main.main_go = \ (ds :: [Char]) (eta :: Int) -> case ds of { [] -> lvl9 eta; : y ys -> case eta of { GHC.Types.I# ipv -> Main.main_go ys (case y of { GHC.Types.C# c# -> GHC.Types.I# (GHC.Prim.+# (GHC.Prim.ord# c#) (GHC.Prim.*# ipv 31#)) }) } }Note that
main_go(which is essentially a strict left fold computing a hash over a String) couldn't unbox itsIntparameter becauselvl9is a thunk that apparently couldn't be inlined. Without !312 (merged) (and probably also with it, seeing that idArity is 0), this will not assign a useful strictness signature tolvl9.This is an example where we want to look at how
lvl9is used to determine which strictness signature to give it.Short of being able to propagate the appropriate higher-order info, we have to blame the simplifier. Why wasn't
lvl9inlined? I guess if the wrapper for$wescomwasn't inlined intolvl9, it would just be a PAP amenable to being inlined intomain_go. This is the reason why the no-sum-cpr version (which doesn't WWescom) properly inlineslvl9and propagates the right strictness signatures.So: we should make sure that
lvl9properly inlines or is givenidArity1 (which would be a lie, strange). -
I tracked down how we got into the above situation. There is this huge foldl', 'optimised' to a foldr:
foldr k (... (foldr k id (escom bitcopy1 [...])) ...) (escom shapewindow [...])) NofibUtils.hash1The
escomwrappers get inlined, thus destroying the usful property that eachfoldrin itself will desugar to a PAP of the formlvl = go (escom shapewindow [...])which will have the proper arity 1 and inline, instead of
lvl = case $wescom shapewindow [...] of (# ww1, ww2 #) -> go (GHC.Types.: @ Char ww1 ww2)I wonder why the wrapper was inlined in the first place; It doesn't look like there's any incoming demand on that foldr argument justifying that decision.
-
What is
go3in the RHS oflvl9?I'm not sure if this is the particular
go3, but they are all pretty similar:go3_rnDO = \ (ds_a3er :: [Char]) (eta_B1 :: Int) -> case ds_a3er of { [] -> z1_rnDN eta_B1; : y_a3ew ys_a3ex -> case eta_B1 of { GHC.Types.I# ipv_smq5 -> go3_rnDO ys_a3ex (case y_a3ew of { GHC.Types.C# c#_a9VM -> GHC.Types.I# (GHC.Prim.+# (GHC.Prim.ord# c#_a9VM) (GHC.Prim.*# ipv_smq5 31#)) }) } }This accumulates a hash in
eta_B1of the stringds_a3er. Which is basicallymain_gofrom above with a different continuationz1_rnDN(which is a CAF again, exhibiting the same lack of argument strictness).Becauuse then
Mgrfuns.$wescom Mgrfuns.shapewindow1 lvl8might be evaluated many timesRight, the culprit is probably that the wrapper
escomwas inlined and the resulting case floated out of the innerfoldrapplication, becausefoldris strict in its third argument.Example:
foldr k (foldr k ys (escom shapewindow [...])) xs(*)
turns into (wrapper inlined)
foldr k (foldr k ys (case $wescom shapewindow [...] of ... -> ...)) xsand then (case floated out, because
foldris strict in its third argument, but not in its second)foldr k (case $wescom shapewindow [...] of ... -> foldr k ys (...)) xsNow, in practice the case expression gets really big and is floated out to top-level, leaving us with a non-PAP CAF
lvl9that can't be inlined.
Consider what happens if we were at (*) and didn't inline the wrapper (or didn't w/w
escomin the first place): No floating out of the argument is happening (I wonder why -- I bet this is documented somewhere) and we'd just float out a huge thunk likelvl_sm07 :: Int -> Int [LclId, Unf=Unf{Src=<vanilla>, TopLvl=True, Value=False, ConLike=False, WorkFree=False, Expandable=False, Guidance=IF_ARGS [] 410 0}] lvl_sm07 = GHC.Base.foldr @ Char @ (Int -> Int) k_slZS (GHC.Base.foldr @ Char @ (Int -> Int) k_slZS (GHC.Base.foldr @ Char @ (Int -> Int) k_slZS (GHC.Base.foldr @ Char @ (Int -> Int) k_slZS (GHC.Base.foldr @ Char @ (Int -> Int) k_slZS (id @ Int) (Mgrfuns.escom Mgrfuns.bitcopy1 (GHC.Types.: @ Int (GHC.Types.I# 15#) (GHC.Types.[] @ Int)))) clear) textreset) (Mgrfuns.escom Mgrfuns.font1 (GHC.Types.: @ Int (GHC.Types.I# 8#) (GHC.Types.[] @ Int)))) (Mgrfuns.escom Mgrfuns.shapewindow1 (GHC.Types.: @ Int (GHC.Types.I# 0#) (GHC.Types.: @ Int (GHC.Types.I# 0#) (GHC.Types.: @ Int (GHC.Types.I# 500#) (GHC.Types.: @ Int (GHC.Types.I# 500#) (GHC.Types.[] @ Int))))))which, after finally inlining
foldrand doing some float outs results inlvl_sm07 :: Int -> Int [LclId, Arity=1, Unf=Unf{Src=<vanilla>, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 20 60}] lvl_sm07 = go_X3f2 lvl_sm1iwhere
gois one of those arity 2 hashing functions. Note how there was an arity increase!. Crucially, this will just inline at call sites and we'll seegos strictness signature!Compare that to
lvl9above, has exactly the same purpose but doesn't inline because we floated out the case. Here is it again for reference:lvl9 = case Mgrfuns.$wescom Mgrfuns.shapewindow1 lvl8 of { (# ww1, ww2 #) -> go3 (GHC.Types.: @ Char ww1 ww2) }This will not inline and we won't see
go3strictness signature. Note how we in turn memoised the head of the list, but that's much worse than being able to propagatelvl9's argument strictness.Solutions
lvl9's strictness signature is pretty useless. Since top-level thunks are analysed with LetDown anyway (yay), maybe we should compute strictness signatures of top-level thunks fortypeArity? Seems hacky. Btw., this is an instance were I'm sure the idea from my master's thesis would be able to propagate the right strictness signature for arity 1.The other way out I see is to refrain from floating out the case expression in the first place, but that only turned out to be beneficial because the arity of the thunk increased, rendering it a PAP in one case but not in the other.
I feel like this isn't so much related to CPR anymore. Maybe we should fork this into its own ticket?
mentioned in issue #16570 (closed)
marked this issue as related to #16570 (closed)
added Pnormal label
-
I think this ticket needs to be solved (the issues around #5075 (comment 189715) and #16570 (closed)) before sum CPR can live up to its full potential.
Starting from #5075 (comment 189715), I still wonder how we could possibly turn out with
lvl = go (escom shapewindow [...])with arity 1 in one version, but withlvl = case $wescom shapewindow [...] of (# ww1, ww2 #) -> go (GHC.Types.: @ Char ww1 ww2)with arity 0 in the other. Note that transforming the former to the latter would only be sound ifgowas of arity 1 and strict in its argument, which it clearly isn't (it's of arity 2).Edited by Sebastian Graf mentioned in merge request !1427 (merged)
assigned to @sgraf812
mentioned in merge request !1866 (closed)
mentioned in issue #18793 (closed)
marked this issue as related to #18793 (closed)
removed the relation with #18793 (closed)
marked this issue as related to #18793 (closed)
-
I came up with a similarly offending program in #18793 (closed), hoping it's a faithful reproducer of #5075 (comment 189917).
mentioned in merge request !4207 (closed)
mentioned in commit 4920947f
mentioned in merge request !4229 (closed)
mentioned in commit 90161b96
mentioned in commit e3951ac4
mentioned in commit 4aaf4073
mentioned in commit 519cd13d
marked this issue as related to #14259
mentioned in merge request !5667 (closed)
-
It appears that fixing #18793 (closed) helped with the immediate problem described in the ticket. But the regression in
reptilepersisted even after this patch and is only fixed with !5667 (closed) where I deactivate CPR for recursive data cons (such as list cons), so basically not fixed at all.In
reptilewe have the more general setting--CR should try to generalise this to cope with more (all?) commands escom :: [Char] -> [Int] -> [Char] escom str ns = '\ESC' : foldr f "" ns where f n "" = show n ++ str f n s = show n ++ "," ++ s bitcopy, circle, shapewindow :: [Int] -> [Char] bitcopy = escom "b" -- xd yd w h xs ys circle = escom "o" -- x y r shapewindow = escom "W" -- x y w h -- and so onAnd if I look at the Core for
shapewindowor the others, I still see the wrapper ofescombeing inlined:shapewindow :: [Int] -> [Char] [LclIdX, Arity=1, Str=<L>, Cpr=2, Unf=Unf{Src=InlineStable, TopLvl=True, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=ALWAYS_IF(arity=0,unsat_ok=True,boring_ok=False) Tmpl= \ (eta_B0 [Occ=Once1] :: [Int]) -> escom shapewindow_s21n eta_B0}] shapewindow = \ (w_s25b [Dmd=ML] :: [Int]) -> case $wescom_s25e shapewindow_s21n w_s25b of { (# ww_s25D, ww_s25E #) -> GHC.Types.: @Char ww_s25D ww_s25E }This looks alright, but then later in
mainwe have something likefoldr k id (shapewindow [0,0,1150])and we'll inline the wrappershapewindowand getfoldr k id (case $wescom Mgrfuns.shapewindow1 [0,0,1150] of <rebuild (:)>)and we'll float out that case again, tolvl9 = case $wescom Mgrfuns.shapewindow1 [0,0,1150] of { (# x, xs #) -> foldr k id (x:xs) }And when we finally inline
foldrwe don't see that the inner loop thing actually has arity 1. Contrast that withlvl8 = shapewindow [0,0,1150] lvl9 = foldr k id lvl8Here, lvl9 has arity 1 and after inlining
foldrcompletely, we'll have a much more useful strictness signature.It took me a few hours to reproduce, but I finally was able to do so:
{-# LANGUAGE MagicHash, UnboxedTuples #-} module Lib (hash, salt, shapewindow, potatotile, setup, func) where import Data.List hiding (foldr,length) import Data.Char -- It's important that escom gets WW'd for its result to reproduce the issue -- We'll do so manually here escom :: [Char] -> [Int] -> [Char] escom str ns = case wescom str ns of (# x, xs #) -> x:xs {-# INLINE escom #-} wescom :: [Char] -> [Int] -> (# Char, [Char] #) wescom str ns = case '\ESC' : foldr f "" ns of x:xs -> (# x, xs #) where f n "" = show n ++ str f n s = show n ++ "," ++ s {-# NOINLINE wescom #-} shapewindow :: [Int] -> [Char] shapewindow = escom "W" -- x y w h func :: Int -> [Char] func mode = escom "b" [mode] setup :: String setup = "huge" {-# NOINLINE setup #-} potatotile :: [String] -> [Char] potatotile = escom "W" . map length -- x y w h {-# NOINLINE potatotile #-} hash :: String -> Int hash = foldl' (\acc c -> ord c + acc*31) 0 {-# INLINE hash #-} salt :: a -> IO a salt = pure {-# NOINLINE salt #-} module Main where import Control.Monad import Lib main = do input <- getContents replicateM_ 500 $ do s <- salt input print $ hash (func 5 ++ potatotile (lines s) ++ setup ++ func 15)If you look at the simplified core output, you see something like
-- RHS size: {terms: 17, types: 13, coercions: 0, joins: 0/0} z_r2GL :: Int -> Int [GblId] z_r2GL = case Lib.$wwescom Lib.func1 lvl1_r2GK of { (# ww_i29e, ww1_i29f #) -> \ (w_s2Fm :: Int) -> case w_s2Fm of { GHC.Types.I# ww2_s2Fo -> case $s$wgo1_r2GH ww_i29e ww1_i29f ww2_s2Fo of ww3_s2FR { __DEFAULT -> GHC.Types.I# ww3_s2FR } } }This is the problematic thunk that isn't eta-expanded. We want it to have arity 1 so that it has a useful strictness signature and so that we can unbox the
Int. Tracking the issue as #19970.This is all irrelevant to whether or not we should give sums the CPR property unconditionally, though. It was a very unfortunate coincidence that doing so triggered the regression in
reptile, which since has made it into GHC HEAD anyway. If !5667 (closed) lands, we'll only give it to non-recursive data constructors and I hope we'll soon be able to resolve this ticket, too.Edited by Sebastian Graf mentioned in issue #19970
marked this issue as related to #19970
mentioned in issue #20069
mentioned in commit 488213ad
mentioned in commit 5223c755
mentioned in commit 3206018e
mentioned in commit 9ee045e9
mentioned in commit 5e164935
mentioned in commit b5438052
mentioned in commit 332a021f
mentioned in commit 48b001e0
mentioned in commit 7164fc75
mentioned in commit cbe73af2
mentioned in commit 0b89d911
mentioned in commit 6191ea8c
mentioned in commit 1c2f8078
mentioned in commit 044e8bd6
mentioned in commit e11554a3
mentioned in commit 5acc1df3
mentioned in issue #14259
mentioned in commit 7e1df129
closed with commit cd1b016f
mentioned in commit cd1b016f
mentioned in commit fb67adf4
mentioned in commit bd2c3e9c
mentioned in merge request !7609 (closed)
mentioned in commit bbb02a5e
mentioned in commit 18811fca
mentioned in commit 042e6a8b
mentioned in commit 7ad72037
mentioned in commit d975f23a
mentioned in commit b7f62c43
mentioned in commit df32f60f
mentioned in commit fe7b785f
mentioned in commit 28786e04
mentioned in commit 3e3a12d7
mentioned in commit 54852df4
mentioned in commit 580563c2
mentioned in commit 1a62071f
mentioned in commit 0ce0638f
mentioned in commit 0ba95a2f
mentioned in commit a3dfdf19
mentioned in commit 9791e547
mentioned in commit f7ee9f58
mentioned in commit 8a804212
mentioned in commit 713a8887
mentioned in commit c1183c21
mentioned in commit 11baab00
mentioned in commit 1680e1f8
mentioned in commit db64871c
mentioned in commit d2f8c39e
mentioned in commit d32c497f
mentioned in commit 12ae661a
mentioned in commit 110cded6
mentioned in commit 08445a5d
mentioned in commit 3cb7bd71
mentioned in commit fbd94388
mentioned in commit 9c358588
mentioned in commit a74d8606
mentioned in commit fa43c07e
mentioned in commit 6718280c
mentioned in commit 94a7209d
mentioned in commit 6c4d9a57
mentioned in commit 1575c4a5
mentioned in commit 9f68cd5f
