RPM Community Forums

Mailing List Message of <rpm-devel>

Re: Generalizing EVR comparison precedence, preliminaries

From: Jeff Johnson <n3npq@mac.com>
Date: Fri 09 Jan 2009 - 18:17:06 CET
Message-id: <9010ADA4-1B92-41DC-9DC4-AAEC6810ECC8@mac.com>

On Jan 9, 2009, at 11:05 AM, devzero2000 wrote:

>
> But a rpmbuild rewrite seems to be my current RPM goal because  
> YAMLspec!
> is the only roadmap item @rpm5.org I'm hearing consensus about.
>
>
> Off topic.
>
> Am i the only who  like the initial development of a dep-solver in  
> rpm5 via sat-solver ?
>

No, having an "integrated depsolver" is still on the @rpm5.org  
ROADMAP, and
these days, that also means accommodating a SAT engine as an assertion  
checker.

I can send privately the description of the "integrated depsolver" that
is already in place in RPM for many years from when the RPM-5.0 ROADMAP
was formulated.

Remaining "depsolver" issues have largely to do with creating  
representations of
metadata in a larger framework for installation from multiple  
reposittories, and
for efficiently representing input assertions for a SAT (or other)  
engine.

What appears to be the most promising SAT depsolver input format imho  
is from Mancoosi,
called CUDF. As the Mancoosi project progresses, I'm hoping that RPM  
can supply
CUDF for depsolver problems directly, without the necessary but rather  
awkward
(because there's a huge amount of data contained in a rpmdb, or in a  
vendor distro
repository) need for a DUDF -> CUDF translation.

There are already implementations to generate CUDF for apt (and apt- 
rpm, from Caixa Magica), as
well as for urpmi (from Mandriva) that exist. If I can see a few more  
"real world"
examples of CUDF, then I can attempt spewing CUDF directly from RPM.

For details, see the appropriate Mancoosi mailing lists, where you  
will find
something called libCUDF, whose licensing was just changed from GPL ->  
LGPL
(thank you!) to accomodate the LGPL only restriction on @rpm5.org code.

The other promising SAT input representation (and implementation) is  
from SuSE
in libzypp. There is a binary .solv format in libzypp that is very  
efficient for
distributing package metadata, and is already integrated with a SAT  
depsolver.
Accomodating .solv format, and either using the zypp SAT solver  
directly, or
at least compatibly, are issues I looked at last April. Splitting out  
details for
use by RPM will be very challenging with zypp code for many reasons.

But the fundamental problem that I have is
	Is a depsolver based on SAT instead worth the effort?

Solutions from a SAT depsolver, because of the logic engine involved,  
are quite efficient,
and come back with strong guarantees that, say, a given solution is  
"optimal", or
that no solution exists.

But in the "real world" of packaging, the strong guarantees provided  
by a SAT depsolver
are perhaps irrelevant to users. Do users really distingush between  
the two software
installation failure cases
	No upgrade solution was found.
and
	No upgrade solution exists.
In both cases, a software upgrade did not "work".

Similarly, for the positive software installation case, I wonder  
whether users really care
	The upgrade succeeded.
and
	The upgrade succeeded optimally.

As for efficiency, there are many competitions for SAT solvers that
measure the time taken for assertion checking, and there are
many quite clever techniques to improve the performance of
the assertion checking.

But in the "real world" of RPM packaging, the time taken by depsolving
is only 6-10% of the total install time, so any performance gain by
using SAT can affect only a small part of the total install time. Other
metrics like memory/cpu utilization, have almost nothing to do with
whether a SAT solver is used, but rather have to do with how
metadata is organized, and how metadata is retrieved, all of
which metrics can be improved with or without using SAT as
an assertion checking engine.

I also believe that end users are most strongly sensitive to the
total time of a software installation. But the majority of time
in any installer is spent writing files to the file system, not
in depsolving, and more sophisticated I/O implementations,
wth say, aio, or aggressive read-ahead/write-behind, are
likelier than a SAT depsolver to minimize what the end-user
wants, which is "faster installs".

Disclaimer: There are __LOTS__ of other software installer criteria,  
including "reliability" and "scalability"
and "market share", the list is endless, that are important. SAT  
solvers most certainly have usefulness,
I am not saying anything else.

73 de Jeff


  • application/pkcs7-signature attachment: smime.p7s
Received on Fri Jan 9 18:17:27 2009
Driven by Jeff Johnson and the RPM project team.
Hosted by OpenPKG and Ralf S. Engelschall.
Powered by FreeBSD and OpenPKG.