Date: Thu, 15 Feb 2007 01:17:58 +0100 From: Michel Talon <talon@lpthe.jussieu.fr> To: freebsd-hackers@freebsd.org Subject: Re: portupgrade O(n^m)? Message-ID: <20070215001758.GA32225@lpthe.jussieu.fr>
next in thread | raw e-mail | index | archive | help
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. -- Michel TALON
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20070215001758.GA32225>