[Yum-devel] Re: Speeding up depsolving

[Gijs Hollestelle]

I looked into the problem a little bit further (hit send just a little
too early). And I came up with a patch that collects the list of items
removed during the inner loop of depsolving and moves the checkRemove
step to the outer look of the depsolving. This makes the number of
lookups required a factor 300 less in my case. This patch makes sure
we first construct the list of everything that is removed in the pass
and then does the whole check in one go in the end.

This should (and in my testing does) give the same results as the code
currently in yum. There still  appears to be a problem in my test case
where the depsolving incorrectly wants to update both test-gijs and
readline but this also occurs in the current version of yum. I'll try
and see if I can chase that down.

The results of the patch should be the same as current yum only with a
big speed improvement.

Greets,
  Gijs

On 4/18/07, Gijs Hollestelle <gijs at gewis.nl> wrote:
> Hi all,
>
> I installed Fedora Core 7 test 3 yesterday to see what I could expect
> for the final release. I was very pleasantly surprised by the new yum
> version included, the only thing I noticed was that depsolving yum
> upgrade from test 3 to current rawhide took a very long time.
>
> I found out that a lot of this time is used because when a package for
> example readline is set to be upgraded from version a to verion b yum
> needs to check whether there is anything in the rpmdb that requires
> something that was provided by version a but no longer provided by the
> new version b.
>
> Apart from doing this in the rpmdb yum also checks whether this
> condition holds for anything in the current transaction. In order to
> do this it will for every updated package do the following:
> Iterate through all packages in the current transaction and through
> all their requirements and see if there is anything that satisfies the
> conditions above. When you apply this to an upgrade of 300 packages
> with an average of 30 requirements per package this takes 9000 steps
> times 300 packages gives 2.7 million checks!
>
> Disabling this check by commenting out lines 998 - 1012 gives some
> very impressing results:
> Check enabled:
> yummain.py upgrade  225.72s user 43.63s system 95% cpu 4:41.73 total
>
> Check disabled:
> yummain.py upgrade  50.75s user 8.54s system 78% cpu 1:15.09 total
>
> A factor 3 speed-up!
> In order to test whether I actually broke something I decided to
> create a test-case that I thought would fail now because of the
> removed code:
>
> I created an empty test package called test-gijs and installed it.
> I put an update for test-gijs which requires readline = 0:5.2-3.fc7 in
> my test repository
> then called yum update readline test-gijs and this correcly bailed out
> of depsolving with the following error
> Error: Missing Dependency: readline = 5.2-3.fc7 is needed by package test-gijs
>
> What did not work correctly was running yum update which would attempt
> to update readline and test-gijs while this is not possible.
>
> So it looks like there are some cases where the code is useful
>
> Greets,
>   Gijs
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: depsolve-check.patch
Type: text/x-patch
Size: 2476 bytes
Desc: not available
Url : http://lists.baseurl.org/pipermail/yum-devel/attachments/20070418/e20af049/attachment.bin