Turn on --reorder-goals by default

[snoyberg]

I'll admit that I don't understand exactly what --reorder-goals does under the surface. It was basically explained to me as a feature that makes complicated build plans get resolved more quickly, but slows down simpler build plans. Apologies if that's completely incorrect.

In any event, I've recently needed to update the Yesod installation guide to include --reorder-goals, as it drastically cuts down on the number of times cabal fails to find a valid build plan. Is there a reason not to have this feature on by default? If it's just to speed up simple build plans, I'd argue that those are probably fast enough already.

[23Skidoo]

/cc @kosmikus

[kosmikus]

Michael's description of the tradeoffs of --reorder-goals is correct. I'm in principle ok with enabling --reorder-goals by default.

[kosmikus]

Have you run benchmarks on this? I said that I am in principle ok with
this, but we should not blindly trust that this is an improvement, but
rather have some numbers to back it up.

I don't have my old numbers, but I certainly had a reason that I originally
decided that enabling the option by default is probably not worth it.

[23Skidoo]

@kosmikus
Here are some numbers (avg. of three runs):

	--dry-run	--dry-run --reorder-goals
hnop	0.95 s	0.96 s
yesod	1.53 s	7.99 s
cabal-install	1.04 s	1.58 s
lens	1.05 s	2.07 s
text	0.95 s	1.03 s
accelerate	1.45 s	2.14 s

The slow-down seems to be acceptable overall except in the case of yesod.

[snoyberg]

While I'm concerned about the fact that yesod takes such a longer time to get started, I still prefer that situation to the one where average users just get a confusing error message. IMO we should open up a separate issue to investigate why the solver is so slow on yesod with --reorder-goals, especially since (at least I believe) yesod is working with all the newest versions of its dependencies, which tends to be the simplest case to solve.

[bergmark]

I've noticed considerable slowdown because of this. I timed this with time cabal install foo --dry-run
on one of our internal packages.

Current Cabal master: 12.08 real 9.83 user 1.28 sys
Cabal 1.18: 2.97 real 2.02 user 0.80 sys

All dependencies were are already installed, the output of dry run (in both cases) is just

Resolving dependencies...
In order, the following would be installed (use -v for more details):
foo-0.1

[23Skidoo]

If the majority of users are opposed, we can always revert this change.

[hesselink]

I don't see any speedups in any of the benchmarks, so the speedup in some cases (like @snoyberg says in the first paragraph) doesn't seem to happen. If the problem is that some plans don't find a solution with the current defaults, wouldn't raising the default for 'max-backjumps' be a better fix? On our build server has it set to 8000, which might be a bit extreme as a default, but the current 200 is pretty low.

[kosmikus]

Let's clarify the situation a bit: --reorder-goals applies a heuristic that will typically mean that a valid solution (if one exist) appears significantly "earlier" in the search space. However, in doing so, it'll make traversing the search space more costly, because additional analysis is being performed at each step in determining which goals are more or less costly.

So it's entirely possible that while on average, time consumption goes up quite a bit, there are situations where --reorder-goals can find a solution in "finite" time where the normal solver even with --max-backjumps=-1 takes "forever".

The extra analysis performed by --reorder-goals can potentially be sped by memoization. Prompted by the discussion here, I started looking into this over Easter, but haven't finished. I'm vaguely hopeful that this can be done, but it won't happen within the next few days, I'm afraid, as I have too many other things to do.

Given the numbers @23Skidoo has posted (and also my own measurements), I do think that for the time being, having --reorder-goals available as an option, but not as the default, is still the best solution.

[snoyberg]

To be clear, as the original requester, I don't want this change to go through if it significantly impairs normal usage of cabal. If --reorder-goals can be improved and the performance brought closer to the current default, I'd be very happy. But I can continue telling users to try out --reorder-goals if the solver fails the first time around.

Which makes me wonder: would it make sense to instead of turning on --reorder-goals by default, to try to find a build plan without --reorder-goals and, if that fails, try a second time with --reorder-goals?

[kosmikus]

@snoyberg There are currently two types of failure.

One is that there's really no solution being found. In this case the solver prints Dependency tree exhaustively searched. In this case (unless the solver is actually buggy), there is no hope and no solution exists.

The other is that the backjump limit is being reached. In this case, the solver prints Backjump limit reached (change with --max-backjumps). In this situation, reinvoking the solver may help, but it's unclear in general whether saying --reorder-goals or simply increasing/disabling the backjump limit is more promising. So I don't quite know whether it's a good idea to do something by default, when there are several options.

@hesselink @23Skidoo BTW, the current limit of 200 may indeed be far too low given the size of Hackage we now have. I think increasing this to 2000 would be a relatively harmless change.

[23Skidoo]

I've reverted this change and also set defaultMaxBackjumps to 2000 as @kosmikus suggested.

[tibbe]

Do we want to ship this fix in the next 1.20 bugfix release?

On Tue, Apr 22, 2014 at 3:17 PM, Mikhail Glushenkov <
[email protected]> wrote:

I've reverted this change and also set defaultMaxBackjumps to 2000 as
@kosmikus https://github.com/kosmikus suggested.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/1780#issuecomment-41037829
.

[23Skidoo]

@tibbe

Do we want to ship this fix in the next 1.20 bugfix release?

The defaultMaxBackjumps one? I'm +0.

[tibbe]

I guess we should cherry-pick -x the --reorder-goals one though, as it
likely made people's cabal installs slower.

On Tue, Apr 22, 2014 at 3:43 PM, Mikhail Glushenkov <
[email protected]> wrote:

@tibbe https://github.com/tibbe

Do we want to ship this fix in the next 1.20 bugfix release?

The defaultMaxBackjumps one? I'm +0.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/1780#issuecomment-41040670
.

[23Skidoo]

I guess we should cherry-pick -x the --reorder-goals one though, as it likely made people's cabal installs slower.

This change wasn't in 1.20, so no need to revert it.

[heyakyra]

is this no longer planned? i was unable to build yi without this option

[grayjay]

--reorder-goals still makes each step significantly slower, so I think that the reasons for not making it the default still apply. The solution that @snoyberg suggested in #1780 (comment) could work, though. I created a separate issue for it: #4776

It's also possible that there is a bug causing the solver to not find a solution more quickly without --reorder-goals. Do you want to open an issue for the yi build?

[Mikolaj]

Given that this ticket is linked to from the user guide, let me warn that --reorder-goals in some cases slows down dependency resolution from from 15s to 1200s. See #7784.