[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] Re: [Xen-devel] [PATCH 07 of 10 v2] libxl: optimize the calculation of how many VCPUs can run on a candidate
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 _______________________________________________ Xen-devel mailing list Xen-devel@xxxxxxxxxxxxx http://lists.xen.org/xen-devel
|
Lists.xenproject.org is hosted with RackSpace, monitoring our |