Improved dependency solving?

[GreatEmerald]

One thing that has always bothered me when working with Gentoo is portage's dependency solver. Two things, really: solving speed (particularly the need to resolve dependencies after they're already solved once) and conflict handling.

In general, I'm curious, what exactly makes the dependency solving such a long process? Does the solver compare all the different USE flag combinations to find the "optimal" one, or such? Could the solving speed itself be improved by using different algorithms, caching, etc., or is it already using efficient methods? What struck me is how eix works pretty much instantaneously, compared to emerge --search; could something like that be done for the dependency solver?

Another question is, why doesn't the dependency solver have an option to cache previous solutions (that I know of, anyway)? There are often times when it tries and resolves the exact same solution as on the last invocation, for instance, when there are USE flag changes necessary. In that case, you wait for it to solve the dependencies for the first time, then emerge stops saying that you should add --autounmask-write, then you add it, wait for the solver to solve the same dependencies it just solved, then emerge exits saying that you should run dispatch-conf, then you run it, then you wait for the solver to solve the exact same dependencies a third time. In addition, why can't --pretend also cache the solution, so the solver wouldn't have to solve it a second time when you run it as non-pretend?

About conflict solving: often times emerge outputs fairly unclear information, and some of it seems rather useless to begin with (all those slot conflict lines saying that there are no parents unsatisfied by another package in the slot, for instance – that seems like a very long way of saying "there was a slot conflict, but it was solved and you don't need to bother with this"). But what bothers me the most is that it's all non-interactive. The solver assumes it knows best and offers a solution it thinks is optimal (while also being rather fearful of unmerging conflicting packages). Many times its suggestions are not what was wanted, and then to change the suggestion, the user has to change the initial emerge arguments (remembering exactly what package they want to suggest emerge to update/install) and then wait for the entire tree to get resolved. It's just not very efficient.

It feels to me that the command line just doesn't cut it in this case. Things like --tree help, but they are still too unwieldy and completely non-interactive. I can imagine GUI tools doing a much better job at the whole dependency solving aspect by using a visual approach to the problem. Each package could be represented by a box with sockets, through which different packages are connected. For instance, a simplified version of what one could see if they choose to install webkit-gtk could be this:

[Ant P.]

[GreatEmerald]

[The Doctor]

[steveL]

[kernelOfTruth]

dependency solving on portage got worse and worse

it's probably time to try out pkgcore aka pmerge again


...


not sure how pkgcore is supposed to work if it fails at such trivial things

[John R. Graham]

[SamuliSuominen]

[kernelOfTruth]

[John R. Graham]

[steveL]

I think it's more an indication that the recent multilib and python-deps "shove everything into the ebuild" approach doesn't work very well, as McCreesh has mentioned a couple of times on the mailing-list.

Couple that with systemd profiles being used as a political tool, instead of simply masking systemd elsewhere, as was initially planned and sold to us, and you have a recipe for lots of stupid || deps that should never even have existed, or been considered, raring their ugly head.

[TomWij]

Hello GreatEmerald; this has bothered me in the past, so I've looked into it from time to time as well as tried to minimize the impact of it on my update process. It helps on my "a lot of packages" system when I try to lower backtracking as low as possible; avoid packages, USE flags, Python/... implementations, overlays I don't need and so on; help out Portage by masking certain paths it shouldn't take; ... such that quite some time is cut and the dependency resolution time and conflicts become reasonable again. Please note that time and conflicts are inverse when lowering backtracking; so, as you lower time the conflicts can be more tricky. But managing to solve them (by USE flag changes or masks) will keep them away and avoid the need for more backtracking.

[steveL]

pkgcore has always been magnitudes of order quicker than portage, way before EAPI5 came around.

Sure it'll doubtless slow down as well when given all these nonsense dependencies, but it's still much quicker on the same inputs.

That Tom can't see those areas of improvement, is merely an indicator that he's still young, and fresh outta Uni: inexperienced iow; and the portage codebase is complex, which is why it took ferringb a while to rewrite it.

As Tom said, you'd need a fork, which is what others have already stated, and has twice been done. paludis it turns out is actually slower, despite all the hype about a "C++ package manager." pkgcore never aimed for speed only correctness, and has always beaten every other resolver hands down. (Now paludis claims to aim only for correctness too; which is good as it's a pig.)

[TomWij]

pkgcore continues to stall behind Portage which yields unusable hyped snake oil performance improvements;
it also misses out on the necessary complexity that people use Portage for, which indeed would slow it down.

It is like an impatient youngster that steals and crashes a fast car.

That is a clear indicator that pkgcore is still young, fresh and inexperienced;
it takes time for it to grow up, because premature optimization is the root of all evil.

I didn't say that a fork is needed, but rather say that you end up with one; what you do need is a merge.

[EmaRsk]

[The Doctor]

[steveL]

[TomWij]

steveL ... You provide too much simple (mis)assumptions and respond to tone, which thus misses contextual value; so, please provide actual factual references and respond to content?

Or, as you would hear a customer in a ferringb products store tell you, "Sir, this is the third time you try to sell me a shiny product that doesn't work!"

[hasufell]

[GreatEmerald]

This turned out into an interesting discussion. Thanks everyone!

Now I am a developer, but of course I have no experience with Portage's codebase itself, or with Python (I mostly code in D and C; I haven't looked into GUI toolkits either, so far worked only with SDL). I looked at Portage's source and it does have nice inline documentation, though I still wouldn't know where to start.

My original idea there should be fairly simple and doable without needing changes to the underlying package managers, and could also be agnostic to them. As TomWij pointed out, there are ways to speed up Portage as well. Lowering backtracking is just the thing, the GUI could request a very minimal dependency graph from the package manager and then let the user solve the main conflicts (possibly while a bigger dependency graph is being generated in the background). Once that is done and the GUI knows all the packages that need to be installed, updated and removed, those can be passed to the package manager while disabling their own dependency solver (as they're already solved). However, it's true that the message passing would very likely be too limited and a more direct interfacing with the library would eventually be required, and that's much more complex.

Granted, improving the package managers themselves would be a more direct approach to the problem. But I simply don't think a CLI is capable of presenting it all as well as a GUI would. Ideally you wouldn't need to do any conflict solving as the package manager would solve it all by itself, but that's a pipe dream, without input from the user to know their intent it's impossible to do everything the user wants. After all, it's Gentoo, users want all kinds of crazy things, very often not the defaults. With the current uninteractive paradigm, it's inevitable that you would need to recalculate all the dependencies every time you want to do any sort of change, and making the CLI interactive will never be as visual as using a GUI.

And then there's the issue with accessibility as well. One of the Gentoo devices I maintain is used by non-tech people, and with the current state of things, it is impossible for them to install anything on their own. Editing multiple text files, crafting a long CLI command and then waiting a long time for it to return something which is not necessarily going to work to begin with? Way out of league. Meanwhile a GUI where you draw lines between coloured squares is much more easy to understand. After all, there already have been attempts to make a portage GUI (Portato and such), but those were trying to mimic the way the CLI works instead of changing the paradigm entirely, and in the end that didn't seem to work out that well.

I've never actually heard of pkgcore, it sounds pretty interesting. Why isn't it EAPI 5 capable? Not enough maintainers?

[hasufell]

[szatox]

[krinn]