On Thu, Aug 4, 2011 at 4:21 AM, Søren Sandmann <sandm...@cs.au.dk> wrote: > From: Søren Sandmann Pedersen <s...@redhat.com> > > When someone selects some text in Firefox under a non-composited X > server and initiates a drag, a shaped window is created with a complex > shape corresponding to the outline of the text. Then, on every mouse > movement pixman_region_contains_rectangle() is called many times on > that complicated region. And pixman_region_contains_rectangle() is > doing a linear scan through the rectangles in the region, although the > scan does does when it finds the first box that can't possibly > intersect the passed-in rectangle. > > This patch changes the loop so that it begins with a binary search for > the first box that could possibly overlap the passed-in rectangle. > The performance improvement for the text dragging case is easily > noticable. > --- > pixman/pixman-region.c | 44 +++++++++++++++++++++++++++++++++++++++----- > 1 files changed, 39 insertions(+), 5 deletions(-) > > diff --git a/pixman/pixman-region.c b/pixman/pixman-region.c > index 142493b..a199405 100644 > --- a/pixman/pixman-region.c > +++ b/pixman/pixman-region.c > @@ -2086,6 +2086,40 @@ PIXMAN_EXPORT PREFIX (_inverse) (region_type_t > *new_reg, /* Destination region > return TRUE; > } > > +/* In time O(log n), locate the first box whose y2 is greater than y. > + * Return @end if no such box exists. > + */ > +static box_type_t * > +find_box_for_y (box_type_t *begin, box_type_t *end, int y) > +{ > + box_type_t *mid; > + > + if (end == begin) > + return end; > + > + if (end - begin == 1) > + { > + if (begin->y2 > y) > + return begin; > + else > + return end; > + } > + > + mid = begin + (end - begin) / 2; > + if (mid->y2 > y) > + { > + /* If no box is found in [begin, mid], the function > + * will return @mid, which is then known to be the > + * correct answer. > + */ > + return find_box_for_y (begin, mid, y); > + } > + else > + { > + return find_box_for_y (mid, end, y); > + } > +} > + > /* > * rect_in(region, rect) > * This routine takes a pointer to a region and a pointer to a box > @@ -2102,7 +2136,6 @@ PIXMAN_EXPORT PREFIX (_inverse) (region_type_t > *new_reg, /* Destination region > * partially in the region) or is outside the region (we reached a band > * that doesn't overlap the box at all and part_in is false) > */ > - > pixman_region_overlap_t > PIXMAN_EXPORT PREFIX (_contains_rectangle) (region_type_t * region, > box_type_t * prect) > @@ -2137,12 +2170,13 @@ PIXMAN_EXPORT PREFIX (_contains_rectangle) > (region_type_t * region, > x = prect->x1; > y = prect->y1; > > + pbox = PIXREGION_BOXPTR (region); > + pbox_end = pbox + numRects; > + > + pbox = find_box_for_y (pbox, pbox_end, y); > /* can stop when both part_out and part_in are TRUE, or we reach > prect->y2 */ > - for (pbox = PIXREGION_BOXPTR (region), pbox_end = pbox + numRects; > - pbox != pbox_end; > - pbox++) > + for (; pbox != pbox_end; pbox++) > { > - > if (pbox->y2 <= y) > continue; /* getting up to speed or skipping remainder of band */
If this test is not needed anymore, I think it should be deleted, otherwise the documentation of find_box_for_y should be modified. The same objection applies to patch 4/4. Again, some trailing whitespace (both in 3/4 and in 4/4). Andrea > > -- > 1.7.4 > > _______________________________________________ > Pixman mailing list > Pixman@lists.freedesktop.org > http://lists.freedesktop.org/mailman/listinfo/pixman > _______________________________________________ Pixman mailing list Pixman@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/pixman