[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:  bgamari, osa1
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:  8.8.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:  #15630            |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by tdammers):

 I've instrumented GHC to dump more intermediate information during
 SpecConstr. Specifically, I've added the following logic:

 In `scExpr`, capture the expression to be specialized before and after
 specialization; then compare number of terms to detect a blowup (a factor
 of 2 is enough to weed out the non-blowups), and if this particular
 incantation does in fact blow up, dump the expression before the blowup.

 The resulting dump is a bit too large to attach, but it shows a typical
 pattern: the expressions that blow up all look very much alike; as we
 progress through the compilation, the "before" size stays at ~6000 terms,
 while the "after" size progressively increases, and it looks like
 expressions from earlier incantations get inlined into expressions later
 in the process.

 Which fits the hypothesis from the GHC HQ meeting, namely, that the
 inlining heuristic only looks at the size of the inlinee, but not at the
 inlining context, so when something gets inlined "top-down", then
 functions to be inlined (which don't have their own dependencies inlined
 yet) are all still small, and so the inliner happily copies them many
 times, and then in the next round, it inlines exponentially more
 invocations of the inlined functions' dependencies, and so on.

 For example, given:

 {{{#!haskell
 f = g1 + g2 + g3 + g4 + g5

 g1 = a1 + a2 + a3 + a4

 g2 = b1 + b2 + b3 + b4

 ...
 }}}

 ...the inlining heuristic will first look at `f`, conclude that each of
 `g1` through `g5` is small, and can thus be inlined; then after inlining,
 it will look at f again, and conclude that each of `a1` etc. is small, and
 inline those; and if those have further dependencies following the same
 matter, it will happily keep inlining all those small things, not
 realizing that it is creating a monstrosity. And because all the inlinees
 involved are different, there will not be any opportunities for
 optimizations that might shrink things back down, so the resulting program
 just keeps growing exponentially.

 One fun thing I'll try now is this:

 Considering that I already have code in place to detect blowups, I can
 trivially use this logic to just say "if this blows up, then throw away
 the specialized Core, and use the original expression instead". So I'll
 try that, and see what that does to various performance metrics.

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