[GHC] #12724: Be lazier about reducing type-function applications

[GHC]

#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