Tim Hochberg <tim.hochberg@cox.net> writes:

<pie-in-the-sky>

An idea that has popped up from time to time is delaying evalution of a complicated expressions so that the result can be computed more efficiently. For instance, the matrix expression:

a = b*c + d*e

results in the creation of two, potentially large, temporary matrices and also does a couple of extra loops at the C level than the equivalent expression implemented in C would.

The general idea has been to construct some sort of psuedo-object, when the numerical operations are indicated, then do the actual numerical operations at some later time. This would be very problematic if implemented for all arrays since it would quickly become impossible to figure out what was going on, particularly with view semantics. However, it could result in large performance improvements without becoming incomprehensible if implemented in small enough chunks.

A "straightforward" approach would look something like:

numpy.begin_defer() # Now all numpy operations (in this thread) are deferred a = b*c + d*e # 'a' is a special object that holds pointers to # 'b', 'c', 'd' and 'e' and knows what ops to perform. numpy.end_defer() # 'a' performs the operations and now looks like an array

Since 'a' knows the whole series of operations in advance it can perform them more efficiently than would be possible using the basic numpy machinery. Ideally, the space for 'a' could be allocated up front, and all of the operations could be done in a single loop. In practice the optimization might be somewhat less ambitious, depending on how much energy people put into this. However, this approach has some problems. One is the syntax, which clunky and a bit unsafe (a missing end_defer in a function could cause stuff to break very far away). The other is that I suspect that this sort of deferred evaluation makes multiple views of an array even more likely to bite the unwary.

This is a good idea; probably a bit difficult. I don't like the global defer context though. That could get messy, especially if you start calling functions.

The syntax issue can be cleanly addressed now that PEP 343 (the 'with' statement) is going into Python 2.5. Thus the above would look like:

with numpy.deferral(): a = b*c + d*e

Just removing the extra allocation of temporary variables can result in 30% speedup for this case[1], so the payoff would likely be large. On the down side, it could be quite a can of worms, and would likely require a lot of work to implement.

Alternatively, make some sort of expression type: ex = VirtualExpression() ex.a = ex.b * ex.c + ex.d * ex.e then, compute = ex.compile(a=(shape_of_a, dtype_of_a), etc.....) This could return a function that would look like def compute(b, c, d, e): a = empty(shape_of_a, dtype=dtype_of_a) multiply(b, c, a) # ok, I'm making this one up :-) fused_multiply_add(d, e, a) return a a = compute(b, c, d, e) Or, it could use some sort of numeric-specific bytecode that can be interpreted quickly in C. With some sort of optimizing compiler for that bytecode it could be really fun (it could use BLAS when appropriate, for instance!). or ... use weave :-) -- |>|\/|< /--------------------------------------------------------------------------\ |David M. Cooke http://arbutus.physics.mcmaster.ca/dmc/ |cookedm@physics.mcmaster.ca