<div dir="ltr">One thing to consider is that if conflicts do not exist (or are very rare), the number of possible combinations is a moot point.  A greedy algorithm for installation (which just chooses the most favored package to resolve each dependency) will run in linear time with the number of packages it would install, if no conflicts exist.  <div><br></div><div>So, what you are saying about state exploration may be true for a resolver that uses something like a SAT solver, but doesn't apply to backtracking dependency resolution (unless a huge number of conflicts occur) or simple dependency resolution (at all).  SAT solvers do have heuristics to avoid this blow up, except in pathological cases.  However, simple / backtracking dependency resolution systems have the further advantage of not needing to request unneeded metadata in the first place...</div><div><br></div><div>Thanks,</div><div>Justin</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, May 15, 2015 at 2:57 PM, Robert Collins <span dir="ltr"><<a href="mailto:robertc@robertcollins.net" target="_blank">robertc@robertcollins.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">So, I am working on pip issue 988: pip doesn't resolve packages at all.<br>
<br>
This is O(packages^alternatives_per_package): if you are resolving 10<br>
packages with 10 versions each, there are approximately 10^10 or 10G<br>
combinations. 10 packages with 100 versions each - 10^100.<br>
<br>
So - its going to depend pretty heavily on some good heuristics in<br>
whatever final algorithm makes its way in, but the problem is<br>
exacerbated by PyPI's nature.<br>
<br>
Most Linux (all that i'm aware of) distributions have at most 5<br>
versions of a package to consider at any time - installed(might be<br>
None), current release, current release security updates, new release<br>
being upgraded to, new release being upgraded to's security updates.<br>
And their common worst case is actually 2 versions: installed==current<br>
release and one new release present. They map alternatives out into<br>
separate packages (e.g. when an older soname is deliberately kept<br>
across an ABI incompatibility, you end up with 2 packages, not 2<br>
versions of one package). To when comparing pip's challenge to apt's:<br>
apt has ~20-30K packages, with altnernatives ~= 2, or<br>
pip has ~60K packages, with alternatives ~= 5.7 (I asked dstufft)<br>
<br>
Scaling the number of packages is relatively easy; scaling the number<br>
of alternatives is harder. Even 300 packages (the dependency tree for<br>
openstack) is ~2.4T combinations to probe.<br>
<br>
I wonder if it makes sense to give some back-pressure to people, or at<br>
the very least encourage them to remove distributions that:<br>
 - they don't support anymore<br>
 - have security holes<br>
<br>
If folk consider PyPI a sort of historical archive then perhaps we<br>
could have a feature to select 'supported' versions by the author, and<br>
allow a query parameter to ask for all the versions.<br>
<br>
-Rob<br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
Robert Collins <<a href="mailto:rbtcollins@hp.com">rbtcollins@hp.com</a>><br>
Distinguished Technologist<br>
HP Converged Cloud<br>
_______________________________________________<br>
Distutils-SIG maillist  -  <a href="mailto:Distutils-SIG@python.org">Distutils-SIG@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/distutils-sig" target="_blank">https://mail.python.org/mailman/listinfo/distutils-sig</a><br>
</font></span></blockquote></div><br></div>