From owner-freebsd-ports@FreeBSD.ORG Sat May 12 19:10:18 2007 Return-Path: X-Original-To: freebsd-ports@freebsd.org Delivered-To: freebsd-ports@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id CE1C216A402 for ; Sat, 12 May 2007 19:10:18 +0000 (UTC) (envelope-from kris@obsecurity.org) Received: from elvis.mu.org (elvis.mu.org [192.203.228.196]) by mx1.freebsd.org (Postfix) with ESMTP id B8ECC13C45E for ; Sat, 12 May 2007 19:10:18 +0000 (UTC) (envelope-from kris@obsecurity.org) Received: from obsecurity.dyndns.org (elvis.mu.org [192.203.228.196]) by elvis.mu.org (Postfix) with ESMTP id 849891A3C19; Sat, 12 May 2007 12:11:05 -0700 (PDT) Received: by obsecurity.dyndns.org (Postfix, from userid 1000) id D76FF52C9B; Sat, 12 May 2007 15:10:17 -0400 (EDT) Date: Sat, 12 May 2007 15:10:17 -0400 From: Kris Kennaway To: Stephen Montgomery-Smith Message-ID: <20070512191017.GB24508@xor.obsecurity.org> References: <464597C6.3030406@gmx.de> <20070512174011.GA22526@xor.obsecurity.org> <4645FF71.60100@gmx.de> <20070512175824.GA23103@xor.obsecurity.org> <20070512133054.B5588@math.missouri.edu> <20070512183634.GA23819@xor.obsecurity.org> <20070512134849.D5588@math.missouri.edu> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="vtzGhvizbBRQ85DL" Content-Disposition: inline In-Reply-To: <20070512134849.D5588@math.missouri.edu> User-Agent: Mutt/1.4.2.2i Cc: "\[LoN\]Kamikaze" , freebsd-ports@freebsd.org, Kris Kennaway Subject: Re: Time to abandon recursive pulling of dependencies? X-BeenThere: freebsd-ports@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Porting software to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 12 May 2007 19:10:18 -0000 --vtzGhvizbBRQ85DL Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Sat, May 12, 2007 at 01:53:36PM -0500, Stephen Montgomery-Smith wrote: >=20 >=20 > On Sat, 12 May 2007, Kris Kennaway wrote: >=20 > >On Sat, May 12, 2007 at 01:33:40PM -0500, Stephen Montgomery-Smith wrote: >=20 > >>I've done a little poking around. As of right now, I think that the > >>registering takes a huge amount of time inside of a function called > >>"sortdeps" which may be found in /usr/src/usr.sbin/pkg_install/lib/deps= .c. > > > >That function certainly looks like it can be optimized. >=20 > I believe that if this function is optimized, that practically all of the= =20 > slowness issues we have seen with pkg_add, pkg_deinstall, etc, will be=20 > solved. Give me a few days. I think I will be able to make it work very= =20 > much faster. For starters it uses a bubble sort. I can understand why= =20 > they don't want to use a quicksort, because they want to check complete= =20 > integrety of comparison tree (i.e. that there are no internal loops), but= =20 > I recall seeing an algorithm due perhaps to one of or both of Hopcroft an= d=20 > Tarjan that uses a depth first search, maybe 20 years ago, that should be= =20 > much faster, and I think I could reproduce it. >=20 > (But if someone else decides to work on it instead, email me immediately= =20 > so that I don't have to do it.) Thanks, I appreciate the investigation. Kris --vtzGhvizbBRQ85DL Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.7 (FreeBSD) iD4DBQFGRhEZWry0BWjoQKURAuqPAJ9jb5w4mWK1jrAvH9AiVG0EDFO1zgCY4ijY 2U5TXmZGaOCHwPWm3aV2JQ== =MDhZ -----END PGP SIGNATURE----- --vtzGhvizbBRQ85DL--