[GHC] #11991: Generics deriving is quadratic

[GHC]

#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