Solver choices
Hi folks,
I want to discuss a few choices regarding solver optimisation.
# Ordering / Choice preservation
You might remember that one of the concerns with solvers other than
apt's internal solver is that they ignore the order of or groups, so
a | b would install b if b has less dependencies.
My solution here is to look at all possible solutions for an or group,
and assign weights: -10^{5-i} for the i-th choice. Let's consider an
example. Installing plasma-desktop with kopete on Ubuntu installs libqt4-sql,
we have the following depends:
libqt4-sql Depends libqt4-sql-mysql | ... | ... | libqt4-sql-sqlite
kopete Recommends libqt4-sql-sqlite
(there are no other dependencies on libqt4-sql-*)
apt would install both libqt4-sql-sqlite and libqt4-sql-mysql, whereas
the new solver would only install libqt4-sql-sqlite, as
libqt4-sql-mysql gets 10^5 from libqt4-sql = 10^4
libqt4-sql-sqlite gets 10^2 from libqt4-sql, and 10^5 from kopete = 10^5+10^2
I think that's fine. APT would probably pick the same thing if kopete came before
libqt4-sql, as it would see and satisfy libqt4-sql-sqlite and then notice libqt4-sql's
dep is already satisfied.
# Non-candidate solutions
I propose we order the list of versions per package by preference. Then, given a
maximum of $n$ versions per package, we assign $(n+1)^{n-k}$ to the $k$-th item
in the list. Or to express it differently, we run $n$ optimisation passes, the
first pass optimises #first choices installed, the second the #second, and so
on.
This ensures that non-candidate solutions have as many candidates as possible,
as many second-best choices as possible, and so on. I expect non-candidate solutions
to be opt-in, but we could also just warn and say "The following packages are not
their default version". This comes with a performance impact, though, as it needs
about $k$ additional solver runs (there will be some optimisations to merge multiple
criteria into one criterion to reduce the number of runs).
Downgrades probably need to be minimized before doing any optimisations here, as
otherwise satisfying one candidate by downgrading another might be fine.
# Recommends handling
I plan to add a criterion -newunsatrecommends that essentially encodes the requirement
that as many new Recommends (Recommends from newly installed packages, or new recommends
for installed packages) nas possible need to be satisfied.
This criterion would run after the ordering criterion above, ensuring that ordering also
works for recommends. It's questionable whether to run it after changed.
Assuming our criteria for install will be -changed,choice,-newunsatrecommends,-new, a
Recommends: foo (>> bar) will not upgrade foo if it is <= bar. If our criteria is
choice,-newunsatrecommends,-changed,-new it would. APT currently upgrades packages due
to recommends, but doing that here seems to come with a performance issue, as the criteria
choice and newunsatrecommends are more "open" than the changed criterion - they take longer
to optimise. I also don't think upgrading packages due to recommends is all that useful.
--
debian developer - deb.li/jak | jak-linux.org - free software dev
ubuntu core developer i speak de, en
Reply to: