Skip to content
  • niteria's avatar
    Use IntSet in Dataflow · 88297438
    niteria authored and Ben Gamari's avatar Ben Gamari committed
    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
    5a1a2633. @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
    88297438