From mboxrd@z Thu Jan 1 00:00:00 1970 From: Paul Durrant Subject: Re: [V9 2/3] Refactor rangeset structure for better performance. Date: Wed, 6 Jan 2016 10:14:51 +0000 Message-ID: <8325fe8737064a3e9cb938df5ac55ca1@AMSPEX02CL03.citrite.net> 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> <5684F662.2000604@linux.intel.com> <568CE40E02000078000C3CDE@prv-mh.provo.novell.com> <03002f0a0e6448ad912f650334facf15@AMSPEX02CL03.citrite.net> <568CF38B02000078000C3D62@prv-mh.provo.novell.com> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Return-path: In-Reply-To: <568CF38B02000078000C3D62@prv-mh.provo.novell.com> Content-Language: en-US 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 , 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)" List-Id: xen-devel@lists.xenproject.org > -----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, wrote: > >> From: Jan Beulich [mailto:JBeulich@suse.com] > >> Sent: 06 January 2016 08:53 > >> >>> On 31.12.15 at 10:33, wrote: > >> > 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. :) > >> > >> 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