Resolving dependencies for wai repo on GHC 7.6.3 times out with Travis

[snoyberg]

We have regular build failures on the wai repo due to the build timing out, e.g. https://travis-ci.org/yesodweb/wai/jobs/132019472. I don't know if there is legitimately no build plan, or if the solver is simply having difficulty finding one. I've kicked off some dependency solving on one of my servers to try to determine if there's a workaround. Nonetheless, taking over 10 minutes to solve dependencies is surprising.

Reproduction:

• Tested with GHC 7.6.3 on Linux
• Tested with cabal-install 1.16, 1.22, and 1.24
• Check out the wai repo at commit c9427c887a40dbc35b6f4cca58f5096cd0a1b6e4 to the directory /home/travis/build/yesodweb/wai
• Run the following command:

cabal install --enable-tests --enable-benchmarks --force-reinstalls --ghc-options=-O0 --reorder-goals --max-backjumps=-1 /home/travis/build/yesodweb/wai/warp/ /home/travis/build/yesodweb/wai/wai-conduit/ /home/travis/build/yesodweb/wai/wai-websockets/ /home/travis/build/yesodweb/wai/wai/ /home/travis/build/yesodweb/wai/wai-handler-launch/ /home/travis/build/yesodweb/wai/auto-update/ /home/travis/build/yesodweb/wai/warp-tls/ /home/travis/build/yesodweb/wai/wai-handler-fastcgi/ /home/travis/build/yesodweb/wai/mime-types/ /home/travis/build/yesodweb/wai/wai-extra/ /home/travis/build/yesodweb/wai/wai-app-static/

Expected:

• Either dependency solving succeeds or fails, in a reasonable amount of time
• Very long period of inactivity

[23Skidoo]

/cc @kosmikus

[grayjay]

I started looking into this issue. There is no solution, because there is a conflict between warp's doctest test suite and its benchmarks with GHC 7.6.3.

The test requires doctest, which requires the package ghc. ghc cannot be reinstalled, and the installed version depends on the installed bytestring (0.10.0.2). The benchmark requires criterion >= 1. criterion-1.0.0.0 through 1.1.1.0 all require aeson >= 0.8, and aeson-0.8.0.0 through 0.11.2.0 require bytestring >= 0.10.4.0.

It would be nice to have cabal fail faster, especially when there is a conflict involving so few packages.

[snoyberg]

@grayjay Thank you, that information was very useful. For my immediate needs, I've disabled benchmark building for GHC 7.6.3 (yesodweb/wai@7127092), which works around this issue nicely, and we get testing of the wai repo with 7.6.3 again.

[phadej]

@grayjay is the problem because solver tries ghc quite late in the traversal?

[grayjay]

cabal tries ghc late because it waits to try warp:test. I ran the solver after removing the constraint on criterion so that it could finish. Here are the logs, with and without --reorder-goals: https://gist.github.com/grayjay/5e889f9a701705399f3a054fbc2ac312. I think it would be better if --reorder-goals always ranked goals with 0 or 1 valid choices, like warp:test, ahead of goals with more choices.

[kosmikus]

@grayjay Sorry, only now looking.

I think it would be better if --reorder-goals always ranked goals with 0 or 1 valid choices, like warp:test, ahead of goals with more choices.

Isn't this exactly what --reorder-goals is doing? Or are you saying that this strategy interferes with other heuristics? If you're already set up to test this, could you try with my or your "count-conflicts" branch?

[grayjay]

@kosmikus --reorder-goals prefers goals with fewer choices, but only after many choices have been removed by the heuristics phase. PSQ.prefer and preferByKeys remove the non-preferred goals:

cabal/cabal-install/Distribution/Solver/Modular/PSQ.hs

Line 136 in 9d0c0c0

prefer :: (a -> Bool) -> PSQ k a -> PSQ k a

.

I tried your count-conflicts branch, and it finished in about 8 minutes. The final conflict set was aeson, base, bytestring, criterion, directory, doctest, ghc, hashable, http2, psqueues, time, unix, wai-extra, warp, warp-3.2.7:test, warp-3.2.7:bench.

[kosmikus]

@grayjay Oh right. I had indeed discovered that in most of the cases where count-conflicts is still slow, the removal of choices in the heuristics phase is the culprit. I think we can/should fix this by switching to a scoring approach, as we've discussed elsewhere. Then we can more easily defer choices without completely removing them.

[snoyberg]

I'm unfamiliar with how the solver works internally and therefore have no
input, but just wanted to say thank you all for investing time in trying to
resolve this.

On Fri, May 27, 2016 at 10:25 AM, Andres Löh [email protected]
wrote:

@grayjay https://github.com/grayjay Oh right. I had indeed discovered
that in most of the cases where count-conflicts is still slow, the removal
of choices in the heuristics phase is the culprit. I think we can/should
fix this by switching to a scoring approach, as we've discussed elsewhere.
Then we can more easily defer choices without completely removing them.

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#3453 (comment), or mute
the thread
https://github.com/notifications/unsubscribe/AADBB7SwJMelL5kWudhMj0uOEJn2Ydtyks5qFpxbgaJpZM4Ij_b1
.

[grayjay]

@kosmikus Yes, I think that would fix the issue. How will --reorder-goals interact with the goal ordering on your branch, or will it no longer be necessary?

@snoyberg No problem

[grayjay]

I looked into why warp:test is being deferred in the heuristics phase, as @kosmikus suggested. The behavior changed in #3092 and b502b7f.

#3092 added preferPackageStanzaPreferences, which sets stanza nodes to "weak" in order to defer them and allow tests/benchmarks to be disabled more easily when a dependency is unavailable:

cabal/cabal-install/Distribution/Solver/Modular/Preference.hs

Line 122 in 48a1de5

in SChoiceF qsn gr True ts' -- True: now weak choice

. b502b7f changed deferWeakFlagChoices to handle stanzas as well as flags.

I think there is a bug in preferPackageStanzaPreferences, because it changes the stanza choice to "weak" even when the preference doesn't apply. But even when the preference does apply, the function causes the stanza to be deferred when a choice has already been made with --enable-tests. One option is to change deferWeakFlagChoices so that it only defers flags and stanzas when no choices have been disabled. But then it would depend on the step that enforces constraints, which would complicate things slightly.

I also noticed that the weak/trivial field on the stanza choice node has a different meaning in other parts of the code. Here it means that the stanza has no dependencies:

cabal/cabal-install/Distribution/Solver/Modular/Tree.hs

Lines 53 to 55 in 48a1de5

	-- The Bool indicates whether it's trivial (see 'FChoice' for a discussion
	-- of triviality).
	| SChoice QSN a Bool (PSQ Bool (Tree a))

cabal/cabal-install/Distribution/Solver/Modular/Builder.hs

Line 165 in 48a1de5

trivial = L.null t

/cc @kosmikus @dcoutts

[kosmikus]

@grayjay The fact that "weak" and "trivial" are mixed up is deliberate. In index conversion, trivial flags and stanzas should get the flag set. Later, it's only relevant for deferral, and since all trivial entities should be weak, it should be safe to set the flag for additional entities that we want to be deferred.

I think I agree that preferPackageStanzaPreferences makes too many stanza choices weak.

More generally, I think we should prefer rather than defer choices for which we know that at most a single option can be taken.

[phadej]

https://github.com/dmwit/universe solving is quite slow with ghc-7.0.4, and takes ages with ghc-7.2.2. Example build: https://travis-ci.org/phadej/universe/builds/141199839

Let's see if your changes for this issue would improve universe situation as well.

EDIT:

• I'm not sure that there is a plan for ghc-7.2.2, most likely isn't (adjunctions >= 4 doesn't have a build plan for ghc-7.2.2: http://matrix.hackage.haskell.org/package/adjunctions)
  --reorder-goals seems to slow down (to 3m22s from 2m31s) solving for ghc-7.0.2
• with --constraint 'free <4.5 the time gets down to 35s for ghc-7.0.2 (guess based on http://matrix.hackage.haskell.org/package/free)

[kosmikus]

@phadej it seems that universe is nicely handled by count-conflicts-2 as it currently is, without any extra tweaks on how to (not) defer flags.

I didn't have 7.2.2 readily available, so I tested with 7.2.1 instead.

Here are times on my machine (with other things running next to it, so not overly reliable, but the relative speedup should be definitive enough): https://gist.github.com/kosmikus/c411abf4390dfd1adbcc16f6b665eb43

• ghc-7.0.2 with --count-conflicts: 2.011s
• ghc-7.0.2 with --no-count-conflicts: 160.397s
• ghc-7.2.1 with --count-conflicts: 1.961s
• ghc-7.2.1 with --no-count-conflicts: 988.347s

(I'm a bit surprised that you got 3m22s for 7.2.2. I didn't think my machine to be that slow.)

[phadej]

@kosmikus, great to hear! (I haven't waited for ghc-7.2.2, all times were for ghc-7.0.2)

[kosmikus]

@phadej I've finally turned this into a PR, so you can test it yourself if you like.

[grayjay]

This is fixed by #3480. I opened #3482 and #3488 to track the other issues that were brought up by this example.