portupgrade O(n^m)?

[Ivan Voras]

David Gilbert wrote:
> I have 734 ports installed on my laptop right now.  I'm pretty sure,
> at times, I've had over 1000 ports on my laptop.
> 
> On machine with moderate numbers of ports (most servers seem to have
> 50 to 200 ports), portupgrade takes a moderate amount of time to start
> work.  On machines like my laptop, portupgrade seems to take much more
> time to run.  I assume it's solving the dependency graph before it
> decides what to upgrade first, but is this truly a O(n^2) problem?  It
> seems like the implemented algorithm is O(n^2).

Is portupgrade the problem or one of the pkg_* utilities it calls? I
recently had a problem where a cycle was created in ports dependencies
and portupgrade was very slow in the 'registering packages' part - which
is apparently done by calling pkg_create. It seems to me that this
suspicious comment in sortdeps() might have something to do with it:

 52         if (chkifdepends(pkgs[j], pkgs[i]) == 1) {
 53         /*
 54          * Try to avoid deadlock if package A depends on B which in
 55          * turn depends on C and C due to an error depends on A.
 56          * Use ugly but simple method, becase it Should Never
 57          * Happen[tm] in the real life anyway.
 58          */
 59         if (loop_cnt > 4096) {
 60             warnx("dependency loop detected for package %s", pkgs[j]);
 61             err_cnt++;
 62             break;
 63         }

It's a pessimal way to check for dependencies, but I don't know enough
about how pkg_* works to fix it (i.e. when I tried replacing it with
something better, it broke).

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 262 bytes
Desc: OpenPGP digital signature
Url : http://lists.freebsd.org/pipermail/freebsd-hackers/attachments/20070215/51adb9f1/signature.pgp