#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