| 1 |
On Thu, Apr 23, 2020, at 14:14, Caveman Al Toraboran wrote: |
| 2 |
> On Wednesday, April 22, 2020 9:34 PM, Michael Orlitzky <mjo@g.o> wrote: |
| 3 |
> |
| 4 |
> > Dependency resolution is indeed a (formally) hard problem. Solving the |
| 5 |
> > traveling salesman problem is also hard. Solving the traveling salesman |
| 6 |
> > problem while being punched in the face is even harder. When I complain |
| 7 |
> > about portage being slow, what I mean is that I want to stop being |
| 8 |
> > punched in the face so that I can concentrate all of my energy on the |
| 9 |
> > underlying hard problem. |
| 10 |
> |
| 11 |
> any reason why is it a traveling salesman problem, |
| 12 |
> and not just a tree walk with heuristics to handle |
| 13 |
> exceptions (e.g. cycles)? |
| 14 |
> |
| 15 |
|
| 16 |
If it's so easy, why don't you implement it? /s |
| 17 |
|
| 18 |
Sorry for being a little glib but every couple months I go through this thought process: |
| 19 |
|
| 20 |
1. Wow, portage is slow |
| 21 |
2. I can make this faster, it can't be that hard |
| 22 |
3. ...wow, nevermind, it is really hard |
| 23 |
4. Thank you portage maintainers!!!!! |
| 24 |
|
| 25 |
> |
| 26 |
> my thought |
| 27 |
> ---------- |
| 28 |
> |
| 29 |
> my thought is that dep. resolution is like walking |
| 30 |
> down a tree, and branch out depending on the USE |
| 31 |
> flags -- for this, imo the sympt. run-time |
| 32 |
> complexity should be approximately O(log n), where |
| 33 |
> n = number of packages in portage. |
| 34 |
|
| 35 |
I don't think it's O(log n). Roughly, for 1 package portage has to make the full dep |
| 36 |
tree, solve all the constraints to resolve to actual packages that can be installed, |
| 37 |
and order and merge the tree into a single branch of packages to install. I'm |
| 38 |
probably missing some steps and obviously that's not a rigorous explanation but |
| 39 |
it's at least O(n) where n is the total number of dependencies. |
| 40 |
|
| 41 |
> except that some of its leaves go back to a branch |
| 42 |
> (circular dependencies). here, we can add |
| 43 |
> heuristics/workarounds when cycles are detected. |
| 44 |
|
| 45 |
Cycles make it even more complicated, and I'm not up on the latest algorithms |
| 46 |
to resolve these and know how fast they are. |
| 47 |
|
| 48 |
Speeding up portage would be a fun project but it's less important |
| 49 |
that portage being correct. |
| 50 |
|
| 51 |
Alec |
Archives