On Friday 05 December 2003 22:33, George Shapovalov wrote:
>
> 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 :).

Prolog interpreters work as depth-first searchers. Breath-first is in most 
cases a waste of both memory and clock cycles. In the case of portage this 
would mean something like first getting deep dependencies like glibc, and 
then less important ones. Of course a full dependency tree for portage is a 
bit more complicated than just a graph, anyway that is implementation.

> 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).

I didn't really look at your sourcecode, just at your web-page.

>
> 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 don't believe that the average size of world is going to grow significantly. 
In any case more installed packages often also means a beefier computer.

>
> 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 :).
>
We need indeed a highlevel abstraction, and dep trackers are one of the 
modules. I think that access to the package tree is another, where caching 
can be modular too.


> 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 didn't write that, guess you'll need to ask the person who did.

> 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.

The only less deterministic behaviour I think is acceptable is in the time it 
takes for all dependencies to be calculated, as long as the maximum is 
sensible.

Paul

-- 
Paul de Vrieze
Gentoo Developer
Mail: pauldv@gentoo.org
Homepage: http://www.devrieze.net