Skip to content

'deriving Eq' on recursive datatype makes ghc eat a lot of CPU and RAM

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.

-- Bug1.hs:
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE UndecidableInstances #-}

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
  1. 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).

Edited by Edward Z. Yang
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information