[GHC] #11735: Optimize coercionKind

[GHC]

#11735: Optimize coercionKind
-------------------------------------+-------------------------------------
        Reporter:  goldfire          |                Owner:  (none)
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  7.10.3
      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:                    |
-------------------------------------+-------------------------------------

Comment (by tdammers):

 Replying to [comment:38 goldfire]:
 > I'm sorry -- I don't understand the first part of comment:37. Getting a
 kind should never require getting a role. That's why there is a version of
 `coercionKind` that's a standalone function. Let's assume you got these
 two swapped. Even then, I'm not sure what you're describing; it seems
 you're describing your 'un-refactored" version keeping roles and kinds
 separate.

 I'm sorry, yes, I was being confused there; `coercionKind` and
 `coercionRole` are mutually recursive in the "un-refactored" version only.
 However, the un-refactoring *does* produce a performance improvement, so
 there must be *something* going on here - I assumed that the original
 `coercionKindRole` would ultimately amount to a similar recursion pattern,
 but it probably doesn't.

 > If they are together (as in HEAD), I don't see the quadratic behavior.
 > And yet, something goes terribly wrong in HEAD, even without this
 quadratic behavior. But what?? Or maybe I'm completely missing something
 here.

 I think I have found it. For clarity, this is the relevant code on HEAD:

 {{{
     go (NthCo d co)
       | Just (tv1, _) <- splitForAllTy_maybe ty1
       = ASSERT( d == 0 )
         let (tv2, _) = splitForAllTy ty2 in
         (tyVarKind <$> Pair tv1 tv2, Nominal)

       | otherwise
       = let (tc1,  args1) = splitTyConApp ty1
             (_tc2, args2) = splitTyConApp ty2
         in
         ASSERT2( tc1 == _tc2, ppr d $$ ppr tc1 $$ ppr _tc2 )
         ((`getNth` d) <$> Pair args1 args2, nthRole r tc1 d)

       where
         (Pair ty1 ty2, r) = go co
 }}}

 So the rough shape of the recursion is simple - we hit the `otherwise`
 case repeatedly until we get to the `d == 0` case; O(n). But inside the
 `otherwise` branch, there's this pesky `getNth` call, which is linear in
 `d` (being essentially a linked-list lookup), and another one via
 `nthRole`.

 The problem goes away when we calculate the role at construction time,
 because we are either constructing an NthCo that doesn't wrap another
 NthCo, which makes the role calculation constant-time, or we are
 constructing one that *does* wrap another NthCo, but that one already has
 its role calculated, so it is also constant.

 Hope I'm making sense now.

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