[pacman-dev] [PATCH] Reduce the negligence of _alpm_resolvedeps

[Xavier]

On Sat, Dec 01, 2007 at 12:06:59PM +0100, Xavier wrote:
> On Sat, Dec 01, 2007 at 12:24:16AM +0100, Nagy Gabor wrote:
> > > On Thu, Nov 29, 2007 at 10:13:42PM +0100, Nagy Gabor wrote:
> > > > OK, but I leave the benchmark for you;-)
> > > > Note: Long "dependency paths" like in smoke001.py may cause notable
> > > > slowdown. I made a quick "hack", so probably I made some mistakes...
> > > > 
> > > 
> > > I couldn't measure any difference. pacman always need ~3.5 seconds for
> > > running smoke001.
> > > 
> > Because it is an add transaction;-) I just said that it contains a long
> > dependency path, which can cause notable slowdown in case of -S
> > first_element_of_path. (Unfortunately I cannot write such tricky
> > pactests in python).
> > 
> 
> Oops, my bad. In my defense, it was a bit late :)
> But now, I'm slightly confused. How hard is it to edit smoke001 to do what
> you want? It looks like a totally trivial change to me. So I'm not sure I
> understood what you wanted.
> 

So, I made a simple change to smoke001 :

---------------------------------------------------------------------------
self.description = "Install a thousand packages in a single transaction"

p = pmpkg("pkg1000")

self.addpkg2db("local", p)

for i in range(1000):
	p = pmpkg("pkg%03d" % i)
	p.depends = ["pkg%03d" % (i+1)]
	p.files = ["usr/share/pkg%03d" % i]
	self.addpkg2db("sync", p)

self.args = "-S pkg001"

self.addrule("PACMAN_RETCODE=0")
self.addrule("PKG_EXIST=pkg050")
self.addrule("PKG_EXIST=pkg674")
self.addrule("PKG_EXIST=pkg999")
---------------------------------------------------------------------------

Your resolvedeps patch indeed made its complexity explode :) I couldn't even
wait long enough for it to finish.
So I reduced the number to 100 packages, so that it could handle it in a few
seconds:

---------------------------------------------------------------------------
self.description = "Install a thousand packages in a single transaction"

p = pmpkg("pkg100")

self.addpkg2db("local", p)

for i in range(100):
	p = pmpkg("pkg%02d" % i)
	p.depends = ["pkg%02d" % (i+1)]
	p.files = ["usr/share/pkg%02d" % i]
	self.addpkg2db("sync", p)

self.args = "-S pkg01"

self.addrule("PACMAN_RETCODE=0")
self.addrule("PKG_EXIST=pkg50")
self.addrule("PKG_EXIST=pkg74")
self.addrule("PKG_EXIST=pkg99")
---------------------------------------------------------------------------


I think I see the problem now, the checkdeps calls done in resolvedeps are
something like:
checkdeps(pkg1)
checkdeps(pkg1, pkg2)
checkdeps(pkg1, pkg2, pkg3)
...
checkdeps(pkg1, .......... , pkg99)

While previously, it was:
checkdeps(pkg1)
checkdeps(pkg2)
...
checkdeps(pkg99)

So, I had the following idea, do a first pass with the old algorithm :
checkdeps(pkg1)
checkdeps(pkg2)
...
checkdeps(pkg99)

And once it's done, do a checkdeps call on the whole list :
checkdeps(pkg1, .......... , pkg99)

So there would be a first pass with the old algorithm, and a second pass with
your new one. But I don't really see how to implement this cleanly.