Skip to content
  • niteria's avatar
    Make stronglyConnCompFromEdgedVertices deterministic · 9cb192ce
    niteria authored and Ben Gamari's avatar Ben Gamari committed
    This makes it so the result of computing SCC's depends on the order
    the nodes were passed to it, but not on the order on the user provided
    key type.
    The key type is usually `Unique` which is known to be nondeterministic.
    
    Test Plan:
    `text` and `aeson` become deterministic after this
    ./validate
    
    Compare compile time for `text`:
    ```
    $ cabal get text && cd text* && cabal sandbox init && cabal install
    --dependencies-only && time cabal build
    real    0m59.459s
    user    0m57.862s
    sys     0m1.185s
    $ cabal clean && time cabal build
    real    1m0.037s
    user    0m58.350s
    sys     0m1.199s
    $ cabal clean && time cabal build
    real    0m57.634s
    user    0m56.118s
    sys     0m1.202s
    $ cabal get text && cd text* && cabal sandbox init && cabal install
    --dependencies-only && time cabal build
    real    0m59.867s
    user    0m58.176s
    sys     0m1.188s
    $ cabal clean && time cabal build
    real    1m0.157s
    user    0m58.622s
    sys     0m1.177s
    $ cabal clean && time cabal build
    real    1m0.950s
    user    0m59.397s
    sys     0m1.083s
    ```
    
    Reviewers: ezyang, simonmar, austin, bgamari
    
    Reviewed By: simonmar, bgamari
    
    Subscribers: thomie
    
    Differential Revision: https://phabricator.haskell.org/D1268
    
    GHC Trac Issues: #4012
    9cb192ce