Did i just made the fastest dependency checker in the world? (198 packages in 1.5 seconds)

[Panu Matilainen]

On Wed, 11 Apr 2007, Rahul Sundaram wrote:

> Mark wrote:
>> forgive me if i sound hard but:
>> do you really need proof to see that the dependency checking is a highly 
>> time consuming thing.
>> i just did a yum update.
>> i had a 100% cpu usage for a few minutes during the dep checking. that`s 
>> _TOO_ much for just a update. (oke.. this is a update of 148 packages but 
>> still)
>> 
>> it just seems overkill for me.. specially now that i know that it can all 
>> be done in well under a second in a logic way :P
>> 
>
> You  _don't_ know that. What you are doing might be logical in a simplistic 
> way but it just doesn't deal with a lot of real world cases. When you actual 
> start dealing with all of the logic that is required to solve the 
> dependencies properly you would lose the speed advantage that you currently 
> have.

Well, depsolving *can* be that fast, the proof can be found in apt-rpm 
which takes just a few seconds (depends on the computer speed of course) 
to calculate something like fc5 -> fc6 upgrade with over thousand 
packages. Apt does pay some penalty for abstracting packaging systems
(deb vs rpm) and for all the wacko pinning + other package priority 
calculations, plain rpm depsolve in C would be quite a bit faster still.

As for yum depsolve speed... the folks just rewrote the yum depsolver to 
avoid having to download headers for depsolving, a no small feat. 
Correctness needs to come first, speed is secondary (although important) 
issue. Just how fast it can be made with just python remains to be seen 
(people are working on improving the speed all the time), but writing 
mockup depsolvers in PHP isn't going to help that cause. Writing a 
depsolver in any language is of course an interesting self-education, 
nothing wrong with that :)

 	- Panu -