[GHC] #13081: Code size explosion with with inlined instances for fixed point of functor

[GHC]

#13081: Code size explosion with with inlined instances for fixed point of functor
-------------------------------------+-------------------------------------
           Reporter:  kja            |             Owner:
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.0.2
           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:
-------------------------------------+-------------------------------------
 The following code is not feasible to compile due to a massive explosion
 in "terms" generated by the simplifier as reported by `-v` flag.

 {{{#!hs
 ---[ import Data.Functor.Fixedpoint from unification-fd ]-----------------

 newtype Fix f = Fix { unFix :: f (Fix f) }

 instance (Eq (f (Fix f))) => Eq (Fix f) where
   x == y  = unFix x == unFix y
   x /= y  = unFix x /= unFix y

 --------------------------------------------------------------------------------

 data Foo' a = A
             | B a
             | C a
             | D a a
             | E a a a
             deriving (Eq)

 type Foo = Fix Foo'

 bar :: Foo -> Foo -> m ()
 bar t t' =
   if t == t'
   then undefined
   else undefined
 }}}

 Compiling with `-v` on 8.0.2 yields:

 {{{
 [1 of 1] Compiling Lib              ( src/Lib.hs, .stack-
 work/dist/x86_64-osx/Cabal-1.24.2.0/build/Lib.o )
 *** Parser [Lib]:
 !!! Parser [Lib]: finished in 0.90 milliseconds, allocated 0.797 megabytes
 *** Renamer/typechecker [Lib]:
 !!! Renamer/typechecker [Lib]: finished in 136.61 milliseconds, allocated
 57.026 megabytes
 *** Desugar [Lib]:
 Result size of Desugar (after optimization)
   = {terms: 257, types: 237, coercions: 24}
 !!! Desugar [Lib]: finished in 2.38 milliseconds, allocated 1.264
 megabytes
 *** Simplifier [Lib]:
 Result size of Simplifier iteration=1
   = {terms: 297, types: 305, coercions: 18}
 Result size of Simplifier = {terms: 294, types: 301, coercions: 18}
 !!! Simplifier [Lib]: finished in 3.78 milliseconds, allocated 2.165
 megabytes
 *** Specialise [Lib]:
 Result size of Specialise = {terms: 294, types: 301, coercions: 18}
 !!! Specialise [Lib]: finished in 0.52 milliseconds, allocated 0.382
 megabytes
 *** Float out(FOS {Lam = Just 0,
                    Consts = True,
                    OverSatApps = False}) [Lib]:
 Result size of Float out(FOS {Lam = Just 0,
                               Consts = True,
                               OverSatApps = False})
   = {terms: 366, types: 418, coercions: 18}
 !!! Float out(FOS {Lam = Just 0,
                    Consts = True,
                    OverSatApps = False}) [Lib]: finished in 1.38
 milliseconds, allocated 1.657 megabytes
 *** Simplifier [Lib]:
 Result size of Simplifier iteration=1
   = {terms: 364, types: 362, coercions: 38}
 Result size of Simplifier iteration=2
   = {terms: 311, types: 325, coercions: 38}
 Result size of Simplifier iteration=3
   = {terms: 395, types: 417, coercions: 74}
 Result size of Simplifier iteration=4
   = {terms: 395, types: 410, coercions: 74}
 Result size of Simplifier = {terms: 395, types: 410, coercions: 74}
 !!! Simplifier [Lib]: finished in 9.11 milliseconds, allocated 5.846
 megabytes
 *** Simplifier [Lib]:
 Result size of Simplifier iteration=1
   = {terms: 991, types: 1,022, coercions: 326}
 Result size of Simplifier iteration=2
   = {terms: 991, types: 973, coercions: 326}
 Result size of Simplifier iteration=3
   = {terms: 5,323, types: 5,433, coercions: 2,090}
 Result size of Simplifier iteration=4
   = {terms: 5,323, types: 5,090, coercions: 2,090}
 Result size of Simplifier
   = {terms: 5,323, types: 5,090, coercions: 2,090}
 !!! Simplifier [Lib]: finished in 95.35 milliseconds, allocated 60.572
 megabytes
 *** Simplifier [Lib]:
 Result size of Simplifier iteration=1
   = {terms: 35,839, types: 36,118, coercions: 14,438}
 Result size of Simplifier iteration=2
   = {terms: 35,839, types: 33,717, coercions: 14,438}
 Result size of Simplifier iteration=3
   = {terms: 250,219, types: 250,145, coercions: 100,874}
 Result size of Simplifier iteration=4
   = {terms: 250,219, types: 233,338, coercions: 100,874}
 Result size of Simplifier
   = {terms: 250,219, types: 233,338, coercions: 100,874}
 !!! Simplifier [Lib]: finished in 5567.46 milliseconds, allocated 2798.871
 megabytes
 *** Float inwards [Lib]:
 Result size of Float inwards
   = {terms: 250,219, types: 233,338, coercions: 100,874}
 !!! Float inwards [Lib]: finished in 744.72 milliseconds, allocated
 594.429 megabytes
 *** Called arity analysis [Lib]:
 Result size of Called arity analysis
   = {terms: 250,219, types: 233,338, coercions: 100,874}
 !!! Called arity analysis [Lib]: finished in 311.34 milliseconds,
 allocated 190.166 megabytes
 *** Simplifier [Lib]:

 }}}

 ... at which point it seems to "hang", though depending on hardware it
 might still succeed. It is clearly proportional in the number of
 constructors and occurrences of the type variable in those constructor. To
 aggravate the issue, simply add more of both.

 Any of ...

   * compiling with -O0
   * adding a NOINLINE pragma to `(==)` in the instance for `Fix`
   * implementing a manual `Eq` instance for `Foo` and adding a NOINLINE
 pragma there

 ... solves the issue for me.

 Observed on both 8.0.1 (Windows and macOS) and 8.0.2 (macOS)

 Not present on 7.10.3 (Windows and macOS).

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13081>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler