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

["Jan Beulich" <JBeulich@xxxxxxxx>]

>>> On 06.01.16 at 10:46, <Paul.Durrant@xxxxxxxxxx> wrote:
>> From: Jan Beulich [mailto:JBeulich@xxxxxxxx]
>> Sent: 06 January 2016 08:53
>> >>> 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.
>> 
> 
> Yes, it allows the rangeset to grow larger. Would it be better to tie 
> emulation rangesets to a specific domain and have the rangeset limits defined 
> for the domain by the toolstack?

In fact that's what I had suggested in reply to 3/3 at about the same
time as the mail you've replied to here.

Jan


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