[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 goldfire):

 Sorry, still confused. :(

 How are `coercionKind` and `coercionRole` ''mutually'' recursive? I see
 that `coercionRole` calls `coercionKind` but not the other way around.

 But you're right that I'm trying to understand better why there's a
 performance improvement in this patch (even before any caching). In the
 nested `NthCo` case, I'm pretty sure your refactor would be worse. But in
 the test case at hand (which I assume doesn't have nested `NthCo`s --
 haven't looked), your change is clearly an improvement.

 However, I don't think your analysis above is really the problem. I would
 expect that the running time of `coercionKind` or `coercionRole` on nested
 `NthCo`s to be linear in the sum of the `d`s -- that is, we'll have to add
 together all the indices. You've shown above that the old recursion
 pattern (from `coercionKindRole`) traverses down the linked list twice
 (once in `getNth` and once in `nthRole`), but this shouldn't change
 asymptotic complexity. And, usually, `d` is quite small, and so I wouldn't
 expect this to show up at all, really. I still don't think we've quite
 gotten to the bottom of why separating out `coercionKind` and
 `coercionRole` should effect a performance improvement.

 On the other hand, the separated version really is quadratic... and yet
 it's faster (on this test case)! That's the conundrum.

 Please don't let my nit-picking slow you down or discourage you. It's just
 that I think you've hit something quite interesting, and, well, I'm
 interested. :)

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