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

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

> -----Original Message-----
> From: Jan Beulich [mailto:JBeulich@suse.com]
> Sent: 06 January 2016 08:53
> To: Zhang Yu
> Cc: Andrew Cooper; Paul Durrant; Wei Liu; Ian Jackson; Stefano Stabellini;
> Kevin Tian; zhiyuan.lv@intel.com; Shuai Ruan; xen-devel@lists.xen.org; Keir
> (Xen.org)
> Subject: Re: [Xen-devel] [V9 2/3] Refactor rangeset structure for better
> performance.
> 
> >>> 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?

  Paul

> Jan