[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 31.12.15 at 10:33, <yu.c.zhang@xxxxxxxxxxxxxxx> wrote:
> 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
>>> introduced.
>> 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. :)

I don't follow: Patch 3 makes things worse resource consumption
wise, not better.


Xen-devel mailing list



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