Skip site navigation (1)Skip section navigation (2)
Date:      Sat, 12 May 2007 15:10:17 -0400
From:      Kris Kennaway <kris@obsecurity.org>
To:        Stephen Montgomery-Smith <stephen@math.missouri.edu>
Cc:        "\[LoN\]Kamikaze" <LoN_Kamikaze@gmx.de>, freebsd-ports@freebsd.org, Kris Kennaway <kris@obsecurity.org>
Subject:   Re: Time to abandon recursive pulling of dependencies?
Message-ID:  <20070512191017.GB24508@xor.obsecurity.org>
In-Reply-To: <20070512134849.D5588@math.missouri.edu>
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>

next in thread | previous in thread | raw e-mail | index | archive | help

--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--



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20070512191017.GB24508>