portupgrade O(n^m)?

[Garrett Cooper]

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