From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 24820 invoked by uid 1002); 6 Dec 2003 08:27:27 -0600 Mailing-List: contact gentoo-portage-dev-help@gentoo.org; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail Reply-To: gentoo-portage-dev@gentoo.org X-BeenThere: gentoo-portage-dev@gentoo.org Received: (qmail 25254 invoked from network); 6 Dec 2003 08:27:27 -0600 From: Paul de Vrieze To: gentoo-portage-dev@gentoo.org Date: Sat, 6 Dec 2003 15:26:32 +0100 User-Agent: KMail/1.5.4 References: <200312050158.17479.george@gentoo.org> <200312051326.47191.pauldv@gentoo.org> <200312051333.04801.george@gentoo.org> In-Reply-To: <200312051333.04801.george@gentoo.org> MIME-Version: 1.0 Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha1; boundary="Boundary-02=_rce0/IOc9zbtGT+"; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200312061526.52187.pauldv@gentoo.org> X-Spam-Status: No, hits=-9.4 required=5.0 tests=BAYES_01,EMAIL_ATTRIBUTION,IN_REP_TO,PGP_SIGNATURE_2, QUOTED_EMAIL_TEXT,REFERENCES,REPLY_WITH_QUOTES, USER_AGENT_KMAIL autolearn=ham version=2.55-uvt6 X-Spam-Checker-Version: SpamAssassin 2.55-uvt6 (1.174.2.19-2003-05-19-exp) X-Virus-Scanned: by AMaViS-ng (Milter interface) Subject: Re: [gentoo-portage-dev] portage-ng concurse entry Was: Updated Portage project page X-Archives-Salt: 8ac7c035-2b70-40b6-973f-352e8c9742cf X-Archives-Hash: 7dee3aad367b6ac4310d3cf9beda5483 --Boundary-02=_rce0/IOc9zbtGT+ Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Content-Description: signed data Content-Disposition: inline On Friday 05 December 2003 22:33, George Shapovalov wrote: > > Shouldn't it be breadth-first? With depth first you might need to do > adjustments to the formed list occasionally, if multiple nodes go to the > same dependency in a different number of steps. I think I was able to > produce the example of such situation, but I would appreciate any good > pointers to a theory :). Prolog interpreters work as depth-first searchers. Breath-first is in most= =20 cases a waste of both memory and clock cycles. In the case of portage this= =20 would mean something like first getting deep dependencies like glibc, and=20 then less important ones. Of course a full dependency tree for portage is a= =20 bit more complicated than just a graph, anyway that is implementation. > Well, I stated in the writeup that this is a simplistic design only > relevant for the prototype. However I'll try to explain my reasoning for > the future discussions. > (To drobbins: yes, I am afraid we are pulling the "discussion before > requirements" thing again here. But this it the core and unavoidable part > of the design, so it will definitely be there. Also I am trying to locali= ze > the discussion to this list only). I didn't really look at your sourcecode, just at your web-page. > > Thus note, all the comments below concern this hypothetical design I used > in language demonstration, but that will probably be rethought for the re= al > design. > > > While you have a point with your prediction on number of packages, most > > of those packages involve leaf packages. That means that the number of > > dependencies per leaf package will probably not increase. However the > > amount of packages totally not regarded will grow. For this portage > > should do some kind of on-demand loading of packages. I see no need > > whatsoever to have a normal emerge task load in the whole tree and crea= te > > a graph of that. > > 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 ha= ve > to do searches or operations involving world. So I have been thinking alo= ng > 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 significant= ly.=20 In any case more installed packages often also means a beefier computer. > > Touche :). > That's why I spent so many words discussing memory layout. > However the real solution IMHO should allow multiple dependency trackers > (cores) to be plugged as desired (choice of both at compilation and > run-time (i.e. choosing at compilation to be able to choose at run time > :))). And for that we would need a high level of efficient abstraction. A= nd > this is what got me started thinking about Ada :). > We need indeed a highlevel abstraction, and dep trackers are one of the=20 modules. I think that access to the package tree is another, where caching= =20 can be modular too. > 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. > I stay by my thought that any important to the system tool should be dumb. > If there is any uncertainty it should stop and ask, unless it was designed > for a very specific situation, where it can be trusted to make the choice. > Package maintaince is not such area - IMHO every user that has identical > configuration should get identical results (to the extent possible. So he= re > we are talking requirements Daniel ;)). Otherwise we are facing a > disasterous consequencies wil many people complaining and us being unable > to reproduce anything reliably. The only less deterministic behaviour I think is acceptable is in the time = it=20 takes for all dependencies to be calculated, as long as the maximum is=20 sensible. Paul =2D-=20 Paul de Vrieze Gentoo Developer Mail: pauldv@gentoo.org Homepage: http://www.devrieze.net --Boundary-02=_rce0/IOc9zbtGT+ Content-Type: application/pgp-signature Content-Description: signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.2 (GNU/Linux) iD8DBQA/0ecrbKx5DBjWFdsRAkS7AJ48fkmXOGp6s/aLDdN5GHU9hxWaZwCdH75r JpPP9fYXkhsUR0Dje5NLYSE= =S2Fl -----END PGP SIGNATURE----- --Boundary-02=_rce0/IOc9zbtGT+--