[GHC] #14683: Slow compile times for Happy-generated source

[GHC]

#14683: Slow compile times for Happy-generated source
-------------------------------------+-------------------------------------
        Reporter:  harpocrates       |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  high              |            Milestone:  8.4.1
       Component:  Compiler          |              Version:  8.2.2
      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:                    |
-------------------------------------+-------------------------------------
Changes (by simonpj):

 * cc: goldfire (added)


Comment:

 > In other words, we're spending close to 90% time and alloc on the
 coercionKind function.

 Ha!  A smoking gun.  Well done!

 Moreover, it's a gun that has fired before: see #5631, and the comment in
 `Coercion/hs`
 {{{
 Note [Nested InstCos]
 ~~~~~~~~~~~~~~~~~~~~~
 In Trac #5631 we found that 70% of the entire compilation time was
 being spent in coercionKind!  The reason was that we had
    (g @ ty1 @ ty2 .. @ ty100)    -- The "@s" are InstCos
 where
    g :: forall a1 a2 .. a100. phi
 If we deal with the InstCos one at a time, we'll do this:
    1.  Find the kind of (g @ ty1 .. @ ty99) : forall a100. phi'
    2.  Substitute phi'[ ty100/a100 ], a single tyvar->type subst
 But this is a *quadratic* algorithm, and the blew up Trac #5631.
 So it's very important to do the substitution simultaneously.

 cf Type.applyTys (which in fact we call here)
 }}}
 But clearly the fix for #5631 isn't solving the current problem.

 Does the profiling info tell us anything about which calls to
 `coercionKind` are so expensive?

 I see two ways forward

 1.  Identify the non-linearity in `coercionKind`. It really should not be
 so expensive.   The fix to #5631 fixed one, but presumably there is
 another.

   It's not immediately obvious how to do this.  One way might be to
 instrument `coercionKind` so that it returns (as well as the kind) the
 number of recursive invocations of `coercionKind` and of `substTy`, and
 then print out coercions that produce big numbers for either of these.

   Alternatively, just fix #11735, and see if that helps.  That's easy to
 do.

 2.  Resurrect #11598.  I have some ideas.

 Actually we might want to do both.  Even if we did (2) it'd just cover up
 badness in (1).

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