1 |
On Sunday 07 December 2003 00:00, George Shapovalov wrote: |
2 |
> I have been thinking a bit more about dfs vs bfs traversals, so here goes |
3 |
> :). |
4 |
> |
5 |
> On Saturday 06 December 2003 06:26, Paul de Vrieze wrote: |
6 |
> > Prolog interpreters work as depth-first searchers. Breath-first is in |
7 |
> > most |
8 |
> |
9 |
> Yea, and unfortunately there isn't much choice about it as recursion is |
10 |
> pretty much the only composition method the standard talks. |
11 |
|
12 |
It is pretty trivial to get whatever behaviour you want in prolog for your |
13 |
problem. The program does not need to follow the way prolog parses your |
14 |
language statements. |
15 |
|
16 |
> |
17 |
> > cases a waste of both memory and clock cycles. In the case of portage |
18 |
> > this |
19 |
> |
20 |
> Its really only O(n) where small n stands for associated dependencies, so |
21 |
> that's not that much. Besides it does nopt require recursion to be |
22 |
> implemented, so in reality that hit quite often is not even there. |
23 |
> |
24 |
I don't think there is a significance in breath of depth first here (breath |
25 |
first has the same problems with changing deps as depth) as the whole tree |
26 |
needs to be created/walked anyway. (I first thought you were thinking of the |
27 |
tree of all available ebuilds). If you use prolog, probably depth-first is |
28 |
easier. |
29 |
|
30 |
> And isn't this the "right" way to do it? Surely operating on a *complete* |
31 |
> portage tree, that is the one where all the dependencies are explicitly |
32 |
> stated, that wouldn't make any difference. But in reality glibc and similar |
33 |
> dependencies, being a part of the system, are omitted in pretty much all |
34 |
> ebuilds. Thus, with DFS traversal (which is what portage does now) one is |
35 |
> getting glibc somewhere in the middle of world update quite often, which is |
36 |
> not optimal if you want complete coherency (and it can be plain bad in the |
37 |
> case of the major update. This is somewhat alleviated in our case for |
38 |
> system packages by a mandatory bootstrap, but some stuff on perifery can be |
39 |
> hit, if multiple things use the same library and it is affected for example |
40 |
> (and not explicitly included, say because it is consdered "basic")). |
41 |
|
42 |
One can easilly create a virtual glibc dependency for all ebuilds. Then as all |
43 |
ebuilds depend on it it would come first in the flattened vectror result. |
44 |
|
45 |
> No, but quite often it includes "major" packages and that means traversal |
46 |
> of a significant portion of the portage.., but the leafs representing |
47 |
> uncommon packages are not touched, that I agree on. |
48 |
> Thus the more efficient approach (and I had a few thoughts on this, |
49 |
> although without much detail, so didn't document it :)) would be to operate |
50 |
> on a memory-mapped cache and on startup suck into memory only the entries |
51 |
> having weight above certain threshold. Weights should probably be |
52 |
> proportional to the numbers of dependencies *coming into* the |
53 |
> correpsponding package. Thus commonly used stuff gets read and the |
54 |
> traversals are instantaneous, but 99% of the tree just sits on disk |
55 |
> waitning to be called for... |
56 |
|
57 |
That would be an option for one cache module. However with modules it would |
58 |
also be easy to not use caching at all ;-) |
59 |
|
60 |
Paul |
61 |
|
62 |
-- |
63 |
Paul de Vrieze |
64 |
Gentoo Developer |
65 |
Mail: pauldv@g.o |
66 |
Homepage: http://www.devrieze.net |