From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 17071 invoked by uid 1002); 7 Dec 2003 05:19:05 -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 2323 invoked from network); 7 Dec 2003 05:19:05 -0600 From: Paul de Vrieze To: gentoo-portage-dev@gentoo.org Date: Sun, 7 Dec 2003 12:18:52 +0100 User-Agent: KMail/1.5.4 References: <200312050158.17479.george@gentoo.org> <200312061526.52187.pauldv@gentoo.org> <200312061500.03882.george@gentoo.org> In-Reply-To: <200312061500.03882.george@gentoo.org> MIME-Version: 1.0 Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha1; boundary="Boundary-02=_kyw0/x6iI+s64xT"; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Message-Id: <200312071219.00253.pauldv@gentoo.org> X-Spam-Status: No, hits=-8.7 required=5.0 tests=BAYES_10,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: d2101b3e-9664-44e0-a3af-ed3350ea2756 X-Archives-Hash: 86232e84b644ee25f1d79c81926974bd --Boundary-02=_kyw0/x6iI+s64xT Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Content-Description: signed data Content-Disposition: inline On Sunday 07 December 2003 00:00, George Shapovalov wrote: > 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. It is pretty trivial to get whatever behaviour you want in prolog for your= =20 problem. The program does not need to follow the way prolog parses your=20 language statements. > > > 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. > I don't think there is a significance in breath of depth first here (breath= =20 first has the same problems with changing deps as depth) as the whole tree= =20 needs to be created/walked anyway. (I first thought you were thinking of th= e=20 tree of all available ebuilds). If you use prolog, probably depth-first is= =20 easier. > 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 simil= ar > 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 examp= le > (and not explicitly included, say because it is consdered "basic")). One can easilly create a virtual glibc dependency for all ebuilds. Then as = all=20 ebuilds depend on it it would come first in the flattened vectror result. > 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 opera= te > 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... That would be an option for one cache module. However with modules it would= =20 also be easy to not use caching at all ;-) Paul =2D-=20 Paul de Vrieze Gentoo Developer Mail: pauldv@gentoo.org Homepage: http://www.devrieze.net --Boundary-02=_kyw0/x6iI+s64xT Content-Type: application/pgp-signature Content-Description: signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.2 (GNU/Linux) iD8DBQA/0wykbKx5DBjWFdsRAtHSAJ4jdOaJeWohxMUMsRYulI8Go1dQeQCg5R3B R+FxTJBpDg9UW5+BXoUEiWY= =ymMT -----END PGP SIGNATURE----- --Boundary-02=_kyw0/x6iI+s64xT--