[GHC] #7258: Compiling DynFlags is jolly slow

[GHC]

#7258: Compiling DynFlags is jolly slow
-------------------------------------+-------------------------------------
        Reporter:  simonpj           |                Owner:  simonpj
            Type:  bug               |               Status:  new
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:  7.6.1
      Resolution:                    |             Keywords:  deriving-perf
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by tdammers):

 This commit:

 http://git.haskell.org/ghc.git/commitdiff/19a2ba3ea436b60466fc4022f53a6631e41b87a5

 ...reduces complexity in register allocation spilling from quadratic to
 logarithmic. The old version would run a carthesian product on the list of
 allocated registers (`assig`) and the list of registers to `keep`; the new
 version uses set operations instead, based on `UniqSet` / `UniqFW`. I've
 also moved things around a little to pre-filter the list of allocations to
 only include the interesting entries in the first place, reducing the
 number of list items from linear to (as far as I can tell) constant.

 I believe there are further optimization opportunities here, such as:

 - changing the current list-based code to also use set/map operations
 - moving the register class check into the `candidates` part
 - precalculating the list of candidates (not sure about this one though)

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