[GHC] #12234: 'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM

[GHC]

#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