|
|
| OptimizationAccording to Knuth, "Premature optimization is the root of all evil". Although the performance of Topographica is critically important, the way to achieve high performance is by spending all of our optimization efforts on the very small portion of the code that accounts for nearly all of the run time, i.e., the bottlenecks. The overall architecture of Topographica is designed explicitly to localize those bottlenecks into specific functions and objects that can then be heavily optimized without affecting any of the rest of the code. Only in such small, local regions, behind well-defined modules with clear semantics, is it possible to optimize effectively in a way that can be maintained in the long run. If it is precisely clear what the module is supposed to do, then the implementation can be polished to achieve that, while reasoning only about the behavior of that one specific module. Conversely, finding that good performance requires adding special hacks in the largest-scale, general-purpose parts of the overall Topographica architecture means that the architecture is flawed and needs to be re-thought. For instance, please do not add any special checks scattered through the code testing for specific PatternGenerator or Sheet objects, substituting a quicker version of some operation but falling back to the general case for others. Such code is impossible to understand and maintain, because changes to the specific object implementations will not have any effect. Instead, we can optimize the individual PatternGenerator or Sheet object heavily. If some special hack needs to be done at a high level, e.g. at the base Sheet class level, we can add a method there that then gets overridden in the subclass with the special purpose code. That way all optimization will be local (and thus maintainable). If it's not clear how to optimize something cleanly, first do it uncleanly to see if it will have any effect, but don't check it in to SVN. If it looks like the optimization is worthwhile, brainstorm with other team members to figure out a way to do it cleanly and check in the clean version instead. For a good overview of how to optimize memory usage, which is often the bottleneck for our simulations, see Ulrich Drepper's article. If you are ambitious, even the most optimized components in Topographica could be further improved using these techniques, possibly substantially. Optimizing Python codeAlthough dramatic speedups usually require big changes as described below, sometimes all you need is minor tweaks to Python code to get it to have reasonable performance. Usually this involves avoiding unnecessary attribute lookup, as described here. What is usually more important to ensure is that anything that can
use the array-based primitives provided by
numpy does so, because these
generally have underlying C implementations that are quite fast.
Using numpy operations should be the first approach when optimizing
any component, and indeed when writing the component for the first
time (because the numpy primitives are much easier to use and
maintain than e.g. explicitly writing Providing optimized versions of Topographica objectsHowever, there are certain cases where the performance of numpy is not sufficient, or where numpy is unsuitable (for example, some numpy operations do not act in-place on arrays). Other components may be able to be implemented much more quickly if certain assumptions are made about the nature of their arguments, or the types of computations that can be performed.In these cases, it is worthwhile to have a reference
version of the object that is simple to understand and does not make
any special assumptions. Then, an optimized version can be offered as
an alternative. The convention we use is to add the suffix
For example, consider The non-optimized version also acts as a simple specification of exactly what the optimized version is supposed to do, apart from any optimizations. The optimized versions are often nearly unreadable, so having the simple version available is very helpful for understanding and debugging. The expectation is that the simple (slow) versions will rarely change, but the optimized ones will get faster and faster over time, while preserving the same user-visible behavior. Finding bottlenecksAs discussed above, we wish to spend our time optimizing parts of
the code that account for most of the run
time. For instance, if we have a simple simulation consisting of a
SOM-based sheet connected to a We can run topographica as follows, using the
$ ./topographica speed_test.ty -c "from topo.misc.util import profile; \
profile('topo.sim.run(200)',n=20)"
1477056 function calls (1468656 primitive calls) in 50.198 CPU seconds
Ordered by: cumulative time, internal time
List reduced from 111 to 20 due to restriction <20>
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 50.198 50.198
The n=20 argument restricts the list to the top 20
functions, ordered by cumulative time. For more information about the
types of ordering available, help(profile) provides a
link to Python's documentation.
From
from topo.base.functionfamily import DotProduct
class CFPRF_Plugin(CFPResponseFn):
"""
Generic large-scale response function based on a simple single-CF function.
Applies the single_cf_fn to each CF in turn. For the default
single_cf_fn of DotProduct(), does a basic dot product of each CF with the
corresponding slice of the input array. This function is likely
to be slow to run, but it is easy to extend with any arbitrary
single-CF response function.
The single_cf_fn must be a function f(X,W) that takes two
identically shaped matrices X (the input) and W (the
ConnectionField weights) and computes a scalar activation value
based on those weights.
"""
single_cf_fn = ResponseFnParameter(default=DotProduct(),
doc="Accepts a ResponseFn that will be applied to each CF individually.")
def __call__(self, cfs, input_activity, activity, strength):
rows,cols = activity.shape
single_cf_fn = self.single_cf_fn
for r in xrange(rows):
for c in xrange(cols):
cf = cfs[r][c]
r1,r2,c1,c2 = cf.slice_array
X = input_activity[r1:r2,c1:c2]
#if (X.shape != cf.weights.shape):
# self.warning("Shapes %s and %s are not compatible" % (X.shape,cf.weights.shape))
activity[r,c] = single_cf_fn(X,cf.weights)
activity *= strength
About 60% of the total run time is spent in this method, so if we were
able to optimize it, this would lead to good optimization of the
simulation in total. Looking further down the list, we can see
functions associated with learning, and that these account for about
half as much of the run time. So, optimizing the response function
will be approximately twice as beneficial as optimizing the learning
function in this case; only if it were much easier to optimize the learning
function would it be worthwhile to begin with that.
How do we begin to optimize the response function? We have more
fine-grained information about the occupation of the CPU while
executing the response function; the subsequent line in the output
shows that about 70% of the time spent running the response function
is spent in
import numpy.oldnumeric as Numeric
class DotProduct(ResponseFn):
"""
Return the sum of the element-by-element product of two 2D
arrays.
"""
def __call__(self,m1,m2):
# Should work even for non-contiguous arrays, e.g. with matrix
# slices or submatrices.
a = m1*m2
return Numeric.sum(a.ravel())
In this case, it seems strange that
from numpy import dot
class DotProduct(ResponseFn):
def __call__(self,m1,m2):
return dot(m1.ravel(),m2.ravel())
With this new DotProduct, we can profile the code again:
$ ./topographica examples/speed_test.ty -c "from topo.misc.util import profile; \
profile('topo.sim.run(200)',n=20)"
837056 function calls (828656 primitive calls) in 38.153 CPU seconds
Ordered by: cumulative time, internal time
List reduced from 109 to 20 due to restriction <20>
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 38.153 38.153
We can see from the above output that the time spent in If we wanted to proceed further with this particular optimization,
we note that although we have reduced the execution time of
import numpy
class CFPRF_Plugin(CFPResponseFn):
"""
Generic large-scale response function based on a simple single-CF function.
Applies the single_cf_fn to each CF in turn. For the default
single_cf_fn of DotProduct, does a basic dot product of each CF with the
corresponding slice of the input array. This function is likely
to be slow to run, but it is easy to extend with any arbitrary
single-CF response function.
The single_cf_fn must be a function f(X,W) that takes two
identically shaped matrices X (the input) and W (the
ConnectionField weights) and computes a scalar activation value
based on those weights.
"""
#single_cf_fn = ResponseFnParameter(DotProduct(),
# doc="Accepts a ResponseFn that will be applied to each CF individually.")
def __call__(self, cfs, input_activity, activity, strength):
rows,cols = activity.shape
single_cf_fn = numpy.dot
for r in xrange(rows):
for c in xrange(cols):
cf = cfs[r][c]
r1,r2,c1,c2 = cf.slice_array
X = input_activity[r1:r2,c1:c2]
#if (X.shape != cf.weights.shape):
# self.warning("Shapes %s and %s are not compatible" % (X.shape,cf.weights.shape))
activity[r,c] = single_cf_fn(X.ravel(),cf.weights.ravel())
activity *= strength
This leads to the following performance profile:
$ ./topographica speed_test.ty -c "from topo.misc.util import profile; \
profile('topo.sim.run(200)',n=20)"
516656 function calls (508256 primitive calls) in 35.410 CPU seconds
Ordered by: cumulative time, internal time
List reduced from 108 to 20 due to restriction <20>
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 35.410 35.410
This does reduce the total run time, but only slightly, to 93% of its previous value.
But Considering optimizations with C++ (weave)Topographica makes it reasonably easy to re-write functions in C++ and offer them as optimized alternatives. We might wonder if it would help in this case, or doesnumpy already do a good job? We
could replace DotProduct with a version written in
C++, or we could replace the entire CFPRF_Plugin class
with one written in C++. As at 02/2007, we find that simply re-writing
the single_cf_fn in C++ provides little performance improvement,
but that re-writing the entire CFP function provides a big performance
improvement.
Replacing the CFP function with one written entirely in C++, we get the following profile:
$ ./topographica speed_test.ty -c "from topo.misc.util import profile; \
profile('topo.sim.run(200)',n=20)"
515119 function calls (506917 primitive calls) in 22.492 CPU seconds
Ordered by: cumulative time, internal time
List reduced from 155 to 20 due to restriction <20>
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 22.492 22.492
The simulation now takes about half the time the original
version took, and 60% of the time the The C++ code adds extra work: for maintenance, for deployment on different platforms, and for user understanding --- so it has to be justified, meaning it should provide large speedups. In this case, the performance improvement justifies the additional costs (which have been substantial in terms of maintenance and platform support --- although platform support cost is diluted by all such C++ functions, and any added in the future). While making this kind of investigation, you should check that simulations run with different versions of a function are producing the same results. In particular, when working with optimized C++ functions, it is possible for one version to appear much faster than another when in fact the computations being performed are not equivalent. You could make a simple check by adding a print statement after profiling to show the sum of V1 activity, or some similar indicator. A final consideration is to ensure that the profile run times are long enough to obtain reliable results. For shorter runs, it would be necessary to repeat them to find a reasonable estimate of the minimum time. |
|