[patch] RegularPolyCollection.get_transformed_patches speed-up

_Tim_Leslie · May 9, 2007, 2:15pm

Hi All,

I've attached a patch which optimizes a particular case of the
RegularPolyCollection.get_transformed_patches method. This is
particularly useful when using a picker on a scatter plot with ~40,000
points (as I happen to be doing) and cuts the time spent in this
function from ~4s to ~1s, which accounts for about 50% of the lag in
my particular use case.

Similar improvements might be possible in the N > 1 case, but I don't
have a) a data set or b) the time to work them out with, so hopefully
someone is happy to check in this patch as it stands, as I think the
N==1 is probably the common case.

If there are any problems with the patch let me know and I'll try to
fix it up. It's against latest svn (3262)

Cheers,

Tim

collections.patch (1.54 KB)

Eric_Firing2 · May 9, 2007, 5:52pm

Tim,

Based on a *very superficial* quick look, I have two comments:

1) Since the plan is (or was?) to have one more release before specializing to numpy-only support, the ".T" won't work at present.

2) In the following (possibly mangled by mailer),

> + if Nsizes == 1:
> + xy = asarray([xverts, yverts]).T * sizes[0]
> + polys = [xy + offset for offset in transOffset.seq_xy_tups(self._offsets)]

I think you can gain additional speedup by eliminating the list comprehension. Instead of using seq_xy_tups you can use numerix_xy to return a 2-D array (with columns x and y), and simply add that to xy.

Eric

Tim Leslie wrote:

···

Hi All,

I've attached a patch which optimizes a particular case of the
RegularPolyCollection.get_transformed_patches method. This is
particularly useful when using a picker on a scatter plot with ~40,000
points (as I happen to be doing) and cuts the time spent in this
function from ~4s to ~1s, which accounts for about 50% of the lag in
my particular use case.

Similar improvements might be possible in the N > 1 case, but I don't
have a) a data set or b) the time to work them out with, so hopefully
someone is happy to check in this patch as it stands, as I think the
N==1 is probably the common case.

If there are any problems with the patch let me know and I'll try to
fix it up. It's against latest svn (3262)

Cheers,

Tim

------------------------------------------------------------------------

Index: lib/matplotlib/collections.py

--- lib/matplotlib/collections.py (revision 3262)
+++ lib/matplotlib/collections.py (working copy)
@@ -153,7 +153,7 @@
         if not self.pickable(): return
         ind =
         x, y = mouseevent.x, mouseevent.y
- for i, thispoly in enumerate(self.get_transformed_patches()): + for i, thispoly in enumerate(self.get_transformed_patches()):
             inside = nxutils.pnpoly(x, y, thispoly)
             if inside: ind.append(i)
         if len(ind):
@@ -167,7 +167,6 @@
         The ith element in the returned sequence is a list of x,y
         vertices defining the ith polygon
         """
-
         verts = self._verts
         offsets = self._offsets
         usingOffsets = offsets is not None
@@ -451,13 +450,19 @@
     __init__.__doc__ = dedent(__init__.__doc__) % kwdocd
      def get_transformed_patches(self):
- +
         xverts, yverts = zip(*self._verts)
         xverts = asarray(xverts)
         yverts = asarray(yverts)
         sizes = sqrt(asarray(self._sizes)*self._dpi.get()/72.0)
         Nsizes = len(sizes)
         transOffset = self.get_transoffset()
+
+ # optimize this case for an approx 4x speedup
+ if Nsizes == 1:
+ xy = asarray([xverts, yverts]).T * sizes[0]
+ polys = [xy + offset for offset in transOffset.seq_xy_tups(self._offsets)]
+
         polys =
         for i, loc in enumerate(self._offsets):
             xo,yo = transOffset.xy_tup(loc)

------------------------------------------------------------------------

-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/

------------------------------------------------------------------------

_______________________________________________
Matplotlib-devel mailing list
Matplotlib-devel@lists.sourceforge.net
matplotlib-devel List Signup and Options

_Tim_Leslie · May 10, 2007, 12:34am

Tim,

Based on a *very superficial* quick look, I have two comments:

1) Since the plan is (or was?) to have one more release before
specializing to numpy-only support, the ".T" won't work at present.

2) In the following (possibly mangled by mailer),

> + if Nsizes == 1:
> + xy = asarray([xverts, yverts]).T * sizes[0]
> + polys = [xy + offset for offset in
transOffset.seq_xy_tups(self._offsets)]

I think you can gain additional speedup by eliminating the list
comprehension. Instead of using seq_xy_tups you can use numerix_xy to
return a 2-D array (with columns x and y), and simply add that to xy.

Thanks for the feedback Eric, I'll rework the patch with your comments
in mind. I also just noticed a rather glaring bug, in that I don't
actually have a 'return polys' after I calculate them in the special
case, which is somewhat embarrassing. I'll fix all this up and submit
a new patch later today.

Cheers,

Tim

···

On 5/10/07, Eric Firing <efiring@...229...> wrote:

Eric

Tim Leslie wrote:
> Hi All,
>
> I've attached a patch which optimizes a particular case of the
> RegularPolyCollection.get_transformed_patches method. This is
> particularly useful when using a picker on a scatter plot with ~40,000
> points (as I happen to be doing) and cuts the time spent in this
> function from ~4s to ~1s, which accounts for about 50% of the lag in
> my particular use case.
>
> Similar improvements might be possible in the N > 1 case, but I don't
> have a) a data set or b) the time to work them out with, so hopefully
> someone is happy to check in this patch as it stands, as I think the
> N==1 is probably the common case.
>
> If there are any problems with the patch let me know and I'll try to
> fix it up. It's against latest svn (3262)
>
> Cheers,
>
> Tim
>
> ------------------------------------------------------------------------
>
> Index: lib/matplotlib/collections.py
> ===================================================================
> --- lib/matplotlib/collections.py (revision 3262)
> +++ lib/matplotlib/collections.py (working copy)
> @@ -153,7 +153,7 @@
> if not self.pickable(): return
> ind =
> x, y = mouseevent.x, mouseevent.y
> - for i, thispoly in enumerate(self.get_transformed_patches()):
> + for i, thispoly in enumerate(self.get_transformed_patches()):
> inside = nxutils.pnpoly(x, y, thispoly)
> if inside: ind.append(i)
> if len(ind):
> @@ -167,7 +167,6 @@
> The ith element in the returned sequence is a list of x,y
> vertices defining the ith polygon
> """
> -
> verts = self._verts
> offsets = self._offsets
> usingOffsets = offsets is not None
> @@ -451,13 +450,19 @@
> __init__.__doc__ = dedent(__init__.__doc__) % kwdocd
>
> def get_transformed_patches(self):
> -
> +
> xverts, yverts = zip(*self._verts)
> xverts = asarray(xverts)
> yverts = asarray(yverts)
> sizes = sqrt(asarray(self._sizes)*self._dpi.get()/72.0)
> Nsizes = len(sizes)
> transOffset = self.get_transoffset()
> +
> + # optimize this case for an approx 4x speedup
> + if Nsizes == 1:
> + xy = asarray([xverts, yverts]).T * sizes[0]
> + polys = [xy + offset for offset in transOffset.seq_xy_tups(self._offsets)]
> +
> polys =
> for i, loc in enumerate(self._offsets):
> xo,yo = transOffset.xy_tup(loc)
>
> ------------------------------------------------------------------------
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by DB2 Express
> Download DB2 Express C - the FREE version of DB2 express and take
> control of your XML. No limits. Just data. Click to get it now.
> http://sourceforge.net/powerbar/db2/
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Matplotlib-devel mailing list
> Matplotlib-devel@lists.sourceforge.net
> matplotlib-devel List Signup and Options

Eric_Firing2 · May 10, 2007, 3:55am

Tim Leslie wrote:

Tim,

Based on a *very superficial* quick look, I have two comments:

1) Since the plan is (or was?) to have one more release before
specializing to numpy-only support, the ".T" won't work at present.

2) In the following (possibly mangled by mailer),

> + if Nsizes == 1:
> + xy = asarray([xverts, yverts]).T * sizes[0]
> + polys = [xy + offset for offset in
transOffset.seq_xy_tups(self._offsets)]

I think you can gain additional speedup by eliminating the list
comprehension. Instead of using seq_xy_tups you can use numerix_xy to
return a 2-D array (with columns x and y), and simply add that to xy.

Thanks for the feedback Eric, I'll rework the patch with your comments
in mind. I also just noticed a rather glaring bug, in that I don't
actually have a 'return polys' after I calculate them in the special
case, which is somewhat embarrassing. I'll fix all this up and submit
a new patch later today.

Tim,

I took a look at the original code in collections.py. It looks like it could be greatly streamlined by using numerix consistently, taking advantage of the resize function (for the sizes array) and broadcasting. No loops should be needed, and the x and y coordinates never need to be separated; it might still be worthwhile to special-case the Nsizes==1 case to avoid the call to resize. I am not sure whether there would be any problem with returning a 3-D array instead of a list of 2-D arrays; if so, that conversion could be done with a list comprehension at the end.

My impression is that that for small arrays, lists and tuples are faster than using numerix, and the reverse for large arrays, but I don't know where the switchover is. There many places in mpl (including other methods of RegularPolyCollection) where zips and list comprehensions and explicit loops could be eliminated by using numerix consistently; I don't know in how many of these it would be good to make this change. Lists are much more flexible, and there are places where that flexibility is needed.

Eric

···

On 5/10/07, Eric Firing <efiring@...229...> wrote:

Cheers,

Tim

Eric

Tim Leslie wrote:
> Hi All,
>
> I've attached a patch which optimizes a particular case of the
> RegularPolyCollection.get_transformed_patches method. This is
> particularly useful when using a picker on a scatter plot with ~40,000
> points (as I happen to be doing) and cuts the time spent in this
> function from ~4s to ~1s, which accounts for about 50% of the lag in
> my particular use case.
>
> Similar improvements might be possible in the N > 1 case, but I don't
> have a) a data set or b) the time to work them out with, so hopefully
> someone is happy to check in this patch as it stands, as I think the
> N==1 is probably the common case.
>
> If there are any problems with the patch let me know and I'll try to
> fix it up. It's against latest svn (3262)
>
> Cheers,
>
> Tim
>
> ------------------------------------------------------------------------
>
> Index: lib/matplotlib/collections.py
> ===================================================================
> --- lib/matplotlib/collections.py (revision 3262)
> +++ lib/matplotlib/collections.py (working copy)
> @@ -153,7 +153,7 @@
> if not self.pickable(): return
> ind =
> x, y = mouseevent.x, mouseevent.y
> - for i, thispoly in enumerate(self.get_transformed_patches()):
> + for i, thispoly in enumerate(self.get_transformed_patches()):
> inside = nxutils.pnpoly(x, y, thispoly)
> if inside: ind.append(i)
> if len(ind):
> @@ -167,7 +167,6 @@
> The ith element in the returned sequence is a list of x,y
> vertices defining the ith polygon
> """
> -
> verts = self._verts
> offsets = self._offsets
> usingOffsets = offsets is not None
> @@ -451,13 +450,19 @@
> __init__.__doc__ = dedent(__init__.__doc__) % kwdocd
>
> def get_transformed_patches(self):
> -
> +
> xverts, yverts = zip(*self._verts)
> xverts = asarray(xverts)
> yverts = asarray(yverts)
> sizes = sqrt(asarray(self._sizes)*self._dpi.get()/72.0)
> Nsizes = len(sizes)
> transOffset = self.get_transoffset()
> +
> + # optimize this case for an approx 4x speedup
> + if Nsizes == 1:
> + xy = asarray([xverts, yverts]).T * sizes[0]
> + polys = [xy + offset for offset in transOffset.seq_xy_tups(self._offsets)]
> +
> polys =
> for i, loc in enumerate(self._offsets):
> xo,yo = transOffset.xy_tup(loc)
>
> ------------------------------------------------------------------------
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by DB2 Express
> Download DB2 Express C - the FREE version of DB2 express and take
> control of your XML. No limits. Just data. Click to get it now.
> http://sourceforge.net/powerbar/db2/
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Matplotlib-devel mailing list
> Matplotlib-devel@lists.sourceforge.net
> matplotlib-devel List Signup and Options

Eric_Firing2 · May 10, 2007, 7:36am

Tim,

I couldn't resist; here is a numerix version of the method, which I committed to svn:

     def get_transformed_patches(self):
         # Shouldn't need all these calls to asarray;
         # the variables should be converted when stored.
         # Similar speedups with numerix should be attainable
         # in many other places.
         verts = asarray(self._verts)
         offsets = asarray(self._offsets)
         Npoly = len(offsets)
         scales = sqrt(asarray(self._sizes)*self._dpi.get()/72.0)
         Nscales = len(scales)
         if Nscales >1:
             scales = resize(scales, (Npoly, 1, 1))
         transOffset = self.get_transoffset()
         xyo = transOffset.numerix_xy(offsets)
         polys = scales * verts + xyo[:, newaxis, :]
         return polys

It is faster even when there are only three polygons; and as the comment indicates, it would be even faster with additional numpification of the entire class. (Present version with 3 polys, 161 usecs vs 241 usecs; with 1000, 6.4 msec vs 47.3 msec.)

It is also only lightly tested. I hope I haven't overlooked some situation that would work with the old version but not with this one.

Eric

Tim Leslie wrote:

···

On 5/10/07, Eric Firing <efiring@...229...> wrote:

Tim,

Based on a *very superficial* quick look, I have two comments:

1) Since the plan is (or was?) to have one more release before
specializing to numpy-only support, the ".T" won't work at present.

2) In the following (possibly mangled by mailer),

> + if Nsizes == 1:
> + xy = asarray([xverts, yverts]).T * sizes[0]
> + polys = [xy + offset for offset in
transOffset.seq_xy_tups(self._offsets)]

I think you can gain additional speedup by eliminating the list
comprehension. Instead of using seq_xy_tups you can use numerix_xy to
return a 2-D array (with columns x and y), and simply add that to xy.

Thanks for the feedback Eric, I'll rework the patch with your comments
in mind. I also just noticed a rather glaring bug, in that I don't
actually have a 'return polys' after I calculate them in the special
case, which is somewhat embarrassing. I'll fix all this up and submit
a new patch later today.

Cheers,

Tim

Eric

Tim Leslie wrote:
> Hi All,
>
> I've attached a patch which optimizes a particular case of the
> RegularPolyCollection.get_transformed_patches method. This is
> particularly useful when using a picker on a scatter plot with ~40,000
> points (as I happen to be doing) and cuts the time spent in this
> function from ~4s to ~1s, which accounts for about 50% of the lag in
> my particular use case.
>
> Similar improvements might be possible in the N > 1 case, but I don't
> have a) a data set or b) the time to work them out with, so hopefully
> someone is happy to check in this patch as it stands, as I think the
> N==1 is probably the common case.
>
> If there are any problems with the patch let me know and I'll try to
> fix it up. It's against latest svn (3262)
>
> Cheers,
>
> Tim
>
> ------------------------------------------------------------------------
>
> Index: lib/matplotlib/collections.py
> ===================================================================
> --- lib/matplotlib/collections.py (revision 3262)
> +++ lib/matplotlib/collections.py (working copy)
> @@ -153,7 +153,7 @@
> if not self.pickable(): return
> ind =
> x, y = mouseevent.x, mouseevent.y
> - for i, thispoly in enumerate(self.get_transformed_patches()):
> + for i, thispoly in enumerate(self.get_transformed_patches()):
> inside = nxutils.pnpoly(x, y, thispoly)
> if inside: ind.append(i)
> if len(ind):
> @@ -167,7 +167,6 @@
> The ith element in the returned sequence is a list of x,y
> vertices defining the ith polygon
> """
> -
> verts = self._verts
> offsets = self._offsets
> usingOffsets = offsets is not None
> @@ -451,13 +450,19 @@
> __init__.__doc__ = dedent(__init__.__doc__) % kwdocd
>
> def get_transformed_patches(self):
> -
> +
> xverts, yverts = zip(*self._verts)
> xverts = asarray(xverts)
> yverts = asarray(yverts)
> sizes = sqrt(asarray(self._sizes)*self._dpi.get()/72.0)
> Nsizes = len(sizes)
> transOffset = self.get_transoffset()
> +
> + # optimize this case for an approx 4x speedup
> + if Nsizes == 1:
> + xy = asarray([xverts, yverts]).T * sizes[0]
> + polys = [xy + offset for offset in transOffset.seq_xy_tups(self._offsets)]
> +
> polys =
> for i, loc in enumerate(self._offsets):
> xo,yo = transOffset.xy_tup(loc)
>
> ------------------------------------------------------------------------
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by DB2 Express
> Download DB2 Express C - the FREE version of DB2 express and take
> control of your XML. No limits. Just data. Click to get it now.
> http://sourceforge.net/powerbar/db2/
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> Matplotlib-devel mailing list
> Matplotlib-devel@lists.sourceforge.net
> matplotlib-devel List Signup and Options

_Tim_Leslie · May 10, 2007, 12:06pm

Hi Eric,

I just checked out your change and it works another 0.2s faster than
what I had for my example, so I'm more than happy with the final
result. Thanks for taking the time to put my hazy ideas into practice
the right way

Cheers,

Tim

···

On 5/10/07, Eric Firing <efiring@...229...> wrote:

Tim,

I couldn't resist; here is a numerix version of the method, which I
committed to svn:

     def get_transformed_patches(self):
         # Shouldn't need all these calls to asarray;
         # the variables should be converted when stored.
         # Similar speedups with numerix should be attainable
         # in many other places.
         verts = asarray(self._verts)
         offsets = asarray(self._offsets)
         Npoly = len(offsets)
         scales = sqrt(asarray(self._sizes)*self._dpi.get()/72.0)
         Nscales = len(scales)
         if Nscales >1:
             scales = resize(scales, (Npoly, 1, 1))
         transOffset = self.get_transoffset()
         xyo = transOffset.numerix_xy(offsets)
         polys = scales * verts + xyo[:, newaxis, :]
         return polys

It is faster even when there are only three polygons; and as the comment
indicates, it would be even faster with additional numpification of the
entire class. (Present version with 3 polys, 161 usecs vs 241 usecs;
with 1000, 6.4 msec vs 47.3 msec.)

It is also only lightly tested. I hope I haven't overlooked some
situation that would work with the old version but not with this one.

Eric

Tim Leslie wrote:
> On 5/10/07, Eric Firing <efiring@...229...> wrote:
>> Tim,
>>
>> Based on a *very superficial* quick look, I have two comments:
>>
>> 1) Since the plan is (or was?) to have one more release before
>> specializing to numpy-only support, the ".T" won't work at present.
>>
>> 2) In the following (possibly mangled by mailer),
>>
>> > + if Nsizes == 1:
>> > + xy = asarray([xverts, yverts]).T * sizes[0]
>> > + polys = [xy + offset for offset in
>> transOffset.seq_xy_tups(self._offsets)]
>>
>> I think you can gain additional speedup by eliminating the list
>> comprehension. Instead of using seq_xy_tups you can use numerix_xy to
>> return a 2-D array (with columns x and y), and simply add that to xy.
>>
>
> Thanks for the feedback Eric, I'll rework the patch with your comments
> in mind. I also just noticed a rather glaring bug, in that I don't
> actually have a 'return polys' after I calculate them in the special
> case, which is somewhat embarrassing. I'll fix all this up and submit
> a new patch later today.
>
> Cheers,
>
> Tim
>
>> Eric
>>
>> Tim Leslie wrote:
>> > Hi All,
>> >
>> > I've attached a patch which optimizes a particular case of the
>> > RegularPolyCollection.get_transformed_patches method. This is
>> > particularly useful when using a picker on a scatter plot with ~40,000
>> > points (as I happen to be doing) and cuts the time spent in this
>> > function from ~4s to ~1s, which accounts for about 50% of the lag in
>> > my particular use case.
>> >
>> > Similar improvements might be possible in the N > 1 case, but I don't
>> > have a) a data set or b) the time to work them out with, so hopefully
>> > someone is happy to check in this patch as it stands, as I think the
>> > N==1 is probably the common case.
>> >
>> > If there are any problems with the patch let me know and I'll try to
>> > fix it up. It's against latest svn (3262)
>> >
>> > Cheers,
>> >
>> > Tim
>> >
>> ------------------------------------------------------------------------
>> >
>> > Index: lib/matplotlib/collections.py
>> > ===================================================================
>> > --- lib/matplotlib/collections.py (revision 3262)
>> > +++ lib/matplotlib/collections.py (working copy)
>> > @@ -153,7 +153,7 @@
>> > if not self.pickable(): return
>> > ind =
>> > x, y = mouseevent.x, mouseevent.y
>> > - for i, thispoly in enumerate(self.get_transformed_patches()):
>> > + for i, thispoly in enumerate(self.get_transformed_patches()):
>> > inside = nxutils.pnpoly(x, y, thispoly)
>> > if inside: ind.append(i)
>> > if len(ind):
>> > @@ -167,7 +167,6 @@
>> > The ith element in the returned sequence is a list of x,y
>> > vertices defining the ith polygon
>> > """
>> > -
>> > verts = self._verts
>> > offsets = self._offsets
>> > usingOffsets = offsets is not None
>> > @@ -451,13 +450,19 @@
>> > __init__.__doc__ = dedent(__init__.__doc__) % kwdocd
>> >
>> > def get_transformed_patches(self):
>> > -
>> > +
>> > xverts, yverts = zip(*self._verts)
>> > xverts = asarray(xverts)
>> > yverts = asarray(yverts)
>> > sizes = sqrt(asarray(self._sizes)*self._dpi.get()/72.0)
>> > Nsizes = len(sizes)
>> > transOffset = self.get_transoffset()
>> > +
>> > + # optimize this case for an approx 4x speedup
>> > + if Nsizes == 1:
>> > + xy = asarray([xverts, yverts]).T * sizes[0]
>> > + polys = [xy + offset for offset in
>> transOffset.seq_xy_tups(self._offsets)]
>> > +
>> > polys =
>> > for i, loc in enumerate(self._offsets):
>> > xo,yo = transOffset.xy_tup(loc)
>> >
>> ------------------------------------------------------------------------
>> >
>> -------------------------------------------------------------------------
>> > This SF.net email is sponsored by DB2 Express
>> > Download DB2 Express C - the FREE version of DB2 express and take
>> > control of your XML. No limits. Just data. Click to get it now.
>> > http://sourceforge.net/powerbar/db2/
>> >
>> ------------------------------------------------------------------------
>> >
>> > _______________________________________________
>> > Matplotlib-devel mailing list
>> > Matplotlib-devel@lists.sourceforge.net
>> > matplotlib-devel List Signup and Options
>>