Re: [gentoo-portage-dev] portage-ng concurse entry Was: Updated Portage project page

[George Shapovalov <george@gentoo.org>]

I'll answer this one as this seems a bit more substantial and I would really 
like to keep the discussion on this list. 

On Friday 05 December 2003 04:26, Paul de Vrieze wrote:
> Prolog != AI
> AI != undeterministic
Quite often these are synonimous (or were, when I was looking into this. But I 
must admit this was quite some time ago), but strictly speaking you are 
right. I'll update that section of the page.

> prolog is very good at graph traversal tasks (which is what AI in many
> cases involves and why in AI prolog is used a lot) as the mode of operation
> is basically a depth-first backtracking search algorithm (about 10 lines of
> pseudocode). For that reason I think it is a good candidate for the new and
> improved dependency algorithm.
Shouldn't it be breadth-first? With depth first you might need to do 
adjustments to the formed list occasionally, if multiple nodes go to the same 
dependency in a different number of steps. I think I was able to produce the 
example of such situation, but I would appreciate any good pointers to a 
theory :).

As fot the lines of code, that's anecdotal. 
(adding from the other email:)
>  Also, your code (which is about 1000 lines long)
> does -only- a simple dfs and topological ordering, while I can do the
> same in about 10 lines in prolog and have backtracking for free. I

The *traversal* code (btw I use BFS traversal there, not DFS) is completely 
localized in bc-graphs-directed-bfs_traverse.adb and is about the same 10 
lines :) and is completely generic. 
The rest of 990 lines deal with such mundane tasks as reading the (possibly 
misformed) ebuilds and dealing with user (inluding minimalistic help). 
Essentially just doing what you describe here:

> While prolog is very good for such tasks I don't think it is suited to
> implement the core of portage. This is not because I think prolog is a
> problem, it is because I think that such languages are not suited for
> procedural dispatch, divide, etc. tasks. That is something that C is good


> Then about caching
Well, I stated in the writeup that this is a simplistic design only relevant 
for the prototype. However I'll try to explain my reasoning for the future 
discussions.
(To drobbins: yes, I am afraid we are pulling the "discussion before 
requirements" thing again here. But this it the core and unavoidable part of 
the design, so it will definitely be there. Also I am trying to localize the 
discussion to this list only).

Thus note, all the comments below concern this hypothetical design I used in 
language demonstration, but that will probably be rethought for the real 
design.

> While you have a point with your prediction on number of packages, most of
> those packages involve leaf packages. That means that the number of
> dependencies per leaf package will probably not increase. However the
> amount of packages totally not regarded will grow. For this portage should
> do some kind of on-demand loading of packages. I see no need whatsoever to
> have a normal emerge task load in the whole tree and create a graph of
> that.
I somewhat agree with that. However my observation is that these packages most 
often are libraries or other helpers that user is usualy not interested in 
directly. And the long operations are the ones where you have to do searches 
or operations involving world. So I have been thinking along the lines of 
making the longest operations fast and bounded, getting the O(1) 
responsivity. 
But in reality I do not think this shpould be "the ultimate solution" or even 
that there should be one. See the next one.

> I would like portage to remain lean and mean. I do run gentoo on a 16MB
> 60mhz pentium, and I like it. While the cache should also be a module that
> replaces a direct-tree-read module (possibly wrapping it), I think that
> caching should be possible on a configurable level. Not just dumbly load in
> all ebuilds.
Touche :). 
That's why I spent so many words discussing memory layout.
However the real solution IMHO should allow multiple dependency trackers 
(cores) to be plugged as desired (choice of both at compilation and run-time 
(i.e. choosing at compilation to be able to choose at run time :))). And for 
that we would need a high level of efficient abstraction. And this is what 
got me started thinking about Ada :).


And finally:
> My biggest concern when reading your small paper is that you chose a
> deterministic approach to this problem, while in fact the problem is
> non-determinisitic.
Could you please elaborate? I am afraid we are thinking about slightly 
different things here.

I stay by my thought that any important to the system tool should be dumb. If 
there is any uncertainty it should stop and ask, unless it was designed for a 
very specific situation, where it can be trusted to make the choice. Package 
maintaince is not such area - IMHO every user that has identical 
configuration should get identical results (to the extent possible. So here 
we are talking requirements Daniel ;)). Otherwise we are facing a disasterous 
consequencies wil many people complaining and us being unable to reproduce 
anything reliably.

George



--
gentoo-portage-dev@gentoo.org mailing list