[GHC] #14263: typeKind is quadratic

[GHC]

#14263: typeKind is quadratic
-------------------------------------+-------------------------------------
           Reporter:  goldfire       |             Owner:  (none)
               Type:  task           |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.2.1
           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:
-------------------------------------+-------------------------------------
 While pondering Phab:D3998, I realized that any computation of a type's
 kind should be careful in the presence of nested `AppTy`s. And, to my
 horror, I realized that GHC's very own `typeKind` isn't! That is, if you
 have the type `a b c d e`, GHC will take a quadratic (or worse -- haven't
 benchmarked) amount of time computing its kind.

 This can be easily fixed by looking for nested `AppTy`s and using
 `piResultTys`, instead of repeated uses of `piResultTy` (as is currently
 done).

 NB: This was not discovered through witnessing poor performance, but it
 does seem like very low-hanging compiler-performance fruit.

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