Date: Wed, 14 Feb 2007 19:33:56 +0100 From: Joerg Sonnenberger <joerg@britannica.bec.de> To: freebsd-hackers@freebsd.org Subject: Re: portupgrade O(n^m)? Message-ID: <20070214183356.GA7745@britannica.bec.de> In-Reply-To: <17875.18893.789217.224987@canoe.dclg.ca> References: <17875.18893.789217.224987@canoe.dclg.ca>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20070214183356.GA7745>