From owner-freebsd-ports@FreeBSD.ORG Sat May 12 19:30:54 2007 Return-Path: X-Original-To: freebsd-ports@freebsd.org Delivered-To: freebsd-ports@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 508F516A404 for ; Sat, 12 May 2007 19:30:54 +0000 (UTC) (envelope-from jdc@koitsu.dyndns.org) Received: from alnrmhc15.comcast.net (alnrmhc15.comcast.net [206.18.177.55]) by mx1.freebsd.org (Postfix) with ESMTP id 2572713C45A for ; Sat, 12 May 2007 19:30:53 +0000 (UTC) (envelope-from jdc@koitsu.dyndns.org) Received: from icarus.home.lan (c-71-198-0-135.hsd1.ca.comcast.net[71.198.0.135]) by comcast.net (alnrmhc15) with ESMTP id <20070512193053b1500slvlse>; Sat, 12 May 2007 19:30:53 +0000 Received: by icarus.home.lan (Postfix, from userid 1000) id B603A1FA01D; Sat, 12 May 2007 12:30:52 -0700 (PDT) Date: Sat, 12 May 2007 12:30:52 -0700 From: Jeremy Chadwick To: Stephen Montgomery-Smith Message-ID: <20070512193052.GA63649@icarus.home.lan> Mail-Followup-To: Stephen Montgomery-Smith , Kris Kennaway , "[LoN]Kamikaze" , freebsd-ports@freebsd.org References: <464597C6.3030406@gmx.de> <20070512174011.GA22526@xor.obsecurity.org> <4645FF71.60100@gmx.de> <20070512175824.GA23103@xor.obsecurity.org> <20070512133054.B5588@math.missouri.edu> <20070512183634.GA23819@xor.obsecurity.org> <20070512134849.D5588@math.missouri.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20070512134849.D5588@math.missouri.edu> User-Agent: Mutt/1.5.15 (2007-04-06) Cc: "\[LoN\]Kamikaze" , freebsd-ports@freebsd.org, Kris Kennaway Subject: Re: Time to abandon recursive pulling of dependencies? X-BeenThere: freebsd-ports@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Porting software to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 12 May 2007 19:30:54 -0000 On Sat, May 12, 2007 at 01:53:36PM -0500, Stephen Montgomery-Smith wrote: > I believe that if this function is optimized, that practically all of the > slowness issues we have seen with pkg_add, pkg_deinstall, etc, will be > solved. Give me a few days. I think I will be able to make it work very > much faster. For starters it uses a bubble sort. I can understand why they > don't want to use a quicksort, because they want to check complete integrety > of comparison tree (i.e. that there are no internal loops), but I recall > seeing an algorithm due perhaps to one of or both of Hopcroft and Tarjan > that uses a depth first search, maybe 20 years ago, that should be much > faster, and I think I could reproduce it. Please don't use a bubblesort, it's incredibly inefficient. Using a topological sort would be the most optimal way to do this. It's a standard algorithm: http://en.wikipedia.org/wiki/Topological_sorting http://www.cee.hw.ac.uk/~alison/ds98/node65.html We have existing code that does it (src/usr.bin/tsort/tsort.c), but one shouldn't use the code from there. tsort.c builds the actual graph in memory, which isn't needed in the case of pkg_install as long as we have functions like chkifdepends() and others which query dependency relations (these represent arcs in the graph). Thanks for looking into/solving all of this though. Thumbs up. :-) -- | Jeremy Chadwick jdc at parodius.com | | Parodius Networking http://www.parodius.com/ | | UNIX Systems Administrator Mountain View, CA, USA | | Making life hard for others since 1977. PGP: 4BD6C0CB |