[GHC] #15938: Hadrian's recompilation check is extremely slow

[GHC]

#15938: Hadrian's recompilation check is extremely slow
-------------------------------------+-------------------------------------
        Reporter:  bgamari           |                Owner:  (none)
            Type:  bug               |               Status:  new
        Priority:  high              |            Milestone:  8.8.1
       Component:  Build System      |              Version:  8.6.2
  (Hadrian)                          |
      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 NeilMitchell):

 If you are spending all the time in file pattern matching, I'd say that's
 a strong suggestion you are doing a lot more file pattern matching that is
 desirable. Yes, it could be faster, but in a normal build system I'd
 expect it to be in the weeds - less than 1%.

 The real culprit though is almost certainly TypeMap.unionWith, which
 corresponds to adding a user rule during startup (e.g. with %>). In a
 normal build system I'd expect perhaps 100 user rules. If you want to
 match on a million rules you have, you put them in a dictionary yourself
 and add a predicate rule. My guess is Hadrian probably has a list and
 unrolls it into Shake one at a time. Once you have a huge number of user
 rules, and match on each linearly, you become quadratic in a huge number.

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