diff options
| author | Bartosz Nitka <niteria@gmail.com> | 2015-10-22 15:30:56 +0200 |
|---|---|---|
| committer | Ben Gamari <ben@smart-cactus.org> | 2015-10-22 15:30:57 +0200 |
| commit | 9cb192ce4b34a472041010df9c30f5d741eb0261 (patch) | |
| tree | 9a4630221bd520877770be3e021b3c8b428f07d1 /testsuite/tests/determinism | |
| parent | 0499aa7ce68819f72faafdaacda6831ede1ab616 (diff) | |
| download | haskell-9cb192ce4b34a472041010df9c30f5d741eb0261.tar.gz | |
Make stronglyConnCompFromEdgedVertices deterministic
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
Diffstat (limited to 'testsuite/tests/determinism')
| -rw-r--r-- | testsuite/tests/determinism/Makefile | 3 | ||||
| -rw-r--r-- | testsuite/tests/determinism/all.T | 3 | ||||
| -rw-r--r-- | testsuite/tests/determinism/determinism001.hs | 23 | ||||
| -rw-r--r-- | testsuite/tests/determinism/determinism001.stdout | 4 |
4 files changed, 33 insertions, 0 deletions
diff --git a/testsuite/tests/determinism/Makefile b/testsuite/tests/determinism/Makefile new file mode 100644 index 0000000000..9a36a1c5fe --- /dev/null +++ b/testsuite/tests/determinism/Makefile @@ -0,0 +1,3 @@ +TOP=../.. +include $(TOP)/mk/boilerplate.mk +include $(TOP)/mk/test.mk diff --git a/testsuite/tests/determinism/all.T b/testsuite/tests/determinism/all.T new file mode 100644 index 0000000000..3d4ff2010d --- /dev/null +++ b/testsuite/tests/determinism/all.T @@ -0,0 +1,3 @@ +setTestOpts(extra_hc_opts('-package ghc')) + +test('determinism001', normal, compile_and_run, ['']) diff --git a/testsuite/tests/determinism/determinism001.hs b/testsuite/tests/determinism/determinism001.hs new file mode 100644 index 0000000000..7d1c5896df --- /dev/null +++ b/testsuite/tests/determinism/determinism001.hs @@ -0,0 +1,23 @@ +module Main where + +import Digraph + +main = mapM_ print + [ test001 + , test002 + , test003 + , test004 + ] + +-- These check that the result of SCCs doesn't depend on the order of the key +-- type (Int here). + +test001 = testSCC [("a", 1, []), ("b", 2, []), ("c", 3, [])] + +test002 = testSCC [("a", 2, []), ("b", 3, []), ("c", 1, [])] + +test003 = testSCC [("b", 1, []), ("c", 2, []), ("a", 3, [])] + +test004 = testSCC [("b", 2, []), ("c", 3, []), ("a", 1, [])] + +testSCC = flattenSCCs . stronglyConnCompFromEdgedVertices diff --git a/testsuite/tests/determinism/determinism001.stdout b/testsuite/tests/determinism/determinism001.stdout new file mode 100644 index 0000000000..c94a1fe80b --- /dev/null +++ b/testsuite/tests/determinism/determinism001.stdout @@ -0,0 +1,4 @@ +["c","b","a"] +["c","b","a"] +["a","c","b"] +["a","c","b"] |