search

sarugaku / resolvelib

Resolve abstract dependencies into concrete ones
ISC License
138 stars 31 forks source link

Always prefer causes when backtracking #132

Closed notatallshaw closed 9 months ago

notatallshaw commented 1 year ago

As per https://github.com/sarugaku/resolvelib/issues/131 this moves the responsibility from the downstream library to prefer backtracking causes into resolvelib itself solving the issue of an O(n2) performance problem that can happen.

It provides additional performance benefits under those circumstances because get_preference will be called a lot less.

After working on this PR I decided not to have this as optional, it keeps the resolver and tests much simpler and while it may be possible to construct a dependency graph where this approach is slower we have no such reports come from Pip and as per this comment in real world benchmarking there is over a 2x improvement in resolution speed to preferring backtracking, this makes intuitive sense as any successful solution must not have conflicts so resolving them first will generally be faster.

But let me know if you would prefer this approach to be optional, I can do so.

I have been testing these change in Pip on this branch: https://github.com/pypa/pip/compare/main...notatallshaw:pip:always-prefer-causes

uranusjr commented 1 year ago

Logic looks good, one question about interface change. Would it be possible to have a test for this?

notatallshaw commented 1 year ago

Logic looks good, one question about interface change. Would it be possible to have a test for this?

I will look at the existing tests and see if I can sufficiently adapt one.

notatallshaw commented 9 months ago

I'm closing this, this optimization is relatively niche in real world cases (only one reported case of significant slowdown and never been able to reproduce).

But I do have a bigger optimization that will extend this strategey to "always prefer conflicting causes, then causes", that optimization will have a stronger justification with lots of real world examples I can show it speeds up. I will make a new PR for that one.