1 |
On Friday 05 December 2003 22:33, George Shapovalov wrote: |
2 |
> |
3 |
> Shouldn't it be breadth-first? With depth first you might need to do |
4 |
> adjustments to the formed list occasionally, if multiple nodes go to the |
5 |
> same dependency in a different number of steps. I think I was able to |
6 |
> produce the example of such situation, but I would appreciate any good |
7 |
> pointers to a theory :). |
8 |
|
9 |
Prolog interpreters work as depth-first searchers. Breath-first is in most |
10 |
cases a waste of both memory and clock cycles. In the case of portage this |
11 |
would mean something like first getting deep dependencies like glibc, and |
12 |
then less important ones. Of course a full dependency tree for portage is a |
13 |
bit more complicated than just a graph, anyway that is implementation. |
14 |
|
15 |
> Well, I stated in the writeup that this is a simplistic design only |
16 |
> relevant for the prototype. However I'll try to explain my reasoning for |
17 |
> the future discussions. |
18 |
> (To drobbins: yes, I am afraid we are pulling the "discussion before |
19 |
> requirements" thing again here. But this it the core and unavoidable part |
20 |
> of the design, so it will definitely be there. Also I am trying to localize |
21 |
> the discussion to this list only). |
22 |
|
23 |
I didn't really look at your sourcecode, just at your web-page. |
24 |
|
25 |
> |
26 |
> Thus note, all the comments below concern this hypothetical design I used |
27 |
> in language demonstration, but that will probably be rethought for the real |
28 |
> design. |
29 |
> |
30 |
> > While you have a point with your prediction on number of packages, most |
31 |
> > of those packages involve leaf packages. That means that the number of |
32 |
> > dependencies per leaf package will probably not increase. However the |
33 |
> > amount of packages totally not regarded will grow. For this portage |
34 |
> > should do some kind of on-demand loading of packages. I see no need |
35 |
> > whatsoever to have a normal emerge task load in the whole tree and create |
36 |
> > a graph of that. |
37 |
> |
38 |
> I somewhat agree with that. However my observation is that these packages |
39 |
> most often are libraries or other helpers that user is usualy not |
40 |
> interested in directly. And the long operations are the ones where you have |
41 |
> to do searches or operations involving world. So I have been thinking along |
42 |
> the lines of making the longest operations fast and bounded, getting the |
43 |
> O(1) |
44 |
> responsivity. |
45 |
> But in reality I do not think this shpould be "the ultimate solution" or |
46 |
> even that there should be one. See the next one. |
47 |
|
48 |
I don't believe that the average size of world is going to grow significantly. |
49 |
In any case more installed packages often also means a beefier computer. |
50 |
|
51 |
> |
52 |
> Touche :). |
53 |
> That's why I spent so many words discussing memory layout. |
54 |
> However the real solution IMHO should allow multiple dependency trackers |
55 |
> (cores) to be plugged as desired (choice of both at compilation and |
56 |
> run-time (i.e. choosing at compilation to be able to choose at run time |
57 |
> :))). And for that we would need a high level of efficient abstraction. And |
58 |
> this is what got me started thinking about Ada :). |
59 |
> |
60 |
We need indeed a highlevel abstraction, and dep trackers are one of the |
61 |
modules. I think that access to the package tree is another, where caching |
62 |
can be modular too. |
63 |
|
64 |
|
65 |
> And finally: |
66 |
> > My biggest concern when reading your small paper is that you chose a |
67 |
> > deterministic approach to this problem, while in fact the problem is |
68 |
> > non-determinisitic. |
69 |
> |
70 |
> Could you please elaborate? I am afraid we are thinking about slightly |
71 |
> different things here. |
72 |
> |
73 |
I didn't write that, guess you'll need to ask the person who did. |
74 |
|
75 |
> I stay by my thought that any important to the system tool should be dumb. |
76 |
> If there is any uncertainty it should stop and ask, unless it was designed |
77 |
> for a very specific situation, where it can be trusted to make the choice. |
78 |
> Package maintaince is not such area - IMHO every user that has identical |
79 |
> configuration should get identical results (to the extent possible. So here |
80 |
> we are talking requirements Daniel ;)). Otherwise we are facing a |
81 |
> disasterous consequencies wil many people complaining and us being unable |
82 |
> to reproduce anything reliably. |
83 |
|
84 |
The only less deterministic behaviour I think is acceptable is in the time it |
85 |
takes for all dependencies to be calculated, as long as the maximum is |
86 |
sensible. |
87 |
|
88 |
Paul |
89 |
|
90 |
-- |
91 |
Paul de Vrieze |
92 |
Gentoo Developer |
93 |
Mail: pauldv@g.o |
94 |
Homepage: http://www.devrieze.net |