<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Feb 10, 2017 at 3:52 PM, David Cournapeau <span dir="ltr"><<a href="mailto:cournape@gmail.com" target="_blank">cournape@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span>On Fri, Feb 10, 2017 at 2:33 PM, Justin Cappos <span dir="ltr"><<a href="mailto:jcappos@nyu.edu" target="_blank">jcappos@nyu.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Yes, don't use a SAT solver.  It requires all metadata from all packages (~30MB uncompressed) and gives hard to predict results in some cases. </div></blockquote><div><br></div></span><div>I doubt there exists an algorithm where this is not the case.</div></div></div></div></blockquote><div><br></div><div>Okay, so there was a discussion about the pros and cons (including algorithms like backtracking dependency resolution which do not require all metadata) a while back on the mailing list:  <a href="https://mail.python.org/pipermail/distutils-sig/2015-April/026157.html">https://mail.python.org/pipermail/distutils-sig/2015-April/026157.html</a><br></div><div><br></div><div>(I believe you may have seen this before because you replied to a message further down in the thread.)</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><span><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">  Also the lack of fixed dependencies is a substantial problem for a SAT solver.  Overall, we think it makes more sense to use a simple backtracking dependency resolution algorithm.</div></blockquote><div><br></div></span><div>As soon as you want to deal with version ranges and ensure consistency of the installed packages, backtracking stops being simple rather quickly.</div></div></div></div></blockquote><div><br></div><div>Can you explain why you think this is true?  </div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>I agree lack of fixed dependencies is an issue, but I doubt it is specific to a SAT solver. SAT solvers have been used successfully in many cases now: composer (php), dnf (Red Hat/Fedora), conda or our own packages manager at Enthought in python, 0install.</div></div></div></div></blockquote><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>I would certainly be interested in seeing a proper comparison with other algorithms.</div></div></div></div></blockquote><div><br></div><div>Sure, there are different tradeoffs which make sense in different domains.  Certainly, if you have a relatively small set of packages with statically defined dependencies and already are distributing all package metadata to clients, a SAT solver will be faster at resolving complex dependency issues. <br></div><div><br></div><div>We can provide the data we gathered (maybe others provide get some data too?) and then the discussion will be more grounded with numbers.</div><div><br></div><div>Thanks,</div><div>Justin</div></div></div></div>