[GHC] #13253: Exponential compilation time with RWST & ReaderT stack with `-02`

[GHC]

#13253: Exponential compilation time with RWST & ReaderT stack with `-02`
-------------------------------------+-------------------------------------
        Reporter:  phadej            |                Owner:  dfeuer
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.4.1
       Component:  Compiler          |              Version:  8.0.1
      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:                    |
-------------------------------------+-------------------------------------

Comment (by mpickering):

 I think this is what happens but I've sinced paged out the details.

 We start with `((FormSuccess f <*> x0) <*> x1)`

 You have

 {{{
 ((FormSuccess f <*> x0) <*> x1) <*> x2
 =>
 ((<*>) (FormSuccess f) x0) <*> x1 <*> x2
 => (Inline (<*>))
  (case x0 of {
                   FormMissing -> FormMissing;
                   FormFailure errs_a2dS -> FormFailure errs_a2dS;
                   FormSuccess a_a2dU -> FormSuccess ...;
                 }) <*> x1 <*> x2
 => (prefixify)
 ((<*>) (case x0 of {
                   FormMissing -> FormMissing;
                   FormFailure errs_a2dS -> FormFailure errs_a2dS;
                   FormSuccess a_a2dU -> FormSuccess ...;
                 }) x1) <*> x2
 => (StrictArg)
 (case x0 of {
                   FormMissing -> (<*>) FormMissing x1;
                   FormFailure errs_a2dS -> (<*>) (FormFailure errs_a2dS)
 x1;
                   FormSuccess a_a2dU -> (<*>) (FormSuccess ...) x1     ;
                 }) <*> x2
 => (Inline)

 (case x0 of {
                   FormMissing -> (case x1...)
                   FormFailure errs_a2dS -> case x1....
                   FormSuccess a_a2dU -> case x1...     ;
                 }) <*> x2

 => (Strict arg for x2)
 (case x0 of {
                   FormMissing -> (<*>) (case x1...) x2;
                   FormFailure errs_a2dS -> (<*>) (case x1...) x2;
                   FormSuccess a_a2dU -> (<*>) (case x1...) x2     ;
                 })
 => (Strict arg fires again pushing the <*> into the inner cases and now we
 have 9 copies of (<*>).
 }}}

 Does that sound plausible?

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