Re: [Xen-devel] [PATCH 08 of 10 v2] libxl: enable automatic placement of guests on NUMA nodes

[Ian Jackson <Ian.Jackson@xxxxxxxxxxxxx>]

George Dunlap writes ("Re: [Xen-devel] [PATCH 08 of 10 v2] libxl: enable 
automatic placement of guests on NUMA nodes"):
> The only potential concern is that it seems likely that your
> comparison function above will not actually generate an ordering,
> because the relationship it generates isn't transitive.  That is, you
> could have a situation where A > B, B > C, but C > A.  For example:
> A: freemem 1000, domains 1
> B: freemem 1090, domains 2
> C: freemem 1110, domains 3
> 
> In this case, A>B, because memory is within 10% but has fewer domains.
>  B > C, because B is within 10%, and has fewer domains.  But C > A,
> because C has more than 10% more memory than A (so its domains are not
> counted against it).

The conventional approach to this kind of thing is to invent a score
for sorting etc.  Something like
    score = tuning_parameter * log(freemem) - number_of_domains
which does sort of roughly the same as your 10% rule if you squint.

Or maybe you want to take the log of the number_of_domains too, which
would be equivalent for sorting to
    score = freemem / (number_of_domains + other_tuning_parameter)

>  This may give you strange results from your quicksort.  But it's
> likely to give something *reasonable* anyway.  (And if it turns out to
> cause problems, a bubble sort shouldn't be too expensive and will
> likely to be more robust against this kind of quirkiness.)

The behaviour of sorting functions when giving broken comparison
functions may be entirely arbitrary and is not guaranteed to be
anything near the plausible intended orderings.  If you're using qsort
you're not guaranteed that any particular algorithm will be used, so
you can't make any assumptions about its behaviour in this case.

Ian.

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