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)? 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. except that some of its leaves go back to a branch (circular dependencies). here, we can add heuristics/workarounds when cycles are detected. how common is it to stumble upon cycles in a single dependency resolution run? let's say it happens S many times per run. so in overall, i think, it should be O(log n + S). since it can be seen as a tree, imo it is very easy to distribute the computation across several cores, even for a single package dep. resolution. e.g. create threads upon branching in the tree until MAX_THRD reached. of course all in C, statically-linked (minimum run-time dep. for emerge). i don't see why we need fancy stuff like python.
