#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