Time to abandon recursive pulling of dependencies?

[Jeremy Chadwick]

On Sat, May 12, 2007 at 01:53:36PM -0500, Stephen Montgomery-Smith wrote:
>  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.

Please don't use a bubblesort, it's incredibly inefficient.

Using a topological sort would be the most optimal way to do this.  It's
a standard algorithm:

http://en.wikipedia.org/wiki/Topological_sorting
http://www.cee.hw.ac.uk/~alison/ds98/node65.html

We have existing code that does it (src/usr.bin/tsort/tsort.c), but one
shouldn't use the code from there.  tsort.c builds the actual graph in
memory, which isn't needed in the case of pkg_install as long as we
have functions like chkifdepends() and others which query dependency
relations (these represent arcs in the graph).

Thanks for looking into/solving all of this though.  Thumbs up.  :-)

-- 
| Jeremy Chadwick                                    jdc at parodius.com |
| Parodius Networking                           http://www.parodius.com/ |
| UNIX Systems Administrator                      Mountain View, CA, USA |
| Making life hard for others since 1977.                  PGP: 4BD6C0CB |