#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