[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 Ben Gamari <ben@…>):

 In [changeset:"df636682f3b8299268d189bfaf6de1d672c19a73/ghc"
 df636682/ghc]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="df636682f3b8299268d189bfaf6de1d672c19a73"
 Performance improvements linear regAlloc (#7258)

 When allocating and potentially spilling registers, we need to check
 the desired allocations against current allocations to decide where we
 can spill to, cq. which allocations we can toss and if so, how.
 Previously, this was done by walking the Cartesian product of the
 current allocations (`assig`) and the allocations to keep (`keep`),
 which has quadratic complexity. This patch introduces two improvements:

 1. pre-filter the `assig` list, because we are only interested in two
 types of allocations (in register, and in register+memory), which will
 only make up a small and constant portion of the list; and
 2. use set / map operations instead of lists, which reduces algorithmic
 complexity.

 Reviewers: austin, bgamari

 Reviewed By: bgamari

 Subscribers: rwbarton, thomie

 Differential Revision: https://phabricator.haskell.org/D4109
 }}}

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