[GHC] #9872: Runing type functions is too slow

[GHC]

#9872: Runing type functions is too slow
-------------------------------------+-------------------------------------
              Reporter:  simonpj     |            Owner:
                  Type:  bug         |           Status:  new
              Priority:  normal      |        Milestone:
             Component:  Compiler    |          Version:  7.8.3
            Resolution:              |         Keywords:
      Operating System:              |     Architecture:  Unknown/Multiple
  Unknown/Multiple                   |       Difficulty:  Unknown
       Type of failure:              |       Blocked By:
  None/Unknown                       |  Related Tickets:
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by simonpj):

 Some diagnosis:

  * 90%+ of compile time is being spent in `TrieMap` code, called from
 `partitionFunEqs`, called from `kick_out` in the constraint solver.  Here
 are the top cost centres in a profiled compiler.
 {{{
 COST CENTRE    MODULE    %time %alloc

 fdT            TrieMap    36.7   44.8
 fdList         TrieMap    13.4   16.8
 foldTyLit      TrieMap    10.9   17.2
 fdVar          TrieMap     8.2   11.1
 foldMaybe      TrieMap     3.7    1.3
 foldUFM        UniqFM      3.7    1.5
 lm_nil         TrieMap     2.3    0.0
 lm_cons        TrieMap     1.9    0.0
 mapUnionVarSet VarSet      1.5    1.1
 tlm_string     TrieMap     1.2    0.0
 foldTM         TrieMap     1.1    0.7
 }}}

  * The inert set has up to 150 inert `CFunEqCans`.  That's absurd. I think
 I know how to reduce it dramatically by improving the order in which goals
 are solved.

  * Each call to `kick_out` requires us to look at each of the 150 inert
 items, in case it mentions the newly-assigned variable. (This is already
 quadratic, hence wanting to minimise the size of the inert
 set.)[[BR]][[BR]]
    But `partitionFunEqs` '''still''' should not be so expensive.   Part of
 the reason turned out to be the use of a `TrieMap`.  Suppose a `TrieMap`
 has exactly one item in it, with a big key, like `A (K C D E F) (K E D C
 F)` etc.  Then the `TrieMap` will have a long string of singleton UFMs etc
 to represent it.  That's not a very clever representation; simply to
 reconstruct a copy takes time proportional to the size of the
 key.[[BR]][[BR]]
   I think the solution may be to give `TrieMaps` a special case for
 singleton maps, which does not invert the kay.

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