On Mon, 17 Jun 2013 00:07:57 +0200
Tom Wijsman <TomWij@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