Time to abandon recursive pulling of dependencies?

[Kris Kennaway]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 187 bytes
Desc: not available
Url : http://lists.freebsd.org/pipermail/freebsd-ports/attachments/20070512/6a6ffd8a/attachment.pgp