On Sunday 07 December 2003 00:00, George Shapovalov wrote:
> I have been thinking a bit more about dfs vs bfs traversals, so here goes
> :).
>
> On Saturday 06 December 2003 06:26, Paul de Vrieze wrote:
> > Prolog interpreters work as depth-first searchers. Breath-first is in
> > most
>
> Yea, and unfortunately there isn't much choice about it as recursion is
> pretty much the only composition method the standard talks.

It is pretty trivial to get whatever behaviour you want in prolog for your 
problem. The program does not need to follow the way prolog parses your 
language statements.

>
> > cases a waste of both memory and clock cycles. In the case of portage
> > this
>
> Its really only O(n) where small n stands for associated dependencies, so
> that's not that much. Besides it does nopt require recursion to be
> implemented, so in reality that hit quite often is not even there.
>
I don't think there is a significance in breath of depth first here (breath 
first has the same problems with changing deps as depth) as the whole tree 
needs to be created/walked anyway. (I first thought you were thinking of the 
tree of all available ebuilds). If you use prolog, probably depth-first is 
easier.

> And isn't this the "right" way to do it? Surely operating on a *complete*
> portage tree, that is the one where all the dependencies are explicitly
> stated, that wouldn't make any difference. But in reality glibc and similar
> dependencies, being a part of the system, are omitted in pretty much all
> ebuilds. Thus, with DFS traversal (which is what portage does now) one is
> getting glibc somewhere in the middle of world update quite often, which is
> not optimal if you want complete coherency (and it can be plain bad in the
> case of the major update. This is somewhat alleviated in our case for
> system packages by a mandatory bootstrap, but some stuff on perifery can be
> hit, if multiple things use the same library and it is affected for example
> (and not explicitly included, say because it is consdered "basic")).

One can easilly create a virtual glibc dependency for all ebuilds. Then as all 
ebuilds depend on it it would come first in the flattened vectror result.

> No, but quite often it includes "major" packages and that means traversal
> of a significant portion of the portage.., but the leafs representing
> uncommon packages are not touched, that I agree on.
> Thus the more efficient approach (and I had a few thoughts on this,
> although without much detail, so didn't document it :)) would be to operate
> on a memory-mapped cache and on startup suck into memory only the entries
> having weight above certain threshold. Weights should probably be
> proportional to the numbers of dependencies *coming into* the
> correpsponding package. Thus commonly used stuff gets read and the
> traversals are instantaneous, but 99% of the tree just sits on disk
> waitning to be called for...

That would be an option for one cache module. However with modules it would 
also be easy to not use caching at all ;-)

Paul

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