#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 ):
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
