[GHC] #11602: Exponential behaviour in typeKind, unifyTys etc

[GHC]

#11602: Exponential behaviour in typeKind, unifyTys etc
-------------------------------------+-------------------------------------
           Reporter:  simonpj        |             Owner:
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  7.10.3
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 In Trac #11371 Bartosz found some very suspicious performance behaviour.
 Specifically:

 * See comment 42 of #11371, which says that `liftCoMatch` and
 `promoteCoercion` is responsible for a significant fraction of all
 compiler allocation.  Why so expensive?  Especially since only used from
 `OptCoercion`.

 * There are two comments in `Unify` saying
 {{{
 ty_co_match_app menv subst ty1a ty1b co2a co2b
   = do { -- TODO (RAE): Remove this exponential behavior.
          subst1 <- ty_co_match menv subst  ki1a ki2a ki_ki_co ki_ki_co
 }}}
 and
 {{{
 unify_ty_app ty1a ty1b ty2a ty2b
   = do { -- TODO (RAE): Remove this exponential behavior.
          let ki1a = typeKind ty1a
              ki2a = typeKind ty2a
        ; unify_ty ki1a ki2a (mkNomReflCo liftedTypeKind)
 }}}
   NB: `ty_co_match_app` is also called from `liftCoMatch`.

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