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

[GHC]

#15938: Hadrian's recompilation check is extremely slow
-------------------------------------+-------------------------------------
        Reporter:  bgamari           |                Owner:  alpmestan
            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):

 I investigated further, the issue is that adding a user rule match is
 ''O(n)'', so adding ''n'' rules is ''O(n^2^)''. I have raised a ticket to
 fix that at https://github.com/ndmitchell/shake/issues/632, so in time the
 construction in Hadrian might become efficient. But I still recommend
 fixing it since it's better to not enumerate all the possible paths in
 advance.

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