[GHC] #11991: Generics deriving is quadratic

27 Apr 2016

      #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