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

["Yu, Zhang" <yu.c.zhang@xxxxxxxxxxxxxxx>]

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. :)

Yu

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