From 9cb192ce4b34a472041010df9c30f5d741eb0261 Mon Sep 17 00:00:00 2001 From: Bartosz Nitka Date: Thu, 22 Oct 2015 15:30:56 +0200 Subject: 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 --- testsuite/tests/determinism/Makefile | 3 +++ testsuite/tests/determinism/all.T | 3 +++ testsuite/tests/determinism/determinism001.hs | 23 +++++++++++++++++++++++ testsuite/tests/determinism/determinism001.stdout | 4 ++++ 4 files changed, 33 insertions(+) create mode 100644 testsuite/tests/determinism/Makefile create mode 100644 testsuite/tests/determinism/all.T create mode 100644 testsuite/tests/determinism/determinism001.hs create mode 100644 testsuite/tests/determinism/determinism001.stdout (limited to 'testsuite/tests/determinism') 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"] -- cgit v1.2.1