[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 heisenbug):

 Replying to [comment:33 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.

 Hmmm, what do you think about having the cartesian product for a smaller
 cut-off size? Manipulating the sets surely also has a (large) constant
 factor built-in.

 >
 > 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:35>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler