[GHC] #7258: Compiling DynFlags is jolly slow

[GHC]

#7258: Compiling DynFlags is jolly slow
-------------------------------------+-------------------------------------
        Reporter:  simonpj           |                Owner:  simonpj
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  7.6.1
      Resolution:                    |             Keywords:  deriving-perf
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 tdammers):

 Replying to [comment:88 simonpj]:
 > Hmm. The `Cmm` for `g10` is actually a lot bigger than that for `f10`,
 and looked to me as if it too would scale quadratically.

 It would, but for different reasons, and I believe I can rewrite it to not
 scale quadratically (but haven't gotten around to it yet).

 >  Are `f10` and `g10` accurate reflections of the "scale well" and "scale
 badly" versions of Read?

 No; we don't actually have a "scale well" version of `Read` yet. All the
 implementations of `Read` that I have produced so far are in the "scale
 badly" category, although the degree to which they scale badly differs
 somewhat. We have two kinds of "scale well" examples:

 1. Trivial ones, where rather than nest code such that chains of closures
 appear, we just call `read` or something else N times, but in benign ways;
 these examples do not have much of an explanatory value, and I merely
 included them to establish a performance baseline
 2. Well-behaved nested / chained examples, such as the `getline-appl` one;
 however, none of these do anything equivalent to `read`.

 >
 > I can see why things might scale badly, if we have a lot of
 > {{{
 > p1 >>= \x ->
 > p2 >>= \y ->
 > p3 >>= \z ->
 > return (K x y z)
 > }}}
 > And `f10` has that structure, albeit with data constructors rather than
 functions.  BUT: if that's it, why doesn't `(>>=)` inline, so we get a
 case expression instead??

 I believe the `(>>=)` does in fact inline; `f10` is the kind of shape you
 get when you inline the `(>>=)` from `ReadP`. `(>>=)` from other monadic
 types does not introduce this kind of shape, which would explain why
 `Read` misbehaves but `getLine` over `IO` does not.

 >
 > So if `f10` is reasonably accurate, I can see two ways forward:
 >
 > 1 Do something in the back end to generate less code.
 >
 > 2 Generate different code.  I'm still intrigued (and a bit disbelieving)
 why a different exposition of Read generates code that scales better.

 See above; `Read` always misbehaves here, so your disbelief is entirely
 justified. The bad behavior seems to be related to the actual
 implementation of `(>>=)`, not so much whether the `(>>=)` gets inlined.
 Or, more accurately, inlining `(>>=)` actually *is* the problem; if we
 didn't inline it, then `read-appl` would compile to something equivalent
 to the generic applicative example, which behaves nicely.

 > Concerning (1) the kind of thing I had in mind was more like this
 > {{{
 > f10 =
 >   A (\i0 ->
 >   A (\i1 ->
 >   A (\i2 ->
 >   A (\i3 ->
 >   A (\i4 -> let t = (i0,i1,i2,i3,i4) in
 >   A (\i5 ->
 >   A (\i6 ->
 >   A (\i7 ->
 >   A (\i8 ->
 >   A (\i9 ->
 >   case t of (i0,i1,i2,i3,i4) ->
 >      N (i0, i1, i2, i3, i4, i5, i6, i7, i8, i9)
 > }}}
 > Now no function closure gets more than 5 free variables.  I imagine one
 could do this as a STG-to-STG transformation if we decided that this was
 really the core issue.

 Further experimentation shows that this doesn't actually achieve anything;
 the resulting Core is *exactly the same*, and if you put both functions
 into the same compilation unit, they get optimized into expressing one in
 terms of the other (I'm guessing here that CSE is smart enough to figure
 out that they are equivalent). I have written 3 versions of `f10`, one as-
 is, one (`g10`) using the suggested 5-tuple optimization, and one (`h10`)
 using a nested-tuple optimization, and I end up with Core that has
 literally these lines:

 {{{
 f10 = A f1

 g10 = f10

 h10 = f10
 }}}

 > A tantalising point is this.  We have something like this:
 > {{{
 >    let f4 = [i0,i1,i2,i3] \i4 ->
 >             let f5 = [i0,i1,i2,i3, i4] \i5 -> ...blah...
 > }}}
 > The list before the `\` are the free vars of the closure.
 >
 > Inside the code for `f4` we have `f4`'s function closure in hand, with
 `i0...` in it.  Rather than capturing `i0, i1...` as the free vars of f5,
 we could just store a pointer to `f4`'s function closure (it's a kind of
 tuple, after all) and fetch its free vars from there.  It's as if we
 wanted to say
 > {{{
 >    let f4 = [i0,i1,i2,i3] \i4 ->
 >             let f5 = [f4, i4] \i5 -> ...blah...
 > }}}
 > with `f4` and `i4` being the free vars of `f5`'s closure.  This would be
 a deeper change to the code generator, but it could make a lot of sense in
 cases where ''all'' of `f4`'s free variables are also free in `f5`.  (If
 not all where, you might get a space leak by closing over `f4`.)

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