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