#12724: Be lazier about reducing type-function applications -------------------------------------+------------------------------------- Reporter: simonpj | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.0.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): Here is the basic idea we had: keep `CFunEqCan`s in a lower-priority wing of the work-list, and then solve them only when necessary. When we see a type function application like `F 20` in a type, we ''flatten'' it to produce a flatten-unification-variable, fuv, and a constraint `[W] F 20 ~ fuv`. It is this constraint that would be de- prioritized. If the program can be type-checked without ever solving the `CFunEqCan`, then we do not need to reduce the type function. When a `CFunEqCan` comes up as the work item, we try to solve it only if it is ''active''. An ''active'' `CFunEqCan` involves an fuv that: 1. Is an argument to the class in an inert class constraint, OR 2. Is an argument to the type family in an active `CFunEqCan`, OR 3. Is at the top level of an inert equality If a `CFunEqCan` is not active (that is, if it's ''passive''), then just throw it right into the inert set without trying to solve. The inert set will have a new place to store passive `CFunEqCan`s; if it were to become active (by one of the conditions above becoming satisfied), then it must get kicked out. We think that an efficient way of implementing this scheme is by reference counting, essentially, where each fuv is mapped (in some data structure in the `TcSEnv`) to a count of places where it is active. When the count drops to zero, the associated `CFunEqCan` becomes passive. We would then have to increment and decrement counters when adding to and kicking out from the inert set. Note that we have to be careful to making the refcount wibbles as efficient as possible, because they will happen a lot. For example, we can't just get the free variables of a constraint and then look for fuvs, as that would allocate space to store the fv set. Instead, we must write a new function that extracts only fuvs. It remains to be seen if this will be a real performance improvement, as there will be a cost everyone has to pay to speed up the type family case. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/12724#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler