Cabal can't new-build bytestring with GHC 8.0.1 #3824
Comments
Can reproduce with a GHC 8.0.2 snapshot and a recent |
|
Is the problem possibly that new-build will always force use of an installed package if it's available, but since you have a new bytestring we can't use the old unix, so it's unsat? I don't actually know where this policy gets applied. |
|
Definitely feels like a blocker for 2.0. @grayjay if you don't have time to investigate feel free to unassign yourself. |
|
Okay. I at least wanted to look into the last problem. |
|
The space leak was introduced in #3594 and is unrelated to the broken package. I'll work on a PR. |
|
/cc @dcoutts |
The space leak was introduced in haskell#3594. haskell#3594 added a new variable, sortedVersions, to sort the subtrees under package choice nodes in the search tree. However, sortedVersions referenced the subtrees and caused them to be retained when it was not used. This commit forces evaluation of sortedVersions.
Fix a space leak in package preferences (part of issue #3824).
|
I did some more debugging, and I think there are multiple issues here. The reason that the solver didn't find a solution is that new-build first tries to enable tests, but the tests create a cyclic dependency. A bug in the solver prevents it from falling back to building without tests. The solver also takes too long to find that there is no solution, so it hits the backjump limit. It finds a solution immediately with
We would need something like #3422 in order for cabal to find a solution with tests enabled. Without that, I think we would at least need to fix 3 and 4 so that cabal can fail more quickly. 3 doesn't seem too hard, unless performance is a problem. I'm not sure how to fix 4. |
|
Thank you for the detailed analysis. Does (4) become less of a problem if we "componentize" the solver more? |
|
Depending on how we implement component-based solving, it could help with the missing test/bench variables, though it probably wouldn't help with flags. |
|
I just noticed that #1185 describes the broken package issue. |
Previously, the solver only checked for cycles after it had already found a solution. That reduced the number of times that it performed the check in the common case when there were no cycles. However, when there was a cycle, the solver could spend a lot of time searching subtrees that already had a cyclic dependency and therefore could not lead to a solution. This is part of haskell#3824. Changes in this commit: - Store the reverse dependency map on all choice nodes in the search tree, so that 'detectCyclesPhase' can access it at every step. - Check for cycles incrementally at every step. Any new cycle must contain the current package, so we just check whether the current package is reachable from its neighbors. - If there is a cycle, we convert the map to a graph and find a strongly connected component, as before. - Instead of using the whole strongly connected component as the conflict set, we select one cycle. Smaller conflict sets are better for backjumping. - The incremental cycle detection automatically fixes a bug where the solver filtered out the message about cyclic dependencies when it summarized the full log. The bug occurred when the failure message was not immediately after the line where the solver chose one of the packages involved in the conflict. See haskell#4154. I tried several approaches before I found something with reasonable performance. Here is a comparison of runtime and memory usage. I turned off assertions when building cabal. Index state: index-state(hackage.haskell.org) = 2016-12-03T17:22:05Z GHC 8.0.1 Runtime in seconds: Packages Search tree depth Trials master This PR haskell#1 haskell#2 yesod 343 3 2.00 2.00 2.13 2.02 yesod gi-glib leksah 744 3 3.21 3.31 4.10 3.48 phooey 66 3 3.48 3.54 3.56 3.57 stackage nightly snapshot 6791 1 186 193 357 191 Total memory usage in MB, with '+RTS -s': Packages Trials master This PR haskell#1 haskell#2 yesod 1 189 188 188 198 yesod gi-glib leksah 1 257 257 263 306 stackage nightly snapshot 1 1288 1338 1432 12699 haskell#1 - Same as master, but with cycle checking (Data.Graph.stronglyConnComp) after every step. haskell#2 - Store dependencies in Distribution.Compat.Graph in the search tree, and check for cycles containing the current package at every step.
Previously, the solver only checked for cycles after it had already found a solution. That reduced the number of times that it performed the check in the common case where there were no cycles. However, when there was a cycle, the solver could spend a lot of time searching subtrees that already had a cyclic dependency and therefore could not lead to a solution. This is part of haskell#3824. Changes in this commit: - Store the reverse dependency map on all choice nodes in the search tree, so that 'detectCyclesPhase' can access it at every step. - Check for cycles incrementally at every step. Any new cycle must contain the current package, so we just check whether the current package is reachable from its neighbors. - If there is a cycle, we convert the map to a graph and find a strongly connected component, as before. - Instead of using the whole strongly connected component as the conflict set, we select one cycle. Smaller conflict sets are better for backjumping. - The incremental cycle detection automatically fixes a bug where the solver filtered out the message about cyclic dependencies when it summarized the full log. The bug occurred when the failure message was not immediately after the line where the solver chose one of the packages involved in the conflict. See haskell#4154. I tried several approaches and compared performance when solving for packages with different numbers of dependencies. Here are the results. None of these runs involved any cycles, so they should have only tested the overhead of cycle checking. I turned off assertions when building cabal. Index state: index-state(hackage.haskell.org) = 2016-12-03T17:22:05Z GHC 8.0.1 Runtime in seconds: Packages Search tree depth Trials master This PR haskell#1 haskell#2 yesod 343 3 2.00 2.00 2.13 2.02 yesod gi-glib leksah 744 3 3.21 3.31 4.10 3.48 phooey 66 3 3.48 3.54 3.56 3.57 Stackage nightly snapshot 6791 1 186 193 357 191 Total memory usage in MB, with '+RTS -s': Packages Trials master This PR haskell#1 haskell#2 yesod 1 189 188 188 198 yesod gi-glib leksah 1 257 257 263 306 Stackage nightly snapshot 1 1288 1338 1432 12699 haskell#1 - Same as master, but with cycle checking (Data.Graph.stronglyConnComp) after every step. haskell#2 - Store dependencies in Distribution.Compat.Graph in the search tree, and check for cycles containing the current package at every step.
Previously, the solver only checked for cycles after it had already found a solution. That reduced the number of times that it performed the check in the common case where there were no cycles. However, when there was a cycle, the solver could spend a lot of time searching subtrees that already had a cyclic dependency and therefore could not lead to a solution. This is part of #3824. Changes in this commit: - Store the reverse dependency map on all choice nodes in the search tree, so that 'detectCyclesPhase' can access it at every step. - Check for cycles incrementally at every step. Any new cycle must contain the current package, so we just check whether the current package is reachable from its neighbors. - If there is a cycle, we convert the map to a graph and find a strongly connected component, as before. - Instead of using the whole strongly connected component as the conflict set, we select one cycle. Smaller conflict sets are better for backjumping. - The incremental cycle detection automatically fixes a bug where the solver filtered out the message about cyclic dependencies when it summarized the full log. The bug occurred when the failure message was not immediately after the line where the solver chose one of the packages involved in the conflict. See #4154. I tried several approaches and compared performance when solving for packages with different numbers of dependencies. Here are the results. None of these runs involved any cycles, so they should have only tested the overhead of cycle checking. I turned off assertions when building cabal. Index state: index-state(hackage.haskell.org) = 2016-12-03T17:22:05Z GHC 8.0.1 Runtime in seconds: Packages Search tree depth Trials master This PR #1 #2 yesod 343 3 2.00 2.00 2.13 2.02 yesod gi-glib leksah 744 3 3.21 3.31 4.10 3.48 phooey 66 3 3.48 3.54 3.56 3.57 Stackage nightly snapshot 6791 1 186 193 357 191 Total memory usage in MB, with '+RTS -s': Packages Trials master This PR #1 #2 yesod 1 189 188 188 198 yesod gi-glib leksah 1 257 257 263 306 Stackage nightly snapshot 1 1288 1338 1432 12699 #1 - Same as master, but with cycle checking (Data.Graph.stronglyConnComp) after every step. #2 - Store dependencies in Distribution.Compat.Graph in the search tree, and check for cycles containing the current package at every step.
|
#4176 fixed some of the issues with cyclic dependencies, so I think that the only remaining issues are #941, #1185, #1575, and flag/stanza variables missing from conflict sets for cyclic dependencies (item 4 in my previous comment: #3824 (comment)). |
~/Haskell/bytestring$ cd ~/tmp/
~/tmp$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 8.0.1
~/tmp$ cabal --version
cabal-install version 1.24.0.0
compiled using version 1.24.0.0 of the Cabal library
~/tmp$ date
Sun Sep 11 15:15:40 EDT 2016
~/tmp$ git clone https://github.com/haskell/bytestring.git
Cloning into 'bytestring'...
remote: Counting objects: 6795, done.
remote: Total 6795 (delta 0), reused 0 (delta 0), pack-reused 6795
Receiving objects: 100% (6795/6795), 12.25 MiB | 3.33 MiB/s, done.
Resolving deltas: 100% (4409/4409), done.
Checking connectivity... done.
~/tmp$ cd bytestring/
Starting with a clean slate, cabal-install-1.24 ponders for 83 seconds, then claims that the globally installed unix-2.7.2.0 package is broken:
~/tmp/bytestring$ mv ~/.cabal/ ~/.ghc/ ~/tmp/
~/tmp/bytestring$ ~/tmp/.cabal/bin/cabal update
Downloading the latest package list from hackage.haskell.org
~/tmp/bytestring$ /usr/bin/time ~/tmp/.cabal/bin/cabal new-build
Resolving dependencies...
cabal: Could not resolve dependencies:
trying: process-1.4.2.0/installed-1.4... (dependency of
optparse-applicative-0.12.1.0)
next goal: unix (dependency of process-1.4.2.0/installed-1.4...)
rejecting: unix-2.7.2.0/installed-2.7... (package is broken)
rejecting: unix-2.7.2.0, unix-2.7.1.0, unix-2.7.0.1, unix-2.7.0.0,
unix-2.6.0.1, unix-2.6.0.0, unix-2.5.1.1, unix-2.5.1.0, unix-2.5.0.0,
unix-2.4.2.0, unix-2.4.1.0, unix-2.4.0.2, unix-2.4.0.1, unix-2.4.0.0,
unix-2.3.2.0, unix-2.3.1.0, unix-2.3.0.0, unix-2.2.0.0, unix-2.0 (conflict:
process => unix==2.7.2.0/installed-2.7...)
Backjump limit reached (currently 2000, change with --max-backjumps or try to
run with --reorder-goals).
Command exited with non-zero status 1
83.05user 0.16system 1:23.74elapsed 99%CPU (0avgtext+0avgdata 298340maxresident)k
20432inputs+8outputs (75major+78990minor)pagefaults 0swaps
The HEAD version of cabal-install instead quickly diverges and thrashes my machine, unless I stop it:
~/tmp/bytestring$ /usr/bin/time ~/Haskell/cabal/dist-newstyle/build/cabal-install-1.25.0.0/build/cabal/cabal new-build
Resolving dependencies...
^CCommand terminated by signal 2
23.38user 1.23system 0:24.63elapsed 99%CPU (0avgtext+0avgdata 6580484maxresident)k
0inputs+8outputs (0major+1649612minor)pagefaults 0swaps
I tried installing a fresh new user-local unix-2.7.2.0 but that didn't help.
The text was updated successfully, but these errors were encountered: