[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Xen-devel] [V9 2/3] Refactor rangeset structure for better performance.

On 12/21/2015 10:38 PM, Jan Beulich wrote:
On 15.12.15 at 03:05, <shuai.ruan@xxxxxxxxxxxxxxx> wrote:
This patch refactors struct rangeset to base it on the red-black
tree structure, instead of on the current doubly linked list. By
now, ioreq leverages rangeset to keep track of the IO/memory
resources to be emulated. Yet when number of ranges inside one
ioreq server is very high, traversing a doubly linked list could
be time consuming. With this patch, the time complexity for
searching a rangeset can be improved from O(n) to O(log(n)).
Interfaces of rangeset still remain the same, and no new APIs

So this indeed addresses one of the two original concerns. But
what about the other (resource use due to thousands of ranges
in use by a single VM)? IOW I'm still unconvinced this is the way
to go.

Thank you, Jan. As you saw in patch 3/3, the other concern was solved
by extending the rangeset size, which may not be convictive for you.
But I believe this patch - refactoring the rangeset to rb_tree, does
not only solve XenGT's performance issue, but may also be helpful in
the future, e.g. if someday the rangeset is not allocated in xen heap
and can have a great number of ranges in it. :)



Xen-devel mailing list

Xen-devel mailing list



Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.