From owner-freebsd-hackers@FreeBSD.ORG Thu Feb 15 02:44:50 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 04BD316A400 for ; Thu, 15 Feb 2007 02:44:50 +0000 (UTC) (envelope-from youshi10@u.washington.edu) Received: from mxout5.cac.washington.edu (mxout5.cac.washington.edu [140.142.32.135]) by mx1.freebsd.org (Postfix) with ESMTP id D638613C471 for ; Thu, 15 Feb 2007 02:44:49 +0000 (UTC) (envelope-from youshi10@u.washington.edu) Received: from smtp.washington.edu (smtp.washington.edu [140.142.33.7] (may be forged)) by mxout5.cac.washington.edu (8.13.7+UW06.06/8.13.7+UW06.09) with ESMTP id l1F2in6s011635 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Wed, 14 Feb 2007 18:44:49 -0800 X-Auth-Received: from [192.168.10.41] (c-67-187-172-183.hsd1.ca.comcast.net [67.187.172.183]) (authenticated authid=youshi10) by smtp.washington.edu (8.13.7+UW06.06/8.13.7+UW06.09) with ESMTP id l1F2imlZ023098 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for ; Wed, 14 Feb 2007 18:44:48 -0800 Message-ID: <45D3C91E.2000509@u.washington.edu> Date: Wed, 14 Feb 2007 18:44:46 -0800 From: Garrett Cooper User-Agent: Thunderbird 1.5.0.9 (X11/20070122) MIME-Version: 1.0 To: freebsd-hackers@freebsd.org References: <20070215001758.GA32225@lpthe.jussieu.fr> In-Reply-To: <20070215001758.GA32225@lpthe.jussieu.fr> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-PMX-Version: 5.3.0.289146, Antispam-Engine: 2.5.0.283055, Antispam-Data: 2007.2.14.182933 X-Uwash-Spam: Gauge=IIIIIII, Probability=7%, Report='__CT 0, __CTE 0, __CT_TEXT_PLAIN 0, __HAS_MSGID 0, __MIME_TEXT_ONLY 0, __MIME_VERSION 0, __SANE_MSGID 0, __USER_AGENT 0' 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: Thu, 15 Feb 2007 02:44:50 -0000 Michel Talon wrote: > Joerg Sonnenberger wrote: > >> 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. > > The problem is the so called topological sorting of a DAG which is of > order (n+m) where n is the number of nodes and m the number of arrows in > the DAG. In my python program pkgupgrade, i perform this sorting for > the whole set of ports (16000 +) in a couple of seconds. I am quite sure > that portupgrade uses one of the standard algorithms so i doubt very > much that the problem is here. I suspect it is much more in the constant > appeal to databases instead of bringing all data in memory, plus the > natural slowness of ruby. Portmaster in no way solves this problem, nor > helps upgrading in reasonable time. Portupgrade is an excellent program, > very polished, and you will not find much better for source > upgrading. A lot of time is lost in pkg_delete() and pkg_add() which, > while written in C are very inefficient. I have measured that for > removal et reinstallation of around 500 ports at full speed (with a > shell script driving the operation and all binary packages present) > you need around 2 hours. No program efficient or not, can do > without spending these 2 hours, plus the time of downloading the > packages, plus the time of doing backups with portupgrade. If you > envision compiling from source like portmaster does, then you can go > to sleep and come back next morning, hoping that it did not stop after > the first few ports. Give me a few weeks, and if I can band together with a few people I wanted to try and port sections of portupgrade and its related tools to C++ (and maybe do some code tweaks along the way). Most of the ruby files are over 400 lines long, sparsely commented, and I don't know ruby enough to port right now, but I've been making some headway lately so I'll try porting some stuff soon. Again, any help with this endeavor would be much appreciated and would greatly speed up the process. -Garrett