From mboxrd@z Thu Jan 1 00:00:00 1970 From: "Yu, Zhang" Subject: Re: [V9 2/3] Refactor rangeset structure for better performance. Date: Thu, 31 Dec 2015 17:33:22 +0800 Message-ID: <5684F662.2000604@linux.intel.com> References: <1450145110-2860-1-git-send-email-shuai.ruan@linux.intel.com> <1450145110-2860-3-git-send-email-shuai.ruan@linux.intel.com> <56781CFC02000078000C1F14@prv-mh.provo.novell.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; Format="flowed" Content-Transfer-Encoding: 7bit Return-path: In-Reply-To: <56781CFC02000078000C1F14@prv-mh.provo.novell.com> List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , Sender: xen-devel-bounces@lists.xen.org Errors-To: xen-devel-bounces@lists.xen.org To: Jan Beulich , Shuai Ruan Cc: kevin.tian@intel.com, wei.liu2@citrix.com, stefano.stabellini@eu.citrix.com, andrew.cooper3@citrix.com, ian.jackson@eu.citrix.com, xen-devel@lists.xen.org, Paul.Durrant@citrix.com, zhiyuan.lv@intel.com, keir@xen.org List-Id: xen-devel@lists.xenproject.org On 12/21/2015 10:38 PM, Jan Beulich wrote: >>>> On 15.12.15 at 03:05, 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 >