Opened 3 years ago

Closed 3 years ago

#13081 closed bug (duplicate)

Code size explosion with with inlined instances for fixed point of functor

Reported by: kja Owned by:
Priority: normal Milestone:
Component: Compiler Version: 8.0.2
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

The following code is not feasible to compile due to a massive explosion in "terms" generated by the simplifier as reported by -v flag.

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

Change History (4)

comment:1 Changed 3 years ago by mpickering

Resolution: duplicate
Status: newclosed

It doesn't take a long time with HEAD but I'm not sure which ticket this is a duplicate of. Thanks for the nice small report!

comment:2 Changed 3 years ago by rwbarton

Resolution: duplicate
Status: closednew

If it's a regression from 7.10 and fixed in HEAD then it might make sense to merge the fix to 8.0.3, no?

comment:3 Changed 3 years ago by RyanGlScott

I'm 90% sure it's a duplicate of #13056.

comment:4 Changed 3 years ago by RyanGlScott

Resolution: duplicate
Status: newclosed

Er, #12234 rather, which has been marked as merge.

I confirmed that 517d03e41b4f5c144d1ad684539340421be2be2a in particular fixed this regression. There's already been a performance test added (perf/should_compile/T12234) that's very similar in spirit to the one in this ticket, so I'll just close this as a duplicate.

Note: See TracTickets for help on using tickets.