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