Use IntSet in Dataflow

Authored by niteria on Jan 20 2018, 12:24 PM.



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


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

Diff Detail

rGHC Glasgow Haskell Compiler
Automatic diff as part of commit; lint not applicable.
Automatic diff as part of commit; unit tests not applicable.
niteria created this revision.Jan 20 2018, 12:24 PM
niteria updated this revision to Diff 15163.Jan 20 2018, 12:30 PM

remove outdated comment

bgamari accepted this revision.Jan 21 2018, 11:05 AM

Looks good to me.

This revision is now accepted and ready to land.Jan 21 2018, 11:05 AM
This revision was automatically updated to reflect the committed changes.

Looks fine to me. Eliminating bad corner cases is good. Thanks