Re: [Qemu-devel] [PATCH 07/10] util: implement simple interval tree logic

[Peter Xu]

On Thu, May 03, 2018 at 03:21:13PM +0800, Jason Wang wrote:
> 
> 
> On 2018年05月03日 15:10, Peter Xu wrote:
> > 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,
> > 
> 
> Sounds good (but I don't promise I won't have new comments :))

Sure!  I suppose that's why we post patches - we let people see so
that one can leave comments. :)

-- 
Peter Xu