#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