Gentoo Archives: gentoo-portage-dev

From: George Shapovalov <george@g.o>
To: gentoo-portage-dev@g.o
Subject: Re: [gentoo-portage-dev] portage-ng concurse entry Was: Updated Portage project page
Date: Fri, 05 Dec 2003 15:31:51
Message-Id: 200312051333.04801.george@gentoo.org
In Reply to: Re: [gentoo-portage-dev] portage-ng concurse entry Was: Updated Portage project page by Paul de Vrieze
1 I'll answer this one as this seems a bit more substantial and I would really
2 like to keep the discussion on this list.
3
4 On Friday 05 December 2003 04:26, Paul de Vrieze wrote:
5 > Prolog != AI
6 > AI != undeterministic
7 Quite often these are synonimous (or were, when I was looking into this. But I
8 must admit this was quite some time ago), but strictly speaking you are
9 right. I'll update that section of the page.
10
11 > prolog is very good at graph traversal tasks (which is what AI in many
12 > cases involves and why in AI prolog is used a lot) as the mode of operation
13 > is basically a depth-first backtracking search algorithm (about 10 lines of
14 > pseudocode). For that reason I think it is a good candidate for the new and
15 > improved dependency algorithm.
16 Shouldn't it be breadth-first? With depth first you might need to do
17 adjustments to the formed list occasionally, if multiple nodes go to the same
18 dependency in a different number of steps. I think I was able to produce the
19 example of such situation, but I would appreciate any good pointers to a
20 theory :).
21
22 As fot the lines of code, that's anecdotal.
23 (adding from the other email:)
24 > Also, your code (which is about 1000 lines long)
25 > does -only- a simple dfs and topological ordering, while I can do the
26 > same in about 10 lines in prolog and have backtracking for free. I
27
28 The *traversal* code (btw I use BFS traversal there, not DFS) is completely
29 localized in bc-graphs-directed-bfs_traverse.adb and is about the same 10
30 lines :) and is completely generic.
31 The rest of 990 lines deal with such mundane tasks as reading the (possibly
32 misformed) ebuilds and dealing with user (inluding minimalistic help).
33 Essentially just doing what you describe here:
34
35 > While prolog is very good for such tasks I don't think it is suited to
36 > implement the core of portage. This is not because I think prolog is a
37 > problem, it is because I think that such languages are not suited for
38 > procedural dispatch, divide, etc. tasks. That is something that C is good
39
40
41 > Then about caching
42 Well, I stated in the writeup that this is a simplistic design only relevant
43 for the prototype. However I'll try to explain my reasoning for the future
44 discussions.
45 (To drobbins: yes, I am afraid we are pulling the "discussion before
46 requirements" thing again here. But this it the core and unavoidable part of
47 the design, so it will definitely be there. Also I am trying to localize the
48 discussion to this list only).
49
50 Thus note, all the comments below concern this hypothetical design I used in
51 language demonstration, but that will probably be rethought for the real
52 design.
53
54 > While you have a point with your prediction on number of packages, most of
55 > those packages involve leaf packages. That means that the number of
56 > dependencies per leaf package will probably not increase. However the
57 > amount of packages totally not regarded will grow. For this portage should
58 > do some kind of on-demand loading of packages. I see no need whatsoever to
59 > have a normal emerge task load in the whole tree and create a graph of
60 > that.
61 I somewhat agree with that. However my observation is that these packages most
62 often are libraries or other helpers that user is usualy not interested in
63 directly. And the long operations are the ones where you have to do searches
64 or operations involving world. So I have been thinking along the lines of
65 making the longest operations fast and bounded, getting the O(1)
66 responsivity.
67 But in reality I do not think this shpould be "the ultimate solution" or even
68 that there should be one. See the next one.
69
70 > I would like portage to remain lean and mean. I do run gentoo on a 16MB
71 > 60mhz pentium, and I like it. While the cache should also be a module that
72 > replaces a direct-tree-read module (possibly wrapping it), I think that
73 > caching should be possible on a configurable level. Not just dumbly load in
74 > all ebuilds.
75 Touche :).
76 That's why I spent so many words discussing memory layout.
77 However the real solution IMHO should allow multiple dependency trackers
78 (cores) to be plugged as desired (choice of both at compilation and run-time
79 (i.e. choosing at compilation to be able to choose at run time :))). And for
80 that we would need a high level of efficient abstraction. And this is what
81 got me started thinking about Ada :).
82
83
84 And finally:
85 > My biggest concern when reading your small paper is that you chose a
86 > deterministic approach to this problem, while in fact the problem is
87 > non-determinisitic.
88 Could you please elaborate? I am afraid we are thinking about slightly
89 different things here.
90
91 I stay by my thought that any important to the system tool should be dumb. If
92 there is any uncertainty it should stop and ask, unless it was designed for a
93 very specific situation, where it can be trusted to make the choice. Package
94 maintaince is not such area - IMHO every user that has identical
95 configuration should get identical results (to the extent possible. So here
96 we are talking requirements Daniel ;)). Otherwise we are facing a disasterous
97 consequencies wil many people complaining and us being unable to reproduce
98 anything reliably.
99
100 George
101
102
103
104 --
105 gentoo-portage-dev@g.o mailing list

Replies