Skip site navigation (1)Skip section navigation (2)
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>