From owner-freebsd-hackers@FreeBSD.ORG Thu Feb 15 09:20:22 2007 Return-Path: X-Original-To: freebsd-hackers@freebsd.org Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id CF04916A406 for ; Thu, 15 Feb 2007 09:20:22 +0000 (UTC) (envelope-from freebsd-hackers@m.gmane.org) Received: from ciao.gmane.org (main.gmane.org [80.91.229.2]) by mx1.freebsd.org (Postfix) with ESMTP id 62EB313C461 for ; Thu, 15 Feb 2007 09:20:22 +0000 (UTC) (envelope-from freebsd-hackers@m.gmane.org) Received: from list by ciao.gmane.org with local (Exim 4.43) id 1HHcmo-0003Ry-NT for freebsd-hackers@freebsd.org; Thu, 15 Feb 2007 10:20:18 +0100 Received: from lara.cc.fer.hr ([161.53.72.113]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 15 Feb 2007 10:20:18 +0100 Received: from ivoras by lara.cc.fer.hr with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 15 Feb 2007 10:20:18 +0100 X-Injected-Via-Gmane: http://gmane.org/ To: freebsd-hackers@freebsd.org From: Ivan Voras Date: Thu, 15 Feb 2007 10:20:07 +0100 Lines: 56 Message-ID: References: <17875.18893.789217.224987@canoe.dclg.ca> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="------------enigEC3B402146B5F8CB7F1C0FF9" X-Complaints-To: usenet@sea.gmane.org X-Gmane-NNTP-Posting-Host: lara.cc.fer.hr User-Agent: Thunderbird 1.5.0.9 (X11/20070110) In-Reply-To: <17875.18893.789217.224987@canoe.dclg.ca> X-Enigmail-Version: 0.94.0.0 Sender: news Subject: Re: portupgrade O(n^m)? X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 15 Feb 2007 09:20:22 -0000 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--