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

12 Jan 2018

      #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 simonpj):

 Ah, yes I think you may be on to something.
 Suppose we have
 {{{
 case2 (case1 e of
        True -> e1
        False -> e2) of
    True -> r1
    False -> r2
 }}}
 and suppose that `r1` and `r2` are small.  (If they aren't they get bound
 as join points.)
 I've put numbers on the `case1` and `case2` so we can talk about them, but
 they are just ordinary Core `case` expressions.

 Then we push the outer `case2` into the right hand sides of `case1` thus
 {{{
 case1 e of
   True -> case2 e1 of
             True -> r1
             False -> r2
   False -> case2 e2 of
             True -> r1
             False -> r2
 }}}
 We have (by design) duplicated outer `case2`.

 Now suppose that entire expression E was surrounded by `case3 E of { True
 -> s1; False -> s2 }`.
 Again `s1` and `s2` are small. Then we'll duplicate that into alternatives
 of `case1` and then into the alternatives of `case2`, to get this
 {{{
 case1 e of
   True -> case2 e1 of
             True  -> case3 r1 of { True -> s2; False -> s2 }
             False -> case3 r2 of { True -> s2; False -> s2 }
   False -> case2 e2 of
             True  -> case3 r1 of { True -> s2; False -> s2 }
             False -> case3 r2 of { True -> s2; False -> s2 }
 }}}
 Now we have four copies of `case3`.  You can see how this may go
 exponential.

 How can we get these deepyly nested cases?  Suppose
 {{{
 f x = case x of { True -> e1; False -> e2 }
 }}}
 and we have `f (f (f (f (f (f blah)))))`.  If we inline `f` we'll get
 exactly such a deep nest of cases.

 Here is a concrete example
 {{{
 f :: Int -> Bool -> Bool
 {-# INLINE f #-}
 f y x = case x of { True -> y>0 ; False -> y<0 }

 foo y x = f (y+1) $
           f (y+2) $
           f (y+3) $
           f (y+4) $
           f (y+5) $
           f (y+6) $
           f (y+7) $
           f (y+8) $
           f (y+9) $
           f y x
 }}}
 Sure enough, adding one more line to `foo` doubles the size of the
 optimised code.
 And this is very similar to the chain of `<*>` applications that seems to
 trigger the problem in
 the Description.

 So this looks like the root cause of the problem, which is great progress.
 And now we have a tiny repro case, which is also super-helpful.

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