[GHC] #9198: large performance regression in type checker speed in 7.8

[GHC]

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

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