[GHC] #14263: typeKind is quadratic
#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
#14263: typeKind is quadratic -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): I have often wondered if it wouldn't be better to change `Type`s concrete representation to avoid this kind of problem structurally. To wit: {{{#!hs data Type = TyVarTy TyVar | TyConTy TyCon | AppTys Type [Type] -- INVARIANT 1: List is not empty. -- INVARIANT 2: The head type is not an AppTys | ForAllTy ... | LitTy ... | CastTy ... | CoercionTy ... }}} Note that INVARIANT 1 is needed to avoid confusion between, e.g., `AppTys (TyVarTy a) []` and `TyVarTy a`. We could perhaps do even better using `Seq Type` instead of `[Type]` as the container in `AppTys`, given that we sometimes need access to both ends. It might be an interesting experiment to see if performance improves with this change. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14263#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14263: typeKind is quadratic -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): I agree with comment:1. Worth a try. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14263#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14263: typeKind is quadratic -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by RyanGlScott): * cc: RyanGlScott (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14263#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14263: typeKind is quadratic -------------------------------------+------------------------------------- Reporter: goldfire | Owner: dfeuer Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * owner: (none) => dfeuer -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14263#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14263: typeKind is quadratic -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by dfeuer): * owner: dfeuer => (none) Comment: I'm told this shouldn't be a priority for me at the moment, so I'll release it for now. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14263#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14263: typeKind is quadratic -------------------------------------+------------------------------------- Reporter: goldfire | Owner: simonpj Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * owner: (none) => simonpj Comment: I'm on this -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14263#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14263: typeKind is quadratic
-------------------------------------+-------------------------------------
Reporter: goldfire | Owner: simonpj
Type: task | Status: new
Priority: normal | Milestone:
Component: Compiler | Version: 8.2.1
Resolution: | Keywords:
Operating System: Unknown/Multiple | Architecture:
| Unknown/Multiple
Type of failure: None/Unknown | Test Case:
Blocked By: | Blocking:
Related Tickets: | Differential Rev(s):
Wiki Page: |
-------------------------------------+-------------------------------------
Comment (by Simon Peyton Jones
#14263: typeKind is quadratic -------------------------------------+------------------------------------- Reporter: goldfire | Owner: simonpj Type: task | Status: closed Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * status: new => closed * resolution: => fixed -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14263#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#14263: typeKind is quadratic -------------------------------------+------------------------------------- Reporter: goldfire | Owner: simonpj Type: task | Status: closed Priority: normal | Milestone: 8.6.1 Component: Compiler | Version: 8.2.1 Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by bgamari): * milestone: => 8.6.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14263#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (1)
-
GHC