From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:53963) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1fE8OF-0006ca-9w for qemu-devel@nongnu.org; Thu, 03 May 2018 03:10:56 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1fE8OB-0002Gc-73 for qemu-devel@nongnu.org; Thu, 03 May 2018 03:10:55 -0400 Received: from mx3-rdu2.redhat.com ([66.187.233.73]:58848 helo=mx1.redhat.com) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1fE8OB-0002GJ-2i for qemu-devel@nongnu.org; Thu, 03 May 2018 03:10:51 -0400 Date: Thu, 3 May 2018 15:10:41 +0800 From: Peter Xu Message-ID: <20180503071041.GC2378@xz-mi> References: <20180425045129.17449-1-peterx@redhat.com> <20180425045129.17449-8-peterx@redhat.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline In-Reply-To: Subject: Re: [Qemu-devel] [PATCH 07/10] util: implement simple interval tree logic List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Jason Wang Cc: qemu-devel@nongnu.org, "Michael S . Tsirkin" , Alex Williamson , Jintack Lim On Fri, Apr 27, 2018 at 01:53:35PM +0800, Jason Wang wrote: [...] > > +int it_tree_remove(ITTree *tree, ITValue start, ITValue end) > > +{ > > + ITRange range = { .start = start, .end = end }, *overlap, and; > > + GTree *gtree; > > + > > + g_assert(tree); > > + > > + gtree = tree->tree; > > + while ((overlap = g_tree_lookup(gtree, &range))) { > > + if (it_range_equal(overlap, &range)) { > > + /* Exactly what we want to remove; done */ [1] > > + g_tree_remove(gtree, overlap); > > + break; > > + } else if (it_range_cover(overlap, &range)) { [2] > > + /* Split existing range into two; done */ > > + it_tree_remove_subset(gtree, overlap, &range); > > + break; > > + } else if (it_range_cover(&range, overlap)) { [3] > > + /* Drop this range and continue */ > > + g_tree_remove(gtree, overlap); > > + } else { [4] > > + /* > > + * The range to remove has intersection with existing > > + * ranges. Remove part of the range and continue > > + */ > > + it_range_and(&and, overlap, &range); > > + g_assert(and.start <= and.end); > > + it_tree_remove_subset(gtree, overlap, &and); > > + } > > + } > > + > > Looks like what we need here is just calculate the intersection part the > remove it. Here after a second thought, I am thining whether it'll be good I use a general routine in [4] to replace all [1-4]. The problem is that if we do that we'll depend on the next g_tree_lookup() to detect case [1-2] (in that case we'll find nothing in the lookup, but still we'll need to walk the tree) to break the loop, while IMHO that sometimes can be more expensive than the if clauses, especially when the tree is a bit large (each branch needs a if clause actually) and also note that in our use case we really have lots of cases for [1] and [2]. I think I can merge [3] into [4], but I might consider keeping [1] and [2] since I don't really know whether merging them would be better. Anyway we can do that as follow up enhancement after the series merged. But I think we'll need some performance benchmarks. Jason, what do you think? Regards, -- Peter Xu