[GHC] #11991: Generics deriving is quadratic
#11991: Generics deriving is quadratic -------------------------------------+------------------------------------- Reporter: nh2 | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Keywords: | 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: -------------------------------------+------------------------------------- I'm compiling some code with many sum type alternatives and it's absurdly slow. {{{ {-# LANGUAGE DeriveGeneric #-} import GHC.Generics (Generic) data D = D1 | D2 | ... | D400 deriving (Generic) main = return () }}} I did a little benchmark and it's actually precisely O(n²) in the number of alternatives. Easy repro: https://github.com/nh2/ghc-generics-deriving-is-slow/ I assume that this is a bug and it should be linear. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11991 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11991: Generics deriving is quadratic -------------------------------------+------------------------------------- Reporter: nh2 | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Generics 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 nh2): * keywords: => Generics -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11991#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11991: Generics deriving is quadratic -------------------------------------+------------------------------------- Reporter: nh2 | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Generics 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: | -------------------------------------+------------------------------------- Description changed by nh2: @@ -19,0 +19,2 @@ + + Note that it is also quadratic in memory usage. New description: I'm compiling some code with many sum type alternatives and it's absurdly slow. {{{ {-# LANGUAGE DeriveGeneric #-} import GHC.Generics (Generic) data D = D1 | D2 | ... | D400 deriving (Generic) main = return () }}} I did a little benchmark and it's actually precisely O(n²) in the number of alternatives. Easy repro: https://github.com/nh2/ghc-generics-deriving-is-slow/ I assume that this is a bug and it should be linear. Note that it is also quadratic in memory usage. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11991#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#11991: Generics deriving is quadratic -------------------------------------+------------------------------------- Reporter: nh2 | Owner: Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: duplicate | Keywords: Generics 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 nh2): * status: new => closed * resolution: => duplicate Comment: Looks like I just duplicated #5642. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11991#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC