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

[George Shapovalov]

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.

> 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.
And then it gives:

> would mean something like first getting deep dependencies like glibc, and
> then less important ones.
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")).



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


> > 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.
Um, sorry, I somehow got confused and thought some postings on -dev were from 
you as well. I just sent relevant parts to proper place :).

George



--
gentoo-portage-dev@g.o mailing list