[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:  (none)
            Type:  bug               |               Status:  new
        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):
       Wiki Page:                    |
-------------------------------------+-------------------------------------

Comment (by Bartosz Nitka <niteria@…>):

 In [changeset:"cf2c029ccdb967441c85ffb66073974fbdb20c20/ghc"
 cf2c029c/ghc]:
 {{{
 #!CommitTicketReference repository="ghc"
 revision="cf2c029ccdb967441c85ffb66073974fbdb20c20"
 Fix quadratic behavior of prepareAlts

 Summary:
 This code is quadratic and a simple test case I used
 managed to tickle it.

 The example (same one as #14667) looks like this:
 ```
 module A10000 where

  data A = A
    | A00001
    | A00002
  ...
    | A10000

  f :: A -> Int
  f A00001 = 19900001
  f A00002 = 19900002
  ...
  f A10000 = 19910000
 ```

 Applied on top of a fix for #14667, it gives a 30% compile time
 improvement.

 Test Plan: ./validate

 Reviewers: simonpj, bgamari

 Subscribers: rwbarton, thomie, simonmar, carter

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

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