From owner-freebsd-hackers@FreeBSD.ORG Wed Feb 14 17:41:33 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 C49EE16A407 for ; Wed, 14 Feb 2007 17:41:33 +0000 (UTC) (envelope-from dgilbert@daveg.ca) Received: from ox.eicat.ca (ox.eicat.ca [66.96.30.35]) by mx1.freebsd.org (Postfix) with ESMTP id 9ED5713C4A6 for ; Wed, 14 Feb 2007 17:41:33 +0000 (UTC) (envelope-from dgilbert@daveg.ca) Received: by ox.eicat.ca (Postfix, from userid 66) id 9D67FE1E6; Wed, 14 Feb 2007 12:41:32 -0500 (EST) Received: by canoe.dclg.ca (Postfix, from userid 101) id DD5A661C85; Wed, 14 Feb 2007 12:41:33 -0500 (EST) From: David Gilbert MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <17875.18893.789217.224987@canoe.dclg.ca> Date: Wed, 14 Feb 2007 12:41:33 -0500 To: freebsd-hackers@freebsd.org X-Mailer: VM 7.17 under 21.4 (patch 19) "Constant Variable" XEmacs Lucid Subject: 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 17:41:33 -0000 I have 734 ports installed on my laptop right now. I'm pretty sure, at times, I've had over 1000 ports on my laptop. 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). Dave. -- ============================================================================ |David Gilbert, Independent Contractor. | Two things can be | |Mail: dave@daveg.ca | equal if and only if they | |http://daveg.ca | are precisely opposite. | =========================================================GLO================