Date: Thu, 15 Feb 2007 10:20:07 +0100 From: Ivan Voras <ivoras@fer.hr> To: freebsd-hackers@freebsd.org Subject: Re: portupgrade O(n^m)? Message-ID: <er18k7$bbp$1@sea.gmane.org> In-Reply-To: <17875.18893.789217.224987@canoe.dclg.ca> References: <17875.18893.789217.224987@canoe.dclg.ca>
next in thread | previous in thread | raw e-mail | index | archive | help
This is an OpenPGP/MIME signed message (RFC 2440 and 3156)
--------------enigEC3B402146B5F8CB7F1C0FF9
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
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.
>=20
> 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]) =3D=3D 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).
--------------enigEC3B402146B5F8CB7F1C0FF9
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (FreeBSD)
Comment: Using GnuPG with Thunderbird/FreeBSD - http://enigmail.mozdev.org
iD8DBQFF1CXHldnAQVacBcgRAlJ3AJ9cFRiaq5LELI2/XGyPrv8/CzmZUACgug61
DkqLKrdOwQdZOqTPTE+MdZ8=
=QV7c
-----END PGP SIGNATURE-----
--------------enigEC3B402146B5F8CB7F1C0FF9--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?er18k7$bbp$1>