[Pixman] [PATCH 3/4] Speed up pixman_region{, 32}_contains_rectangle()

[Andrea Canciani]

On Thu, Aug 4, 2011 at 4:21 AM, Søren Sandmann <sandmann at cs.au.dk> wrote:
> 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 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 at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/pixman
>