From owner-freebsd-hackers@FreeBSD.ORG Wed Feb 14 18:34:02 2007 Return-Path: X-Original-To: freebsd-hackers@freebsd.org Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id B088016A402 for ; Wed, 14 Feb 2007 18:34:02 +0000 (UTC) (envelope-from joerg@britannica.bec.de) Received: from shell.asta.uni-rostock.de (gateway.stura.uni-rostock.de [139.30.252.67]) by mx1.freebsd.org (Postfix) with ESMTP id 7251513C4AA for ; Wed, 14 Feb 2007 18:34:02 +0000 (UTC) (envelope-from joerg@britannica.bec.de) Received: from britannica.bec.de (unknown [192.168.16.3]) by shell.asta.uni-rostock.de (Postfix) with ESMTP id 035CA187E for ; Wed, 14 Feb 2007 18:33:59 +0000 (GMT) Received: by britannica.bec.de (Postfix, from userid 1000) id D54C3B88D; Wed, 14 Feb 2007 19:33:56 +0100 (CET) Date: Wed, 14 Feb 2007 19:33:56 +0100 From: Joerg Sonnenberger To: freebsd-hackers@freebsd.org Message-ID: <20070214183356.GA7745@britannica.bec.de> Mail-Followup-To: freebsd-hackers@freebsd.org References: <17875.18893.789217.224987@canoe.dclg.ca> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <17875.18893.789217.224987@canoe.dclg.ca> User-Agent: Mutt/1.5.13 (2006-08-11) Subject: Re: portupgrade O(n^m)? X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 14 Feb 2007 18:34:02 -0000 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