#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