[Pixman] [PATCH 3/4] Speed up pixman_region{, 32}_contains_rectangle()
Søren Sandmann
sandmann at cs.au.dk
Fri Aug 5 19:26:05 PDT 2011
From: Søren Sandmann Pedersen <ssp at 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 exit when it finds the first box that can't possibly
intersect the passed-in rectangle.
This patch changes the loop so that it uses a binary search to skip
boxes that don't overlap the current y position. The performance
improvement for the text dragging case is easily noticable.
V2: Use the binary search for the "getting up to speed or skippping
remainder of band" as well.
---
pixman/pixman-region.c | 48 ++++++++++++++++++++++++++++++++++++++++++------
1 files changed, 42 insertions(+), 6 deletions(-)
diff --git a/pixman/pixman-region.c b/pixman/pixman-region.c
index 142493b..71995fd 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)
@@ -2139,12 +2172,15 @@ PIXMAN_EXPORT PREFIX (_contains_rectangle) (region_type_t * region,
/* 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++)
+ pbox != pbox_end;
+ pbox++)
{
-
- if (pbox->y2 <= y)
- continue; /* getting up to speed or skipping remainder of band */
+ /* getting up to speed or skipping remainder of band */
+ if (pbox->y2 <= y)
+ {
+ if ((pbox = find_box_for_y (pbox, pbox_end, y)) == pbox_end)
+ break;
+ }
if (pbox->y1 > y)
{
--
1.7.4
More information about the Pixman
mailing list