Re: [PATCH 1 of 3 v5/leftover] libxl: enable automatic placement of guests on NUMA nodes [and 1 more messages]

[Ian Jackson <Ian.Jackson@eu.citrix.com>]

Dario Faggioli writes ("[PATCH 1 of 3 v5/leftover] libxl: enable automatic placement of guests on NUMA nodes"):
> If a domain does not have a VCPU affinity, try to pin it
> automatically to some PCPUs. This is done taking into account the
> NUMA characteristics of the host.  In fact, we look for a
> combination of host's NUMA nodes with enough free memory and number
> of PCPUs for the new domain, and pin it to the VCPUs of those nodes.

Ian Jackson writes ("Re: [PATCH 1 of 3 v4/leftover] libxl: enable automatic placement of guests on NUMA nodes"):
...
> This part of the algorithm is quadratic in the number of combinations
> divided by the number of nodes.  So the algorithm is
>    O( (  C( nr_nodes, min_nodes ) / min_nodes  )^2 )
> which is quite bad really.
> 
> At the very least this needs to be an exponential allocation, eg
>   +                array_size += nr_nodes + array_size;
> 
> But if you didn't insist on creating the whole list and sorting it,
> you would avoid this allocation entirely, wouldn't you ?
> 
> Should we bve worried that this algorithm will be too slow even if it
> involves just
>   O( C(nr_nodes,min_nodes) )
> iterations ?

I've been told that boxes with 16 NUMA nodes are coming out about
now.

This algorithm will start to have unreasonable performance with
anything bigger than that.  Eg choosing 16 NUMA nodes out of 32 would
involve searching 601,080,390 combinations.  32 out of 64 gives 10^18.

So I think we need a different approach :-(.

Ian.