Date: Sat, 12 May 2007 13:53:36 -0500 (CDT) From: Stephen Montgomery-Smith <stephen@math.missouri.edu> To: Kris Kennaway <kris@obsecurity.org> Cc: "\[LoN\]Kamikaze" <LoN_Kamikaze@gmx.de>, freebsd-ports@freebsd.org Subject: Re: Time to abandon recursive pulling of dependencies? Message-ID: <20070512134849.D5588@math.missouri.edu> In-Reply-To: <20070512183634.GA23819@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>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sat, 12 May 2007, Kris Kennaway wrote: > On Sat, May 12, 2007 at 01:33:40PM -0500, Stephen Montgomery-Smith wrote: >> 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. I believe that if this function is optimized, that practically all of the slowness issues we have seen with pkg_add, pkg_deinstall, etc, will be solved. Give me a few days. I think I will be able to make it work very much faster. For starters it uses a bubble sort. I can understand why they don't want to use a quicksort, because they want to check complete integrety of comparison tree (i.e. that there are no internal loops), but I recall seeing an algorithm due perhaps to one of or both of Hopcroft and Tarjan that uses a depth first search, maybe 20 years ago, that should be much faster, and I think I could reproduce it. (But if someone else decides to work on it instead, email me immediately so that I don't have to do it.)
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20070512134849.D5588>