[Yum-devel] [Patch] Resolver Performance and Correctness

[Florian Festi]

Jeremy Katz wrote:
> On Tue, 2007-06-05 at 13:22 +0200, Florian Festi wrote:
>>    * new _checkInstall, _checkRemove,
>>     * dropped _provideToPkg and _requiredByPkg
>>    * _checkConflicts, _checkFileRequires - work globally
>>     * ignoring installed problems and problems in updates properly?
> 
> Have to look at these closer to really assess correctness.  And where
> one change at a time helps a lot.
> 
> Jeremy

Hmm, don't know if smaller patches would help here much... Some notes on 
these methods:

_checkInstall:
The resolving itself is adjusted/simplified for the new search methods. It 
now adds the pkg to all matching packages as requires. This feels more right 
than the old code although I am not yet sure about the exact semantic of 
that .relatedto/.depends_on code...

_checkConflicts:
Moved the conflict handling code out of _checkInstall because we need to 
loop over all conflicts not just the ones in the newly installed pkgs. Could 
be done in a separate patch but I didn't want to write it twice as it is 
much shorter with the new interface.

_checkRemove:
As the search is just one call now I merged the whole algorithm into a 
single set of nested loops. But in fact nothing really changed here except 
that files move out into a separate method.

_checkFileRequires:
Ok, that's the difficult one...
Rational between that method is that there are much more files that there 
are file requires. So it trades the number of files within the removed pkgs 
for the number of overall file requirements. This is a bad deal for very 
small transactions but pays of comparably fast.

If a file is removed it might break any file requirement anywhere. SO this 
code first gets a list of all file requirements already installed and checks 
with of them are full filled. File requirements that are already broken may 
stay broken.

On every call we get the file requirements from the to install pkgs and add 
them to the list. To reduce the number of searches there is a set of file 
requirements and a mapping back to the pkgs they came from.

The current code still needs an extension to ignore problems within updates. 
I also will add a short circuit to resolve most stuff on the rpmdb only.



Right now _checkConflicts and _checkFileRequires are called on every 
mytscheck round which makes them more expensive that really needed. Further 
patches could try to reduce the time they get called and that way further 
increase the performance for cases with lots of rounds like remove glibc and 
install [a-k]*.

Florian Festi