this is sad [LWN.net]

this is sad

Posted Jun 20, 2016 11:07 UTC (Mon) by nye (guest, #51576)
In reply to: this is sad by niner
Parent article: Klumpp: A few words about the future of the Limba project

>Until you demonstrate that even libsolv fails in your scenario, your argument stands on a very weak base.

The problem has been proven NP-complete, so it doesn't matter how many times you cry "but that's only one example!".

Until you demonstrate that P=NP, your argument stands on a very weak base.

to post comments

this is sad

Posted Jun 21, 2016 11:00 UTC (Tue) by niner (guest, #26151) [Link] (2 responses)

Theoretical limits are irrelevant when it does work well enough in practice. If the dependency solver performs well with millions of packages and comparatively small dependency trees, it doesn't matter if it would take years with a hundred times more candidates. IOW it doesn't need to solve the general problem, only the specific one you encounter in practice.

If it were different, people would not even have to bother trying to write something as widespread available as a syntax highlighter for highly dynamic programming languages like Perl or maybe even C++. Because to fully understand all parts of the source code, they'd have to solve the halting problem. So they don't. They do not pretend to handle completely arbitrary input programs but only those that matter in practice.

this is sad

Posted Jun 21, 2016 12:12 UTC (Tue) by nye (guest, #51576) [Link] (1 responses)

>If the dependency solver performs well with millions of packages and comparatively small dependency trees

That's a fairly major 'if'. It's already not too great with tens of thousands of packages[0]; I don't believe it can ever scale another three orders of magnitude (which is what would be required to be truly mainstream) without a change in approach.

If I understand correctly, package managers have already given up on finding 'optimal' solutions[1] and now use heuristic SAT solvers, but regardless, at some point distros have to let go of the idea that the installability of a given package is a function of *every other possible package*. Eventually to continue scaling there simply has to be some demarcation line that lets the solver prune the tree to something small enough to keep dependency resolution tractable. One way to do this is by separation of a core platform from leaf packages that don't (or rarely) have complex interdependencies, which coincidentally happens to describe how almost every end user actually wants a system to work.

[0]in the sense that both apt and aptitude can take a while to find a solution, especially on a less powerful machine, and aptitude will happily suggest a seemingly endless selection of terrible 'solutions'

[1] in the sense of calculating the minimal set of changes required to satisfy the request

this is sad

Posted Jun 21, 2016 12:22 UTC (Tue) by nye (guest, #51576) [Link]

>If I understand correctly, package managers have already given up on finding 'optimal' solutions[1] and now use heuristic SAT solvers

Just to expand briefly on this: I can't find a quick definitive answer in five minutes to whether libsolv, as used by zypper, is a heuristic solver or a pure solver, but there are unavoidable problems either way: if it's pure then it can't scale efficiently; if it's heuristic then it can't guarantee optimal results, and could potentially fail to find possible solutions.

Reducing the problem space by dividing it into smaller sets with fewer interdependencies is a solution to both.