From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80]) by finch.gentoo.org (Postfix) with ESMTP id E66B21381F3 for ; Sun, 16 Jun 2013 22:20:31 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id D2C36E0929; Sun, 16 Jun 2013 22:20:26 +0000 (UTC) Received: from mail-ee0-f50.google.com (mail-ee0-f50.google.com [74.125.83.50]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id C85BFE08DC for ; Sun, 16 Jun 2013 22:20:25 +0000 (UTC) Received: by mail-ee0-f50.google.com with SMTP id d49so1421146eek.9 for ; Sun, 16 Jun 2013 15:20:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlemail.com; s=20120113; h=date:from:to:subject:message-id:in-reply-to:references:x-mailer :mime-version:content-type; bh=bgJ5ZaNM6TDk58DyfksHMzxAUM6i9rzSckLfGpnfLrQ=; b=SjKUOwltPMwwHwearTY4CtJixw5KnzoGUllkzajSfBVMG1RyvhR1lKsNuIlC/kyb4b JE7kylhtomLzm+j9F978WrTL7SbDnmc5s8DybMJHAMOcOMceP/cmSW4gBZ8gQitrsv6Z 7Wi4PqspkzAsnlFSOd50BI3UyuorylVHqHF8v9FoZufIOZP5XYRL7NpYbUyFMWUv1Q7v jwFJ7QOQ/+n+3dBviTw9RUkevodmGKHsLjbUJGf9rK3/mQ0bcugYYBLs9KXILLYvggPI d5bxUaFcecE3bupMUr9pD7tZbVTno4IpXT7vSdRJppcyv/bom4gxwsorLwLvZpxzDGhG U6EA== X-Received: by 10.15.31.198 with SMTP id y46mr13675796eeu.135.1371421224452; Sun, 16 Jun 2013 15:20:24 -0700 (PDT) Received: from localhost (cpc13-broo7-2-0-cust130.14-2.cable.virginmedia.com. [82.9.16.131]) by mx.google.com with ESMTPSA id b7sm19196882eef.16.2013.06.16.15.20.23 for (version=TLSv1.2 cipher=RC4-SHA bits=128/128); Sun, 16 Jun 2013 15:20:24 -0700 (PDT) Date: Sun, 16 Jun 2013 23:20:19 +0100 From: Ciaran McCreesh To: gentoo-dev@lists.gentoo.org Subject: Re: [gentoo-dev] Re: Packages up for grabs Message-ID: <20130616232019.19d82a6b@googlemail.com> In-Reply-To: <20130617000757.3bb64664@TOMWIJ-GENTOO> References: <1371376191.10717.15.camel@localhost> <1371390923.28535.67.camel@big_daddy.dol-sen.ca> <20130616164445.0c8f8f55@TOMWIJ-GENTOO> <1371402560.28535.79.camel@big_daddy.dol-sen.ca> <1371403298.22480.8.camel@localhost> <20130616202324.45cb3262@TOMWIJ-GENTOO> <20130616232427.063566d4@TOMWIJ-GENTOO> <20130616223856.61345cf3@googlemail.com> <20130617000757.3bb64664@TOMWIJ-GENTOO> X-Mailer: Claws Mail 3.9.0 (GTK+ 2.24.18; x86_64-pc-linux-gnu) Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-dev@lists.gentoo.org Reply-to: gentoo-dev@lists.gentoo.org Mime-Version: 1.0 Content-Type: multipart/signed; micalg=PGP-SHA1; boundary="Sig_/OoChQDSPsqP.Wy0sa5ZGHs7"; protocol="application/pgp-signature" X-Archives-Salt: 8d071c31-53c4-4bd5-b443-a986caec6973 X-Archives-Hash: b459f0b550a6fedcc6772ba33efc445d --Sig_/OoChQDSPsqP.Wy0sa5ZGHs7 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: quoted-printable On Mon, 17 Jun 2013 00:07:57 +0200 Tom Wijsman wrote: > That's assuming you would go threaded, but you can also aim for lower > algorithmic complexities; the complexity makes the CPU the bottleneck. Dependency solving is NP-hard in theory and better than quadratic in practice. The resolution algorithms also aren't the problem in terms of runtime (and still won't be if we started using more sophisticated algorithms for better decision making). The problem is simply that the model is large and messy, and the problem being solved has all kinds of awful corner cases that have to be considered. (As one example, every user has somewhere between a hundred and a thousand packages installed, each of which depends directly or indirectly upon every other package in this collection.) There are certainly improvements to be made, both in terms of efficiency and correctness, but if you're looking for a big leap forward then the most useful thing we could do is reduce or eliminate some of the requirements that make dependency resolution such a fiddly (not hard) problem. --=20 Ciaran McCreesh --Sig_/OoChQDSPsqP.Wy0sa5ZGHs7 Content-Type: application/pgp-signature; name=signature.asc Content-Disposition: attachment; filename=signature.asc -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.20 (GNU/Linux) iEYEARECAAYFAlG+OiYACgkQ96zL6DUtXhE9mgCfVx6TzDTaeAOxFwcOydTVRCAO H6AAoL4RRkB3LJc84qs2vBDa6CB5ikDA =FoQY -----END PGP SIGNATURE----- --Sig_/OoChQDSPsqP.Wy0sa5ZGHs7--