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
_______________________________________________
freebsd-hackers@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
To unsubscribe, send any mail to "[EMAIL PROTECTED]"
