#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/19a2ba3ea436b60466fc4022f53a6631e4...
...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