[prev in list] [next in list] [prev in thread] [next in thread] 

List:       gentoo-portage-dev
Subject:    [gentoo-portage-dev] Constraint-Based Dependency Solver: initial results
From:       michael.lienhardt () laposte ! net
Date:       2019-08-30 14:34:28
Message-ID: 203159305.4080690.1567175668529.JavaMail.zimbra () laposte ! net
[Download RAW message or body]

Dear all,

It's possible that the goal of my current work and its possible benefit for the \
gentoo community are not very clear. In my experience, emerge is a very good tool to \
install new packages whose use flags have already been configured. However, when the \
packages are not correctly configured, emerge can guess, without guarantee, some use \
flags to select/unselect; and unmerging a package seems to be the user's entire \
responsability. My work has several goals:
 - provide a correct and complete implementation of a dependency solver for portage \
                that can help debug emerge
 - since the solver is correct and complete, it would provide a "safe" implementation \
of unmerge, where missing dependencies would be satisfied by the installation of new \
                packages
 - provide a rather small code base that is easy to debug and on which it is easy to \
                prototype some tools, like REQUIRED_USE checks, or interactive use \
                flag configuration
 - be usable, both in term of memory usage and computation time.

I finished implementing the solver and did some preliminary benchs (1000 tests where \
I checked if a random set of packages -- different for each test -- could be \
installed), including comparison with emerge in "search" modality, i.e., with the \
options --autounmask y --autounmask-continue y --autounmask-backtrack y Since this is \
preliminary, I wanted to talk to you about it but I don't have every bugs identified \
yet. In average, my solver is a bit less than 10 times slower than emerge (not very \
good, but not bad as it is still far better than a brute force approach, which is \
more than 100 times slower and takes 3Gb of memory). It is important to note that my \
solver is not suited for end user usage yet (the answer it gives is correct, but \
random -- it includes useless packages, useless package removal and old versions), \
but it is the first tool that I know of that can correctly and completely (modulo \
bugs ^^) check emerge's behavior.

A first result: in more than 25% of the tests that can be installed, emerge fails.
Most of these failures come from the fact that even in "search" modality, emerge \
stops when it sees a REQUIRED_USE that is not correctly configured (I'll post a bug \
report about it and about the SLOT heuristics in a few days). I still need to look at \
the other failures to see what caused them.

Additionally, it seems that when I do "emerge package1 package2", emerge first solves \
the dependencies of package1, and then of package2. It seems that when resolving the \
depenendencies of package2, emerge can end up with a conflict between the choices it \
made for solving the dependencies of package1 and the requirements of package2. I say \
"seems" because my tests were automatically done with a rather long list of packages \
(so other reasons for the observed failures are possible). I'll try to pin down the \
actual emerge behavior and possibly file a bug report.

I am currently porting the tests on docker (to have a safe testing environment) and \
once that's done, I will be able to give actual bug reports. In the future, I have \
                the following plan:
 - cleanup the output of the solver, so it wouldn't be random and be usable instead \
                (this is "just" a technical and boring algorithm to implement, but \
                time consuming)
 - install the configuration computed by my solver (I am still unsure that emerge \
                --nodeps would be flexible enough, and maybe I will have to implement \
                my own planner)
 - find a correct abstraction of packages, similar to the SLOT heuristics ( \
https://gitweb.gentoo.org/proj/portage.git/commit/?id=a9064d08ef4c92a5d0d1bfb3dc8a01b7850812b0 \
                ), to improve efficiency
 - design an interactive package configuration algorithm + UI that would happen \
during the dependency solving process and really help the user configuring what he \
                wants and let the solver do the rest
 - start reading portage's bug tracker and continue reading its code
 - extend pdepa with other kind of relevant analysis

All comments/suggestions are welcomed.

Best,
Michael


[prev in list] [next in list] [prev in thread] [next in thread]