Re: [Xen-devel] [PATCH 07 of 10 v2] libxl: optimize the calculation of how many VCPUs can run on a candidate

[Dario Faggioli <dario.faggioli@xxxxxxxxxx>]

On Thu, 2012-12-20 at 08:41 +0000, Ian Campbell wrote: 
> On Wed, 2012-12-19 at 19:07 +0000, Dario Faggioli wrote:
> > This reduces the complexity of the overall algorithm, as it moves a 
> 
> What was/is the complexity before/after this change? ISTR it was O(n^2)
> or something along those lines before.
> 
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) = O(2^n_nodes)

Did I answer your question?

Dario

-- 
<<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)

Attachment: signature.asc
Description: This is a digitally signed message part

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