#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