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

[Paul Durrant <Paul.Durrant@citrix.com>]

> -----Original Message-----
> From: xen-devel-bounces@lists.xen.org [mailto:xen-devel-
> bounces@lists.xen.org] On Behalf Of Jan Beulich
> Sent: 06 January 2016 09:59
> To: Paul Durrant; Zhang Yu
> Cc: Kevin Tian; Wei Liu; Shuai Ruan; Andrew Cooper; xen-
> devel@lists.xen.org; Stefano Stabellini; zhiyuan.lv@intel.com; Ian Jackson;
> Keir (Xen.org)
> Subject: Re: [Xen-devel] [V9 2/3] Refactor rangeset structure for better
> performance.
> 
> >>> On 06.01.16 at 10:46, <Paul.Durrant@citrix.com> wrote:
> >> From: Jan Beulich [mailto:JBeulich@suse.com]
> >> Sent: 06 January 2016 08:53
> >> >>> On 31.12.15 at 10:33, <yu.c.zhang@linux.intel.com> wrote:
> >> > On 12/21/2015 10:38 PM, Jan Beulich wrote:
> >> >>>>> On 15.12.15 at 03:05, <shuai.ruan@linux.intel.com> 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.
>

Sounds like the way to go then :-)

  Paul
 
> Jan
> 
> 
> _______________________________________________
> Xen-devel mailing list
> Xen-devel@lists.xen.org
> http://lists.xen.org/xen-devel