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

["Yu, Zhang" <yu.c.zhang@linux.intel.com>]

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

Yu

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