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