From mboxrd@z Thu Jan  1 00:00:00 1970
From: Dario Faggioli <dario.faggioli@citrix.com>
Subject: Re: [PATCH 07 of 10 v2] libxl: optimize the calculation
 of how many VCPUs can run on a candidate
Date: Thu, 20 Dec 2012 10:24:09 +0100
Message-ID: <1355995449.28419.40.camel@Abyss>
References: <patchbomb.1355944036@Solace>
	<5dc2571ae5faef87977c.1355944043@Solace>
	<1355992906.14417.58.camel@dagon.hellion.org.uk>
Mime-Version: 1.0
Content-Type: multipart/mixed; boundary="===============5230301457008424114=="
Return-path: <xen-devel-bounces@lists.xen.org>
In-Reply-To: <1355992906.14417.58.camel@dagon.hellion.org.uk>
List-Unsubscribe: <http://lists.xen.org/cgi-bin/mailman/options/xen-devel>,
	<mailto:xen-devel-request@lists.xen.org?subject=unsubscribe>
List-Post: <mailto:xen-devel@lists.xen.org>
List-Help: <mailto:xen-devel-request@lists.xen.org?subject=help>
List-Subscribe: <http://lists.xen.org/cgi-bin/mailman/listinfo/xen-devel>,
	<mailto:xen-devel-request@lists.xen.org?subject=subscribe>
Sender: xen-devel-bounces@lists.xen.org
Errors-To: xen-devel-bounces@lists.xen.org
To: Ian Campbell <Ian.Campbell@citrix.com>
Cc: Marcus Granado <Marcus.Granado@eu.citrix.com>, Dan Magenheimer <dan.magenheimer@oracle.com>, Matt Wilson <msw@amazon.com>, Anil Madhavapeddy <anil@recoil.org>, George Dunlap <George.Dunlap@eu.citrix.com>, Andrew Cooper <Andrew.Cooper3@citrix.com>, Juergen Gross <juergen.gross@ts.fujitsu.com>, Ian Jackson <Ian.Jackson@eu.citrix.com>, "xen-devel@lists.xen.org" <xen-devel@lists.xen.org>, Jan Beulich <JBeulich@suse.com>, Daniel De Graaf <dgdegra@tycho.nsa.gov>
List-Id: xen-devel@lists.xenproject.org

--===============5230301457008424114==
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature"; boundary="=-RTIWRx0K03yPaj+ZiJKG"

--=-RTIWRx0K03yPaj+ZiJKG
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Thu, 2012-12-20 at 08:41 +0000, Ian Campbell wrote:=20
> On Wed, 2012-12-19 at 19:07 +0000, Dario Faggioli wrote:
> > This reduces the complexity of the overall algorithm, as it moves a=20
>=20
> What was/is the complexity before/after this change? ISTR it was O(n^2)
> or something along those lines before.
>=20
Yes and no. Let me try to explain. Counting the number of vCPUs that can
run on (a set) of node(s) was and remains O(n_domains*n_domain_vcpus),
so, yes, sort of quadratic.

The upper bound of the number of candidates evaluated by the placement
algorithm is exponential in the number of NUMA nodes: O(2^n_nodes).

Before this change, we counted the number of vCPUs runnable on each
candidate during each step, so the overall complexity was:

O(2^n_nodes) * O(n_domains*n_domain_vcpus)

In this change I count the number of vCPUs runnable on each candidate
only once, and that happens outside the candidate generation loop, so
the overall complexity is:

O(n_domains*n_domains_vcpus) + O(2^n_nodes) =3D O(2^n_nodes)

Did I answer your question?

Dario

--=20
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://retis.sssup.it/people/faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)



--=-RTIWRx0K03yPaj+ZiJKG
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: This is a digitally signed message part
Content-Transfer-Encoding: 7bit

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iEYEABECAAYFAlDS2TkACgkQk4XaBE3IOsSkggCfWp3ZRDxhqXuExeiFytPX8eHN
SasAnjD2tFJLCh0P3tAxd3V7wjZMw36/
=qT7w
-----END PGP SIGNATURE-----

--=-RTIWRx0K03yPaj+ZiJKG--


--===============5230301457008424114==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
http://lists.xen.org/xen-devel

--===============5230301457008424114==--