On Mon, Oct 23, 2000 at 07:09:08AM +0300, Eray Ozkural wrote:
> > Of course it supports upload and removal of packages from the pool. That's
> > it's whole point.
> No, I'm saying "does it support automatic upload and removal?"
Exactly to the extent that's desired, yes it does. As discussed in the
second last mail of mine in this thread.
> > > > You say you're into algorithms. Maybe, then, you'd like to do some
> > > I looked at that, but why do I have to find what's hidden? :)
> > Because, quite frankly, I have better things to do than hold your hand
> > through complicated code and alogorithms that I have no guarantee you'll
> > understand.
> I looked at the code, but I've found out that it's not well commented.
*shrug* Such is life.
> Long-hacked C code isn't very easy to understand if there're no comments
> around. I could work it out myself, but I'll be very pleased if you
> could give a brief overview of the code and some useful comments because
> I really want to do a review of the code. I guarantee that I'll understand
> it. You could at least tell me about the algorithm that you used;
> did you do random-restart hill climbing, or do you resort to a heuristics?
The first thing you'll need to note is that it's *not* the SAT
problem. There's a trivial "installable" situation that satisfies all the
"givens": don't try to install anything. Once you install one thing, that
invalidates a bunch of other statements, which it then tries to correct.
It's largely brute force, with a few heuristics to make things
quicker. But mostly there's just a large degree of care taken in the
backtracking.
It's unknown what cases it's actually exponential for, if it's reasonable
to expect those cases to occur within Debian, or if they can be easily
avoided. It's fast enough for the moment (it process a weeks updates in a
few minutes, and all the updates since potato released in half an hour or
so), but that's mainly because the machine it's running on is obscenely
fast, and it also seems significantly slower than it was in June.
> May I kindly request you to tell me whether this search is complete?
> And does it perform good because average |clauses|/|proposition_symbols|
> is ... low? I'd be pleased if you can point out what to check next.
Well, think about it: in the *general* case, most packages have fairly
straightforward dependencies, and conflicts tend not to come into play
too much.
The main speed problem is simply that there are 5000 packages on each
of six different architectures, all of which interdepend to a greater
or lesser extent. That's up to 30k SAT problems that need to be checked
every time a new package is checked for inclusion in testing, and there
are usually a dozen of those a day [0], plus any leftovers of which
there are often lots.
> No, that's not much effort. As you see I've already invested some
> time in it. The code is okay as I've seen it; I assume you've already
> benchmarked it so we could try to improve it if you've observed
> performance flaws.
I benchmarked it some time ago, which is why it works at an adequate speed
at the moment. IIRC, I had problems getting a profiler to see through
the perl harness I'm using, so I haven't any recent, or particularly
accurate data.
> > And in any event, tools don't have to make things more complicated. Just
> > because we now have dpkg doesn't mean we have to use it for every new
> > piece of software we install. Just because we have apt, doesn't mean we
> > have to use it for every new piece of software we install. Just because
> > we have bugscan, doesn't mean we have to use it as our sole measure
> > of when we can release. Just because we have "testing" doesn't mean we
> > can't manually play with what packages we will and won't release.
> Why are we using apt in installing almost everything then?
Reread the above. Apt is a *good thing*. I'm not claiming otherwise. The
point is that there are cases where it's better to just do things by
hand, and that apt is such a wonderful program that it *allows* this,
even while it automates everything else.
> Anyway,
> I think organizations like Debian should favor automated systems for
> a political reason, too. It might be possible to distribute management
> and provide less bureaucracy if you build it into the technology.
> Less management, more equality. You don't have to agree with this,
> but I have a feeling that many people here don't like bureaucracy.
One thing we definitely favour is less talk, more action.
You can keep thinking up nifty projects 'til the cows come home, but no
one really benefits from them until someone gets around to implementing
them. And I can assure you that everyone else on this list is too busy
with their own projects to magically do something you've thought up and
talked about.
> About this dpkg.c thing, I've a lot of projects on my hand. :( The best
> way would be to use a debugger to trace through that routine and
> figure out exactly what it does (although I did have an idea what it was
> when I read it) but that might take considerable time. Is there a
> chance I could find a well commented version of that code?
Yes, I have a well commented version that I keep hidden away and only look
at when it suits me. Verily, I run my code through an obfusticator and
a second year engineering student before making it available to others.
No, you've got the most well commented, up to date version right there in
your browser. But for someone well versed in algorithmic theory, and who's
happy to rewrite dpkg at the drop of a hat, it shouldn't be a bother.
Cheers,
aj
[0] That doesn't match my forum quote of about 100 updated source packages
a day, by an order of magnitude. I wonder which one's wrong.
--
Anthony Towns <aj@humbug.org.au> <http://azure.humbug.org.au/~aj/>
I don't speak for anyone save myself. GPG signed mail preferred.
``We reject: kings, presidents, and voting.
We believe in: rough consensus and working code.''
-- Dave Clark
Attachment:
pgp68NXWWEtmt.pgp
Description: PGP signature