ENH: optimize Collection non-affine transform to call transform once #11465

jklymak · 2018-06-20T21:42:29Z

PR Summary

As noted in https://github.com/astropy/astropy/pull/7568/files#diff-421f6873fdd2d8a90f39f3050534b0c3R139 and #11464 Collections weren't very snappy if they had lots of separate paths that needed to be run through a non-affine transform that was slow.

@astrofrog came up w/ the solution in astropy/astropy#7568, and it is applied here on a per-collection basis (his soln was for every collection in a contour set, which may make things even faster). The basic idea is that the transform only gets called once for all the vertices in the paths in the collection and then they get re-divided up after transformation.

Test

From @astrofrog with a deliberately slow transform function...

import time
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.transforms import Transform
from scipy.ndimage import gaussian_filter


class CustomTransform(Transform):

    input_dims = 2
    output_dims = 2
    affine = False

    def transform_path_non_affine(self, path):
        time.sleep(1 / 1000.)
        return path


image = np.random.random((1024, 1024))
image = gaussian_filter(image, 2)

ax = plt.subplot(1, 1, 1)
ax.contour(image, level=10, transform=CustomTransform())
plt.savefig('contours.png')

Takes about 20s on master, about 2s on this PR...

PR Checklist

Has Pytest style unit tests
Code is PEP 8 compliant
New features are documented, with examples if plot related
Documentation is sphinx and numpydoc compliant
Added an entry to doc/users/next_whats_new/ if major new feature (follow instructions in README.rst there)
Documented in doc/api/api_changes.rst if API changed in a backward-incompatible way

jklymak · 2018-06-20T21:53:22Z

Hah, need to be more careful - borks a lot of other things. Still, should be an easy fix...

…once

jklymak · 2018-06-20T23:30:36Z

Timing: there is a small hit for this PR for non-affine transforms that are not too slow. i.e. if I remove the time.sleep:

With time.sleep: 34 s before, 1.09 s after
Without time.sleep: 0.9 s before, 1.10 s after

I'd argue the small 20% hit just for non-affine transforms is worth it to make slow transforms work much faster.

ImportanceOfBeingErnest · 2018-06-20T23:48:04Z

Ähm.. no. 99.999% of all transforms being used in matplotlib are expected to be sufficiently quick. So you say you would rather let those standard cases become slower????

jklymak · 2018-06-20T23:49:28Z

This code path is only for non-affine transforms. Affine transforms aren't affected...

ImportanceOfBeingErnest · 2018-06-20T23:59:47Z

The standard polar plot contains a non-affine transform. Does this proposed solution make the creation of contours on polar plots slower?

jklymak · 2018-06-21T00:03:26Z

That probably depends on the nature of the contours....

jklymak · 2018-06-21T00:12:06Z

import time
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.transforms import Transform
from scipy.ndimage import gaussian_filter


np.random.seed(19680801)

image = np.random.random((1024, 1024))
image = gaussian_filter(image, 2)

ax = plt.subplot(1, 1, 1, projection='polar')
ax.contour(image)
plt.savefig('contours.png')
plt.close()

Old: 11.1 s
New: 8.54 s

ImportanceOfBeingErnest · 2018-06-21T00:24:49Z

What about a less pathological case like

import matplotlib.pyplot as plt
import numpy as np

phi,r = np.meshgrid(np.linspace(0,2*np.pi,50),np.linspace(0,1,50))
z = phi*r

fig, ax = plt.subplots(subplot_kw=dict(projection="polar"))

def time(phi,r,z,fig,ax):
    ax.contour(phi, r, z)
    fig.savefig("contourtiming.png")

jklymak · 2018-06-21T00:32:36Z

Old: 168 ms
New: 168 ms
(7 runs, 20 loops each)

EDIT: But thats not surprising because all the contours are a single line segment in that example. The slowdown / speed up only happens if there are multiple line segments per contour level like in the random examples.

dstansby

👍 looks like a nice speedup

dopplershift

👍 on the functionality and trying to optimize this path.

I think the current implementation has some behavior changes that aren't quite right, though.

dopplershift · 2018-06-21T17:30:36Z

lib/matplotlib/collections.py

@@ -189,7 +189,7 @@ def get_datalim(self, transData):
        paths = self.get_paths()

        if not transform.is_affine:
-            paths = [transform.transform_path_non_affine(p) for p in paths]
+            paths = self._non_affine_transform_paths(paths, transform)


We've gone here from calling transform_path_non_affine to (effectively) transform_non_affine. The former returns a new Path, which based on my reading would seem to offer possibly interpolate points along the path in the transformed coordinate system. The latter will not do this. Now, does anyone know if this is important?

Is it possible to instead combine the individual Paths into one big path and use transform_path_non_affine?

Oh, hummm. OK< I just looked at the default transform_path_non_affine but that can be overridden, so I think you're right that we need to call that instead....

I looked at the default as well, and the line I'm concerned we're skipping is:

return Path._fast_from_codes_and_verts(x, path.codes, {'interpolation_steps': path._interpolation_steps, 'should_simplify': path.should_simplify})

Your current implementation calls self.transform_non_affine(vertices), just like the default transform_path_non_affine, but it reuses the existing Path instances.

Ok, I may be over paranoid. It looks like _fast_from_codes_and_verts just sets the interpolation steps, it doesn't do any actual interpolation at that time.

matplotlib/lib/matplotlib/projections/geo.py

Lines 260 to 265 in b078643

def transform_path_non_affine(self, path):

vertices = path.vertices

ipath = path.interpolated(self._resolution)

return Path(self.transform(ipath.vertices), ipath.codes)

transform_path_non_affine.__doc__ = \

Transform.transform_path_non_affine.__doc__

Looks to me like the path changes length. Which makes life pretty hard because its hard to then split up the new path based on the length of the input path...

So, its possible to come up w/ an algorithm that does this if transform_path_non_affine uses only path.interpolated to get the higher-res path. But, I don't see any reason that an arbitrary user-supplied transform would be restricted to doing that method of interpolation.

Given that ambiguity, I think its impossible to come up with a foolproof algorithm for this. I suppose the special case of no interpolation could be checked for and would work.

I'll point out that @astrofrog's fix is obviously counting on the non-affine path transform not doing any interpolation - i.e. its doing linear dot connecting after the tranform. Certainly that'd be a disaster for a geographic non-affine transform (i.e. you want a straight line in lat/lon to be curved in the projection), but maybe is fine for astropy?

@jklymak - ah I see - in our case we write the transforms we are using and we don't make use of interpolation for now so things should be fine. It would be pretty rare for the resolution of the contour map to be so low that there would be significant distortions between vertices of the path.

dopplershift · 2018-06-21T17:30:42Z

lib/matplotlib/collections.py

+        # repopulate paths
+        verts = np.split(vertices, pos[:-1])
+        for nn, verti in enumerate(verts):
+            paths[nn].vertices = verti


You're modifying paths in place; if you trace back, this is a reference to self._paths, which means you're modifying the original contours. That seems really bad.

jklymak · 2018-07-04T18:11:56Z

OK, closing this, because I don't think it'll work for general implimentations of transform_path_non_affine Thanks @dopplershift for catching that!

jklymak added the status: work in progress label Jun 20, 2018

ENH: optimize Collection non-affine transform to only call transform …

c31d901

…once

jklymak force-pushed the enh-optimize-non-affine-transform branch from acf4ac4 to c31d901 Compare June 20, 2018 22:25

jklymak removed the status: work in progress label Jun 20, 2018

jklymak added this to the v3.0 milestone Jun 20, 2018

jklymak mentioned this pull request Jun 20, 2018

Speeding up contours with (non-affine) transforms #11464

Closed

dstansby approved these changes Jun 21, 2018

View reviewed changes

dopplershift reviewed Jun 21, 2018

View reviewed changes

jklymak added the status: work in progress label Jun 21, 2018

tacaswell modified the milestones: v3.0, v3.1 Jul 1, 2018

jklymak closed this Jul 4, 2018

jklymak deleted the enh-optimize-non-affine-transform branch July 4, 2018 18:12

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ENH: optimize Collection non-affine transform to call transform once #11465

ENH: optimize Collection non-affine transform to call transform once #11465

jklymak commented Jun 20, 2018 •

edited

Loading

jklymak commented Jun 20, 2018

jklymak commented Jun 20, 2018

ImportanceOfBeingErnest commented Jun 20, 2018

jklymak commented Jun 20, 2018

ImportanceOfBeingErnest commented Jun 20, 2018

jklymak commented Jun 21, 2018

jklymak commented Jun 21, 2018

ImportanceOfBeingErnest commented Jun 21, 2018

jklymak commented Jun 21, 2018 •

edited

Loading

dstansby left a comment

dopplershift left a comment

dopplershift Jun 21, 2018

jklymak Jun 21, 2018

dopplershift Jun 21, 2018

dopplershift Jun 21, 2018

jklymak Jun 21, 2018 •

edited

Loading

jklymak Jun 21, 2018

astrofrog Jul 5, 2018

dopplershift Jun 21, 2018

jklymak commented Jul 4, 2018

	def transform_path_non_affine(self, path):
	vertices = path.vertices
	ipath = path.interpolated(self._resolution)
	return Path(self.transform(ipath.vertices), ipath.codes)
	transform_path_non_affine.__doc__ = \
	Transform.transform_path_non_affine.__doc__

ENH: optimize Collection non-affine transform to call transform once #11465

ENH: optimize Collection non-affine transform to call transform once #11465

Conversation

jklymak commented Jun 20, 2018 • edited Loading

PR Summary

Test

PR Checklist

jklymak commented Jun 20, 2018

jklymak commented Jun 20, 2018

ImportanceOfBeingErnest commented Jun 20, 2018

jklymak commented Jun 20, 2018

ImportanceOfBeingErnest commented Jun 20, 2018

jklymak commented Jun 21, 2018

jklymak commented Jun 21, 2018

ImportanceOfBeingErnest commented Jun 21, 2018

jklymak commented Jun 21, 2018 • edited Loading

dstansby left a comment

Choose a reason for hiding this comment

dopplershift left a comment

Choose a reason for hiding this comment

dopplershift Jun 21, 2018

Choose a reason for hiding this comment

jklymak Jun 21, 2018

Choose a reason for hiding this comment

dopplershift Jun 21, 2018

Choose a reason for hiding this comment

dopplershift Jun 21, 2018

Choose a reason for hiding this comment

jklymak Jun 21, 2018 • edited Loading

Choose a reason for hiding this comment

jklymak Jun 21, 2018

Choose a reason for hiding this comment

astrofrog Jul 5, 2018

Choose a reason for hiding this comment

dopplershift Jun 21, 2018

Choose a reason for hiding this comment

jklymak commented Jul 4, 2018

jklymak commented Jun 20, 2018 •

edited

Loading

jklymak commented Jun 21, 2018 •

edited

Loading

jklymak Jun 21, 2018 •

edited

Loading