From owner-freebsd-hackers@FreeBSD.ORG Wed Feb 14 17:55:19 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 DCD5916A46D for ; Wed, 14 Feb 2007 17:55:19 +0000 (UTC) (envelope-from lists@jnielsen.net) Received: from ns1.jnielsen.net (ns1.jnielsen.net [69.55.238.237]) by mx1.freebsd.org (Postfix) with ESMTP id C17E413C4C7 for ; Wed, 14 Feb 2007 17:55:19 +0000 (UTC) (envelope-from lists@jnielsen.net) Received: from localhost (jn@ns1 [69.55.238.237]) (authenticated bits=0) by ns1.jnielsen.net (8.12.9p2/8.12.9) with ESMTP id l1EHt9AE010751; Wed, 14 Feb 2007 12:55:09 -0500 (EST) (envelope-from lists@jnielsen.net) From: John Nielsen To: freebsd-hackers@freebsd.org Date: Wed, 14 Feb 2007 12:55:53 -0500 User-Agent: KMail/1.9.5 References: <17875.18893.789217.224987@canoe.dclg.ca> In-Reply-To: <17875.18893.789217.224987@canoe.dclg.ca> X-Face: #X5#Y*q>F:]zT!DegL3z5Xo'^MN[$8k\[4^3rN~wm=s=Uw(sW}R?3b^*f1Wu*.<=?utf-8?q?of=5F4NrS=0A=09P*M/9CpxDo!D6?=)IY1w<9B1jB; tBQf[RU-R<,I)e"$q7N7 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200702141255.53501.lists@jnielsen.net> X-Virus-Scanned: ClamAV version 0.88.4, clamav-milter version 0.88.4 on ns1.jnielsen.net X-Virus-Status: Clean Cc: David Gilbert 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 17:55:20 -0000 On Wednesday 14 February 2007 12:41, David Gilbert wrote: > 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). Just a "me too". I noticed a huge increase in time for portupgrade when I started using the modular Xorg ports tree and upgraded to X.org 7.2RC. The number of installed ports on my machine went from just over 300 to well over 600 as a result of the upgrade. Specifying small numbers of ports (without globbing) to portupgrade doesn't seem to take much more time, but "portupgrade -a" or anything similar takes forever now. If there is an optimization to be made there it would be good to do it before modular xorg hits the official tree. JN