[matplotlib-devel] [patch] RegularPolyCollection.get_transformed_patches speed-up
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 https://lists.sourceforge.net/lists/listinfo/matplotlib-devel
Re: [matplotlib-devel] [patch] RegularPolyCollection.get_transformed_patches speed-up
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 > https://lists.sourceforge.net/lists/listinfo/matplotlib-devel - 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 https://lists.sourceforge.net/lists/listinfo/matplotlib-devel
Re: [matplotlib-devel] [patch] RegularPolyCollection.get_transformed_patches speed-up
On 5/10/07, Eric Firing <[EMAIL PROTECTED]> 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 > > https://lists.sourceforge.net/lists/listinfo/matplotlib-devel > > - 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 https://lists.sourceforge.net/lists/listinfo/matplotlib-devel
Re: [matplotlib-devel] [patch] RegularPolyCollection.get_transformed_patches speed-up
Tim Leslie wrote: > On 5/10/07, Eric Firing <[EMAIL PROTECTED]> 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 > > 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) >> > >> > >> > >> --
