On Sat, May 12, 2007 at 01:53:36PM -0500, Stephen Montgomery-Smith wrote: > > > 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.)
Thanks, I appreciate the investigation. Kris
pgpm6CGPvwWan.pgp
Description: PGP signature
