On Mon, 17 Jun 2013 00:07:57 +0200 Tom Wijsman <tom...@gentoo.org> wrote: > That's assuming you would go threaded, but you can also aim for lower > algorithmic complexities; the complexity makes the CPU the bottleneck.
Dependency solving is NP-hard in theory and better than quadratic in practice. The resolution algorithms also aren't the problem in terms of runtime (and still won't be if we started using more sophisticated algorithms for better decision making). The problem is simply that the model is large and messy, and the problem being solved has all kinds of awful corner cases that have to be considered. (As one example, every user has somewhere between a hundred and a thousand packages installed, each of which depends directly or indirectly upon every other package in this collection.) There are certainly improvements to be made, both in terms of efficiency and correctness, but if you're looking for a big leap forward then the most useful thing we could do is reduce or eliminate some of the requirements that make dependency resolution such a fiddly (not hard) problem. -- Ciaran McCreesh
signature.asc
Description: PGP signature
