[GHC] #12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: None/Unknown Unknown/Multiple | Test Case: | Blocked By: Blocking: | Related Tickets: Differential Rev(s): | Wiki Page: -------------------------------------+------------------------------------- The example is slimmed down unit test of Annotations-0.2.1 hackage package. If we try to compile Bug.hs with -O0 it compiles quickly. Trying it with -O1 makes GHC-8.0.1 takes a minute to finish. {{{#!hs -- Bug1.hs: {-# LANGUAGE StandaloneDeriving #-} {-# LANGUAGE UndecidableInstances #-} {- # OPTIONS_GHC -O1 #-} module Bug () where import Prelude (Eq) data ExprF rT = ExprF rT rT deriving Eq newtype Expr = Expr (Fix ExprF) deriving Eq newtype Fix fT = In (fT (Fix fT)) deriving instance Eq (f (Fix f)) => Eq (Fix f) }}} {{{ $ time ghc-8.0.1 -c -O0 Bug1.hs -fforce-recomp real 0m0.611s user 0m0.549s sys 0m0.053s $ time ghc-8.0.1 -c -O1 Bug1.hs -fforce-recomp real 1m2.199s user 1m1.676s sys 0m0.465s }}} 7.10.2 for comparison is very quick in both O0/O1: {{{ $ time ghc-7.10.2 -c -O0 Bug1.hs -fforce-recomp real 0m0.220s user 0m0.183s sys 0m0.036s $ time ghc-7.10.2 -c -O1 Bug1.hs -fforce-recomp real 0m0.237s user 0m0.213s sys 0m0.023s }}} The real ExprF datatype uses more constructors and instances: {{{ data ExprF rT = Add rT rT | Sub rT rT | Mul rT rT | Div rT rT | Num Int deriving (Eq, Show) }}} That requires a lot of time and space to finish (Bug2.hs in attach). I've stopped it after 5 minutes (took ~8GB RAM). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by slyfox): * Attachment "Bug1.hs" added. Bug1.hs makes a minute to compile -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by slyfox): * Attachment "Bug2.hs" added. Bug2.hs takes more than 5 minutes to compile -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by osa1): Nice find. Here is some stats: {{{ =========================================Bug========================================= CodeGen 19976.00 ms 40880.83 mb 62.9% of total time Simplifier (7) 10302.00 ms 9418.43 mb 32.4% of total time CorePrep 762.00 ms 323.56 mb 2.4% of total time CoreTidy 469.00 ms 274.51 mb 1.5% of total time Common sub-expression 87.00 ms 60.19 mb 0.3% of total time Float inwards (2) 81.00 ms 51.34 mb 0.3% of total time Renamer/typechecker 47.00 ms 44.12 mb 0.1% of total time Demand analysis 21.00 ms 19.45 mb 0.1% of total time Worker Wrapper binds 3.00 ms 1.89 mb 0.0% of total time Parser 2.00 ms 0.50 mb 0.0% of total time Specialise 0.00 ms 0.23 mb 0.0% of total time Desugar 0.00 ms 0.65 mb 0.0% of total time Called arity analysis 0.00 ms 0.82 mb 0.0% of total time ------------------------------------------------------------------------------------- Total 31750.00 ms 51076.53 mb 100.0% of total time ======================Total====================== CodeGen 62.92% Simplifier 32.45% CorePrep 2.40% CoreTidy 1.48% Common sub-expression 0.27% Float inwards 0.26% Renamer/typechecker 0.15% Demand analysis 0.07% Worker Wrapper binds 0.01% Parser 0.01% Specialise 0.00% Desugar 0.00% Called arity analysis 0.00% }}} Simplifier is running 7 times! More interestingly, I wanted to have a look at Core and STG, and tried -ddump-simpl. It took about 5 minutes until I killed the process and realized that generated incomplete Core output is 664M already {{{ -rw-r--r-- 1 omer users 664M Jun 26 14:18 Bug1.dump-simpl }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by ezyang: @@ -11,1 +11,0 @@ - {- # OPTIONS_GHC -O1 #-} New description: The example is slimmed down unit test of Annotations-0.2.1 hackage package. If we try to compile Bug.hs with -O0 it compiles quickly. Trying it with -O1 makes GHC-8.0.1 takes a minute to finish. {{{#!hs -- Bug1.hs: {-# LANGUAGE StandaloneDeriving #-} {-# LANGUAGE UndecidableInstances #-} module Bug () where import Prelude (Eq) data ExprF rT = ExprF rT rT deriving Eq newtype Expr = Expr (Fix ExprF) deriving Eq newtype Fix fT = In (fT (Fix fT)) deriving instance Eq (f (Fix f)) => Eq (Fix f) }}} {{{ $ time ghc-8.0.1 -c -O0 Bug1.hs -fforce-recomp real 0m0.611s user 0m0.549s sys 0m0.053s $ time ghc-8.0.1 -c -O1 Bug1.hs -fforce-recomp real 1m2.199s user 1m1.676s sys 0m0.465s }}} 7.10.2 for comparison is very quick in both O0/O1: {{{ $ time ghc-7.10.2 -c -O0 Bug1.hs -fforce-recomp real 0m0.220s user 0m0.183s sys 0m0.036s $ time ghc-7.10.2 -c -O1 Bug1.hs -fforce-recomp real 0m0.237s user 0m0.213s sys 0m0.023s }}} The real ExprF datatype uses more constructors and instances: {{{ data ExprF rT = Add rT rT | Sub rT rT | Mul rT rT | Div rT rT | Num Int deriving (Eq, Show) }}} That requires a lot of time and space to finish (Bug2.hs in attach). I've stopped it after 5 minutes (took ~8GB RAM). -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by vladki): Just in case, removing one of the parameters in the `ExprF` constructor makes the problem go away: {{{ data ExprF rT = ExprF rT deriving Eq }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * keywords: => deriving-perf -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * failure: None/Unknown => Compile-time performance bug -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * cc: RyanGlScott (added) Comment: Yikes. Interestingly, the way the `Eq (Fix f)` instance is constructed plays a large role in the slowdown. Since it's a newtype, GHC defaults to deriving that instance via `GeneralizedNewtypeDeriving`, i.e., {{{#!hs instance Eq (f (Fix f)) => Eq (Fix f) where (==) = coerce ((==) :: f (Fix f) -> f (Fix f) -> Bool) :: Fix f -> Fix f -> Bool }}} But if you implement it the "stock" way, i.e., {{{#!hs instance Eq (f (Fix f)) => Eq (Fix f) where In x == In y = x == y }}} Then it compiles instantly. So perhaps the coercion solver is to blame here? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): The solver for `Coercible` is known to struggle with recursive newtypes, where coercibility is (I believe) undecidable. Maybe we should use "stock" for recursive newtypes? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * cc: niteria (added) Comment: Replying to [comment:7 goldfire]:
Maybe we should use "stock" for recursive newtypes?
Maybe. But it bothers me that this used to work fine in 7.10.3. I did some git archaeology and discovered that this commit ( http://git.haskell.org/ghc.git/commit/9cb192ce4b34a472041010df9c30f5d741eb02... ) is responsible for this regression, but I don't understand why a change to the digraph code led to this. niteria, any thoughts as the author of the commit? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by niteria): Shot in the dark: does solving coercibility for recursive newtypes involve finding fixpoints? I've run into one place in the code generator once where not returning the elements of a set in the Unique order would make it never find a fixpoint, because the insertion order would oscillate between 2 values. Otherwise, maybe using Unique order for SCC had some nice properties in this case. But under normal circumstances, I wouldn't expect my commit to cause that. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by niteria): I was able to reproduce it, and indeed my commit has some effect. I narrowed it down with https://phabricator.haskell.org/P127 to ordering inside `occAnalRecBind`. It appears that the simplifier is sensitive to this order in this case. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by niteria): Simplifier stats reveal significantly more `Class op ==` rule rewrites, and passing `-fno-enable-rewrite-rules` fixes the issue. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM
-------------------------------------+-------------------------------------
Reporter: slyfox | Owner:
Type: bug | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 8.0.1
Resolution: | Keywords: deriving-perf
Operating System: Unknown/Multiple | Architecture:
Type of failure: Compile-time | Unknown/Multiple
performance bug | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s):
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by Simon Peyton Jones
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: merge Priority: normal | Milestone: 8.0.3 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/should_compile/T12234 Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * status: new => merge * testcase: => perf/should_compile/T12234 * milestone: => 8.0.3 Comment: Fixed! Thanks for a great report. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: merge Priority: normal | Milestone: 8.0.3 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/should_compile/T12234 Blocked By: | Blocking: Related Tickets: #13056 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * related: => #13056 Comment: #13056 demonstrates another occurrence of this bug, this time involving `Foldable`. But unlike the program in this ticket, it doesn't require any GHC extensions like `UndecidableInstances` to trigger it. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM
-------------------------------------+-------------------------------------
Reporter: slyfox | Owner:
Type: bug | Status: merge
Priority: normal | Milestone: 8.0.3
Component: Compiler | Version: 8.0.1
Resolution: | Keywords: deriving-perf
Operating System: Unknown/Multiple | Architecture:
| Unknown/Multiple
Type of failure: Compile-time | Test Case:
performance bug | perf/should_compile/T12234
Blocked By: | Blocking:
Related Tickets: #13056 | Differential Rev(s):
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by Ryan Scott
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: Type: bug | Status: merge Priority: normal | Milestone: 8.0.3 Component: Compiler | Version: 8.0.1 Resolution: | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/should_compile/T12234 Blocked By: | Blocking: Related Tickets: #13056, #13081 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * related: #13056 => #13056, #13081 Comment: #13081 is yet another occurrence of this. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM -------------------------------------+------------------------------------- Reporter: slyfox | Owner: (none) Type: bug | Status: closed Priority: normal | Milestone: 8.2.1 Component: Compiler | Version: 8.0.1 Resolution: fixed | Keywords: deriving-perf Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | perf/should_compile/T12234 Blocked By: | Blocking: Related Tickets: #13056, #13081 | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * status: merge => closed * resolution: => fixed -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12234#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC