Here is a cue: Removing the `!` on `t` in `mkMachine` removes *all*

#10148: Optimization causes repeated computation -------------------------------------+------------------------------------- Reporter: akio | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by akio): Thank you for looking at this! Replying to [comment:1 nomeata]: trace output. So it seems that (possibly as a result of minimizing the code), `t` and hence `array_adjust` is not actually used. This (function strict in an argument, but argument is unused) might make GHC be a bit too liberal in what it does with the code. Yes, this is indeed a result of minimizing the code. I'll attach a version of the test program that does not rely solely on the bangs. In this version, if I remove the bangs in `mkMachine` (on both `m` and `t`), the amount of trace output grows exponentially (not quadratically) when compiled with `-O1`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10148#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10148: Optimization causes repeated computation -------------------------------------+------------------------------------- Reporter: akio | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by nomeata): It must be related to the `error` call in `adjustA`. Removing the branch, or replacing it by something terminating, even replacing it by `undefined` makes the bug disappear. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10148#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10148: Optimization causes repeated computation -------------------------------------+------------------------------------- Reporter: akio | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by akio): Looking at Core and STG outputs for `repeated2.hs`, it looks like incorrect demand information is causing the problem. ghc 7.10.20150123 produces the following core for `gstep` when invoked with `-O1 -fno-state-hack`: {{{ Rec { Main.$wgstep [InlPrag=[0], Occ=LoopBreaker] :: GHC.Types.Int -> GHC.Prim.Int# -> (# GHC.Types.Int -> Main.Machine, GHC.Types.Int #) [GblId, Arity=2, Str=DmdType , Unf=OtherCon []] Main.$wgstep = \ (ww :: GHC.Types.Int) (ww1 [Occ=Once] :: GHC.Prim.Int#) -> case GHC.Prim.<# ww1 0 of sat { __DEFAULT -> case GHC.Prim.tagToEnum# @ GHC.Types.Bool sat of _ [Occ=Dead] { GHC.Types.False -> let { ipv [Occ=OnceL, Dmd=] :: GHC.Types.Int [LclId, Str=DmdType] ipv = let { sat [Occ=Once, Dmd=] :: GHC.Base.String [LclId, Str=DmdType] sat = let { sat [Occ=Once] :: [GHC.Types.Char] [LclId, Str=DmdType] sat = case ww of _ [Occ=Dead] { GHC.Types.I# ww3 [Occ=Once] -> case GHC.Show.$wshowSignedInt 0 ww3 (GHC.Types.[] @ GHC.Types.Char) of _ [Occ=Dead] { (# ww5 [Occ=Once], ww6 [Occ=Once] #) -> GHC.Types.: @ GHC.Types.Char ww5 ww6 } } } in GHC.CString.unpackAppendCString# "adj "# sat } in Debug.Trace.trace @ GHC.Types.Int sat ww } in let { sat [Occ=Once] :: GHC.Types.Int -> Main.Machine [LclId, Str=DmdType] sat = \ (w [Occ=Once!] :: GHC.Types.Int) -> case w of _ [Occ=Dead] { GHC.Types.I# ww3 [Occ=Once] -> case Main.$wgstep ipv ww3 of _ [Occ=Dead] { (# ww5 [Occ=Once], ww6 [Occ=Once] #) -> Main.Machine ww5 ww6 } } } in (# sat, ww #); GHC.Types.True -> case GHC.Err.undefined of _ [Occ=Dead] { } } } end Rec } }}} Note the `ipv [Occ=OnceL, Dmd=]` part. If I understand it correctly, `Dmd` claims that `ipv` will not be used at all. However, this is wrong and `ipv` will be used in the recursive call to `Main.$wgstep`. This demand info then causes a single-entry closure (`\s`) to be generated for `ipv` in the STG. If I replace the `undefined i` with just `undefined` in the source file, the corresponding definition has no demand information, and its closure is marked as updatable (`\u`) rather than single-entry. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10148#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10148: Optimization causes repeated computation -------------------------------------+------------------------------------- Reporter: akio | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by akio): It looks like the simplifier does not preserve correctness of demand information. After the worker-wrapper pass, I have this fragment of code {{{ of m'_axp [Dmd=] { Array ipv_s1i9 [Dmd=] -> Main.Machine (gstep m'_axp) t_axr } }}} Here, the demand info on `ipv_s1i9` is correct, it is indeed unused. However, after one iteration of simplifier pass, it becomes: {{{ of m'_axp [Dmd=] { Array ipv_s1i9 [Dmd=] -> (# \ (w_s3Ix :: Int) -> case w_s3Ix of _ [Occ=Dead] { GHC.Types.I# ww_X3IZ -> case $wgstep_s3II ipv_s1i9 ww_X3IZ of _ [Occ=Dead] { (# ww_X3Ja, ww_X3Jc #) -> Main.Machine ww_X3Ja ww_X3Jc } }, ww_s3IA #) }}} Now `ipv_s1i9` is referenced and will be used, but its usage information has not been updated. I've found the note `[Case alternative occ info]` in Simplify.hs, which explains why the occurrence info on case-bound variables should be zapped. I tried zapping the usage info as well as the occurrence info here (patch attached). It seems to compile `repeated2.hs` fine, but I'm not sure about a few points: * Is the approach right? i.e. is it a good idea to manually modify the usage info in the simplifier? * Probably the patch is overly conservative, in that it zaps the strictness info as well as the usage info. However, how hard should I try to preserve information? For example, should the code have a special case for when the case binder and the scrutinee are both marked unused? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10148#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10148: Optimization causes repeated computation -------------------------------------+------------------------------------- Reporter: akio | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by Simon Peyton Jones ): In [changeset:"9f0f99fd41ff82cc223d3b682703e508efb564d2/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="9f0f99fd41ff82cc223d3b682703e508efb564d2" Fix a long-standing bug in the demand analyser This patch fixes Trac #10148, an outright and egregious bug in the demand analyser. It is explained in Note [Demand on case-alternative binders] in Demand.hs. I did some other minor refactoring. To my astonishment I got some big compiler perf changes * perf/compiler/T5837: bytes allocated -76% * perf/compiler/T5030: bytes allocated -10% * perf/compiler/T3294: max bytes used -25% Happy days }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10148#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10148: Optimization causes repeated computation -------------------------------------+------------------------------------- Reporter: akio | Owner: Type: bug | Status: new Priority: normal | Milestone: 7.10.2 Component: Compiler | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | stranal/should_run/T10148 Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Changes (by simonpj): * testcase: => stranal/should_run/T10148 * milestone: => 7.10.2 Comment: Thank you akio and Joachim for your help in tracking this one down. Austin: please merge. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10148#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10148: Optimization causes repeated computation -------------------------------------+------------------------------------- Reporter: akio | Owner: Type: bug | Status: patch Priority: normal | Milestone: 7.10.2 Component: Compiler | Version: 7.10.1-rc1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | stranal/should_run/T10148 Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Changes (by thomie): * status: new => patch -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10148#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#10148: Optimization causes repeated computation -------------------------------------+------------------------------------- Reporter: akio | Owner: Type: bug | Status: closed Priority: normal | Milestone: 7.10.2 Component: Compiler | Version: 7.10.1-rc1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | stranal/should_run/T10148 Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Changes (by thoughtpolice): * status: merge => closed * resolution: => fixed Comment: Merged to `ghc-7.10` via 37f928aa8bb55f888ca6e22ec9f8605f695d0b44 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10148#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler