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

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

 Could be worth it, but I'm a bit skeptical - the additional overhead of
 unpacking the sets into lists could easily cancel out the performance
 benefit, and it would make the code more complicated. I'll give it a try
 though.

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