On Wed, Feb 14, 2007 at 12:41:33PM -0500, David Gilbert wrote: > On machine with moderate numbers of ports (most servers seem to have > 50 to 200 ports), portupgrade takes a moderate amount of time to start > work. On machines like my laptop, portupgrade seems to take much more > time to run. I assume it's solving the dependency graph before it > decides what to upgrade first, but is this truly a O(n^2) problem? It > seems like the implemented algorithm is O(n^2).
Well, the complexity is somewhere in the area of O(nm) with m being small. I strongly suggest some basic bucket hashing if it is not done already. For the pkgsrc bulk build (which has similiar problems) it reduced the time to around 3 minutes to resolve all dependencies (6k packages), initally it was somewhere in the area of 1h. Joerg _______________________________________________ [email protected] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-hackers To unsubscribe, send any mail to "[EMAIL PROTECTED]"
