[GHC] #12191: 7% allocation regression in Haddock performance tests

[GHC]

#12191: 7% allocation regression in Haddock performance tests
-------------------------------------+-------------------------------------
        Reporter:  bgamari           |                Owner:  niteria
            Type:  task              |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  8.0.1
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:  #10482            |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by niteria):

 So what's happening in `checkFamInstConsistency` is suboptimal in multiple
 ways:

 1) The algorithm itself is quadratic. It checks every module against every
 other module. It appears to me that the same thing can be done in a linear
 way by maintaining a consistent env of family instances so far and fold
 adding there when possible or reporting an error.

 2) `checkFamInstConsistency` in Haddock appears to be called for every
 module (Haddock is equivalent to `--make`, right?) which is redundant and
 in principle could be done at the very end once.

 3) determining what pairs to compare uses `Set ModulePair`. After my
 change `Ord ModulePair` is linear. The size of the set is quadratic.
 Furthermore the `Ord ModulePair` doesn't cache its canonicalization.

 4) given these there still appear to be better and worse orders for the
 `ModulePair`s. I don't really know why.

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