From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from lists.gentoo.org ([140.105.134.102] helo=robin.gentoo.org) by nuthatch.gentoo.org with esmtp (Exim 4.43) id 1E7cWW-0001B0-KR for garchives@archives.gentoo.org; Tue, 23 Aug 2005 17:25:21 +0000 Received: from robin.gentoo.org (localhost [127.0.0.1]) by robin.gentoo.org (8.13.4/8.13.4) with SMTP id j7NHMaVk016787; Tue, 23 Aug 2005 17:22:36 GMT Received: from smtp.gentoo.org (smtp.gentoo.org [134.68.220.30]) by robin.gentoo.org (8.13.4/8.13.4) with ESMTP id j7NHJjlj028135 for ; Tue, 23 Aug 2005 17:19:46 GMT Received: from cpe-65-26-255-237.wi.res.rr.com ([65.26.255.237] helo=nightcrawler) by smtp.gentoo.org with esmtpa (Exim 4.43) id 1E7cRw-00017X-NJ; Tue, 23 Aug 2005 17:20:37 +0000 Date: Tue, 23 Aug 2005 12:19:21 -0500 From: Brian Harring To: gentoo-dev@lists.gentoo.org Cc: pvdabeel@gentoo.org Subject: Re: [gentoo-dev] RFC - Gentoo on the Lab Message-ID: <20050823171921.GL10816@nightcrawler> References: <20050822025840.6bb9bdb9@acme.rjlouro.org> <20050822163811.3dcc8fde@andy.genone.homeip.net> <1124732954.6502.61.camel@localhost> <20050822214135.6b916221@localhost> <1124814488.6502.154.camel@localhost> Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-dev@gentoo.org Reply-to: gentoo-dev@lists.gentoo.org Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="Zll6mx50Q8J7qlLQ" Content-Disposition: inline In-Reply-To: <1124814488.6502.154.camel@localhost> User-Agent: Mutt/1.5.8i X-Archives-Salt: 6c5c66cc-e767-4373-88f8-4f94cbf5e9f0 X-Archives-Hash: 270777972e3ddf61f8ca7201df6883f3 --Zll6mx50Q8J7qlLQ Content-Type: text/plain; charset=utf8 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Lot of text left inline, pardon, just scroll and deal with it :P On Tue, Aug 23, 2005 at 12:28:08PM -0400, Kristian Benoit wrote: > Here is my recent communication with Pieter: >=20 > On Sat, 2005-08-13 at 21:59 +0200, Pieter Van den Abeele wrote:=20 > > On 13 Aug 2005, at 19:16, Kristian Benoit wrote: > >=20 > > > I've heard that you might be the last to know something about > > > portage-ng. What's the actual status, > >=20 > > Here's what I've done so far: > >=20 > > I've build upon Andreas' Zeller idea of using Smolka's feature logic = =20 > > for software configuration management. Zeller's approach was ok for =20 > > determining consistency/inconsistency of software configurations. In = =20 > > his phd thesis he described the algorithm involved and discussed time = =20 > > complexity (which goes to NP if you allow for quantification). My =20 > > impression after implementing his idea was that for automated =20 > > construction there were a few things that were lacking, and some =20 > > things were incorrect. I revisited Zellers feature logic, and ended =20 > > up with a clean implementation of a declarative language which has =20 > > some very desirable properties for automated software construction. =20 > > I'd say my approach is closer to the spirit of Smolka's feature logic = =20 > > than Zellers approach. My non-destructive feature unification has a =20 > > worst case time complexity of O(n x m) where n is the length of the =20 > > feature term describing your system, and m is the length of the =20 > > feature term describing the component to be added. In practice =20 > > performance is very good. An emerge --vp --emptytree kde with the =20 > > regular portage takes about 55 seconds on my Open Desktop Workstation = =20 > > and produces a list of 200 packages. A similar action using my =20 > > implementation: > >=20 > > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > Total time: 14.55 seconds > > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > Predicate Box Entries =3D Calls+Redos Time > > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > vunify/4 341,900 =3D 341,900+0 72.6% > > $garbage_collect/1 326 =3D 326+0 13.6% > > lists:append/3 684,320 =3D 684,320+0 4.0% > > genterm/2 520 =3D 520+0 3.9% > > hunify/4 520 =3D 520+0 3.3% > > is/2 342,420 =3D 342,420+0 1.8% > > >/2 342,160 =3D 342,160+0 0.8% > > buildsystem/2 1 =3D 1+0 0.0% > > val/3 5,200 =3D 5,200+0 0.0% > > unify/3 260 =3D 260+0 0.0% > >=20 > > % 9,531,861 inferences, 13.96 CPU in 14.55 seconds (96% CPU, 682798 =20 > > Lips) Stating it as nicely as possible, without knowing what that's doing,=20 stats can be construed several ways; faster backend access (both vdb=20 and ebuild/cache), dodging/caching virtuals, etc; language=20 implementation is a point of curiousity also. Faster implementation doesn't surprise me- stable portage is fricking=20 *absolutely* retarded about caching, parsing of deps and cpvs, loading=20 of profile, etc. Either way, interest remains in seeing it :) > > The search space is kept as small as possible because I've introduced = =20 > > lazy feature evaluation and both multi valued and open features. =20 > > Those concepts are missing in Zellers approach. Comparing current =20 > > portage and my implementation performance-wise is difficult. In =20 > > general mine is faster, but current portage doesn't use sql either. =20 > > What is for sure is that mine allows you to express various =20 > > constraints. You can prevent a dependency from being built with a =20 > > specific use flag. My implementation automatically solves 'blockers'. = =20 > > Circular dependencies are also solved correctly. For instance, if you = =20 > > want to install unixodbc with the qt use flag enabled and you want to = =20 > > install qt wit the unixodbc use flag enabled, my portage knows that =20 > > it needs to: > >=20 > > emerge unixodbc without qt > > emerge qt with unixodbc > > remerge unixodbc with qt support > >=20 > > So it makes revdep-rebuild unnecessary basically. revdep-rebuild is still necessary, regardless of use deps or full=20 state graphs- anyone doubting that should take a look at the breakage=20 that has occured whenever mysql/ssl have decided to change their=20 soname while maintaining compatibility. Need a bincompat metadata attribute to kill off revdep-rebuild. > > Once I was done implementing this new declarative language in which =20 > > for instance ebuild concepts can be easily expressed (but also rpm, =20 > > deb, fink, darwinports). This sounds a lot like my restriction subsystem in the rewrite (code's=20 available to anyone after it). With the restriction setup, anyone who wants it could just plugin a=20 different repo/pkg plugin, and have deps based on sonames fex; granted=20 anyone doing it would need some form of a binary repository, but the=20 agnostic aspect of representing matching criteria is the key to it. > > I implemented a knowledge base in which =20 > > those feature terms can be stored/looked up efficiently. I used an =20 > > odbc bridge design pattern and have tested the thing with postgresql/= =20 > > mysql and sqlite. I've also implemented a DCG parser which parses =20 > > ebuilds (no more having to start a bash process for each ebuild like = =20 > > current portage does) Strictly a stable slow down, and relevant when pulling metadata; 2.1=20 (ebd patchset) is a daeonized ebuild processor effectively. Shaves a=20 good 30% off of runtime, while being proper (sans bugs). Alternative implementations welcome of course, but ebd is pretty much=20 something whipped out that addresses long standing bugs without=20 requiring a full rewrite of parsing (interested parties can do it=20 another day, I care not to after filter-env). ~harring --Zll6mx50Q8J7qlLQ Content-Type: application/pgp-signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) iD8DBQFDC1qZvdBxRoA3VU0RAoezAKDE4O70KhHtPAqSpvq31p/3SP0kQACgm3pm JiBUFQJifFqTidLxHWLjU6o= =So8m -----END PGP SIGNATURE----- --Zll6mx50Q8J7qlLQ-- -- gentoo-dev@gentoo.org mailing list