[GHC] #14667: Compiling a function with a lot of alternatives bottlenecks on insertIntHeap

[GHC]

#14667: Compiling a function with a lot of alternatives bottlenecks on
insertIntHeap
-------------------------------------+-------------------------------------
        Reporter:  niteria           |                Owner:  niteria
            Type:  bug               |               Status:  patch
        Priority:  normal            |            Milestone:
       Component:  Compiler          |              Version:
      Resolution:                    |             Keywords:
Operating System:  Unknown/Multiple  |         Architecture:
 Type of failure:  Compile-time      |  Unknown/Multiple
  performance bug                    |            Test Case:
      Blocked By:                    |             Blocking:
 Related Tickets:                    |  Differential Rev(s):  phab:D4329
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by Ben Gamari <ben@…>):

 In [changeset:"88297438d550a93f72261447a215b6a58b4fae55/ghc"
 88297438/ghc]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="88297438d550a93f72261447a215b6a58b4fae55"
 Use IntSet in Dataflow

 Before this change, a list was used as a substitute for a heap.
 This led to quadratic behavior on a simple program (see new
 test case).

 This change replaces it with IntSet in effect reverting
 5a1a2633553. @simonmar said it's fine to revert as long as nofib
 results are good.

 Test Plan:
 new test case:

 20% improvement
 3x improvement when N=10000

 nofib:

 I run it twice for before and after because the compile time
 results are noisy.

 - Compile Allocations:

 ```
           before    before re-run    after     after re-run
 -1 s.d.   -----     -0.0%            -0.1%     -0.1%
 +1 s.d.   -----     +0.0%            +0.1%     +0.1%
 Average   -----     +0.0%            -0.0%     -0.0%
 ```
 - Compile Time:

 ```
           before    before re-run    after     after re-run
 -1 s.d.   -----     -0.1%            -2.3%     -2.6%
 +1 s.d.   -----     +5.2%            +3.7%     +4.4%
 Average   -----     +2.5%            +0.7%     +0.8%

 ```
 I checked each case and couldn't find consistent slow-down/speed-up on
 compile time. Full results here: P173

 Reviewers: simonpj, simonmar, bgamari

 Reviewed By: bgamari

 Subscribers: rwbarton, thomie, carter, simonmar

 GHC Trac Issues: #14667

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

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