-
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 https://github.com/haskell/cabal/issues/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 https://github.com/haskell/cabal/issues/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.
f4f57f24
