#9198: large performance regression in type checker speed in 7.8 -------------------------------------------------+------------------------- Reporter: carter | Owner: Type: bug | Status: new Priority: high | Milestone: Component: Compiler (Type checker) | Version: 7.8.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time performance bug | Unknown/Multiple Test Case: | Difficulty: Blocking: | Unknown | Blocked By: | Related Tickets: -------------------------------------------------+------------------------- Comment (by goldfire): With typos removed and types added, this looks like {{{ begin :: Monad m => (m () -> t) -> t begin cont = cont (return ()) a :: IO a -> (IO () -> t) -> t a m cont = cont (m >> putStrLn "a") end :: t -> t end m = m main = begin a a a a a a a a a a a a a a a a a a a a end }}} Including the type signatures does not improve performance. Great example case -- this does indeed need to be fixed. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9198#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9198: large performance regression in type checker speed in 7.8 -------------------------------------+------------------------------------- Reporter: carter | Owner: Type: bug | Status: new Priority: high | Milestone: 7.10.1 Component: Compiler | Version: 7.8.2 (Type checker) | Keywords: Resolution: | Architecture: Unknown/Multiple Operating System: | Difficulty: Unknown Unknown/Multiple | Blocked By: Type of failure: Compile- | Related Tickets: time performance bug | Test Case: | Blocking: | Differential Revisions: | -------------------------------------+------------------------------------- Old description:

it was recently demonstrated on the haskell-cafe mailing list that the following code takes measurably longer to type check in GHC 7.8.2 than in GHC 7.6.

http://www.haskell.org/pipermail/haskell-cafe/2014-June/114562.html

the program example is as follows {{{ begin cont = cont (return ()) a m =cont (m >> putstrn "a") end m = m main = begin a a a a a a a a a a a a a a a a a end

}}} takes about a second to type check in ghc 7.8, and is "instant" in 7.6 ()

each additional a doubles the time to type check the program

{{{ main = begin a a a a a a a a a a a a a a a a a a a a a a a a end }}}

takes longer than I have the patience to wait :) (so more than 5 seconds)

the author of the email notes that a related program

{{{ main = id id id id id id id id id id id id id id id id id id id id id id (return ()) }}} has the exponential complexity in both 7.8.2 and 7.6.2

This It could very well be that some of the type checker changes between 7.8 and 7.6 enlarged the space of programs that trip up exponential worst case behavior, but one way or another understanding *why* this happened

New description: it was recently demonstrated on the haskell-cafe mailing list that the following code takes measurably longer to type check in GHC 7.8.2 than in GHC 7.6. http://www.haskell.org/pipermail/haskell-cafe/2014-June/114562.html the program example is as follows {{{ begin :: Monad m => (m () -> t) -> t begin cont = cont (return ()) a :: IO a -> (IO () -> t) -> t a m cont = cont (m >> putStrLn "a") end :: t -> t end m = m main = begin a a a a a a a a a a a a a a a a a a end }}} takes about a second to type check in ghc 7.8, and is "instant" in 7.6 () each additional a doubles the time to type check the program {{{ main = begin a a a a a a a a a a a a a a a a a a a a a a a a end }}} takes longer than I have the patience to wait :) (so more than 5 seconds) the author of the email notes that a related program {{{ main = id id id id id id id id id id id id id id id id id id id id id id (return ()) }}} has the exponential complexity in both 7.8.2 and 7.6.2 This It could very well be that some of the type checker changes between 7.8 and 7.6 enlarged the space of programs that trip up exponential worst case behavior, but one way or another understanding *why* this happened -- Comment (by thomie): For what it's worth: crude timing results for the example from the description with 18 `a`'s: ||= GHC =||= Time =|| ||= 7.4.2 =|| 2.2s || ||= 7.6.3 =|| 2.2s || ||= 7.8.3 =|| 3.4s || ||= 7.9.20141113 =|| 3.8s || Command: `time ghc -c -fforce-recomp test.hs` -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9198#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9198: large performance regression in type checker speed in 7.8 -------------------------------------+------------------------------------- Reporter: carter | Owner: Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler (Type | Version: 7.8.2 checker) | Resolution: | 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: | -------------------------------------+------------------------------------- Changes (by bgamari): * milestone: 8.0.1 => 8.2.1 Old description:

it was recently demonstrated on the haskell-cafe mailing list that the following code takes measurably longer to type check in GHC 7.8.2 than in GHC 7.6.

http://www.haskell.org/pipermail/haskell-cafe/2014-June/114562.html

the program example is as follows {{{ begin :: Monad m => (m () -> t) -> t begin cont = cont (return ())

a :: IO a -> (IO () -> t) -> t a m cont = cont (m >> putStrLn "a")

end :: t -> t end m = m

main = begin a a a a a a a a a a a a a a a a a a end }}} takes about a second to type check in ghc 7.8, and is "instant" in 7.6 ()

each additional a doubles the time to type check the program

{{{ main = begin a a a a a a a a a a a a a a a a a a a a a a a a end }}}

takes longer than I have the patience to wait :) (so more than 5 seconds)

the author of the email notes that a related program

{{{ main = id id id id id id id id id id id id id id id id id id id id id id (return ()) }}} has the exponential complexity in both 7.8.2 and 7.6.2

This It could very well be that some of the type checker changes between 7.8 and 7.6 enlarged the space of programs that trip up exponential worst case behavior, but one way or another understanding *why* this happened

New description: it was recently demonstrated on the haskell-cafe mailing list that the following code takes measurably longer to type check in GHC 7.8.2 than in GHC 7.6. http://www.haskell.org/pipermail/haskell-cafe/2014-June/114562.html the program example is as follows {{{#!hs begin :: Monad m => (m () -> t) -> t begin cont = cont (return ()) a :: IO a -> (IO () -> t) -> t a m cont = cont (m >> putStrLn "a") end :: t -> t end m = m main = begin a a a a a a a a a a a a a a a a a a end }}} takes about a second to type check in ghc 7.8, and is "instant" in 7.6 () each additional a doubles the time to type check the program {{{#!hs main = begin a a a a a a a a a a a a a a a a a a a a a a a a end }}} takes longer than I have the patience to wait :) (so more than 5 seconds) the author of the email notes that a related program {{{#!hs main = id id id id id id id id id id id id id id id id id id id id id id (return ()) }}} has the exponential complexity in both 7.8.2 and 7.6.2 This It could very well be that some of the type checker changes between 7.8 and 7.6 enlarged the space of programs that trip up exponential worst case behavior, but one way or another understanding *why* this happened -- Comment: This won't be fixed for 8.0.1. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9198#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9198: large performance regression in type checker speed in 7.8 -------------------------------------+------------------------------------- Reporter: carter | Owner: Type: bug | Status: new Priority: high | Milestone: 8.2.1 Component: Compiler (Type | Version: 7.8.2 checker) | Resolution: | 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: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * cc: RyanGlScott (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9198#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9198: large performance regression in type checker speed in 7.8 -------------------------------------+------------------------------------- Reporter: carter | Owner: (none) Type: bug | Status: new Priority: high | Milestone: Research Component: Compiler (Type | needed checker) | Version: 7.8.2 Resolution: | 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: | -------------------------------------+------------------------------------- Changes (by bgamari): * milestone: 8.4.1 => Research needed -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9198#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler