portupgrade O(n^m)?

[Joerg Sonnenberger]

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