Date: Thu, 15 Feb 2007 13:33:40 -0800 From: Doug Barton <dougb@FreeBSD.org> To: Michel Talon <talon@lpthe.jussieu.fr> Cc: freebsd-hackers@freebsd.org, freebsd ports <freebsd-ports@freebsd.org> Subject: Re: portupgrade O(n^m)? Message-ID: <45D4D1B4.8090404@FreeBSD.org> In-Reply-To: <20070215001758.GA32225@lpthe.jussieu.fr> References: <20070215001758.GA32225@lpthe.jussieu.fr>
next in thread | previous in thread | raw e-mail | index | archive | help
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.
I'm not sure what you mean by "nor helps upgrading in a reasonable
time," but I can say that portmaster isn't trying to solve the problem
of dependency graphing the entire ports tree. What portmaster does for
upgrading individual programs is look at what you have installed, and
then use the ports Makefiles to determine ordering of dependencies.
For the +a (update all) case portmaster uses the data in /var/db/pkg
to determine what ports to start with, and then proceeds up the list
in increasing order of dependency complexity. While upgrading
individual ports it reconfirms dependency information by using the
port's Makefile, and searching the +CONTENTS files to make sure that
the dependency data is recorded correctly when it's finished.
It's probably also worth noting that when I started writing portmaster
my goal was not to write a portupgrade replacement, but rather to
create a tool that quickly and efficiently would handle the subset of
the problem space that I was interested in. You may find it useful to
ask yourself the question of exactly what your goal is. If it's to
provide the be-all and end-all of ports upgrading tools, I think that
you will find your efforts frustrated by the fact that what different
groups of users want is sufficiently different to make handling those
needs with just one tool difficult, if not impossible.
You might also ask yourself what your goals are in interacting with
the FreeBSD community. I notice that your posts are heavy with
negativity, "this is stupid," "those people are morons," etc. I don't
know of any communities where those attitudes are well supported, but
I do know that you won't get very far in this community that way.
hth,
Doug
--
This .signature sanitized for your protection
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?45D4D1B4.8090404>