anonymous functions optimization - wanted for 3.4.0?

[Jaroslav Hajek]

hi all,

attached is a patch that implements an interesting (IMHO) optimization
of anonymous function handles. First a bit of theory:
A number of anonymous function handles looks like this:

h = @(par1, par2, ...) some_func (arg1, arg2, ....)

where each argi is either a reference to some parj, or a constant, or
a variable defined in the calling context. Such a function
is called a "binder" because it merely takes some other function or
handle and binds some of its parameters to certain values.
Callback functions are often binders.

Examples:

@(x) size (x, 3)
@(x, y) my_func (x, my_data, y)

The attached patch optimizes calls to binders. When Octave constructs
an anonymous handle, it attempts to detect if it's a binder. If so, it
augments the handle with information how to transform the argument
list and the "root" function's handle (or value). It then overrides
the call sequence with a fast code that transforms the argument list
and calls the root function. This eliminates the overhead of setting
up an m-function, altering the call stack, and interpreting the
function's body, making binders only incur small additive penalty to
the root function's cost.

The attached benchmark is for illustratory purposes:

a = num2cell (rand (3,3,100000), [1, 2]);
try
  cellfun(); # preload
end_try_catch

tic; cellfun (@(x) sum (x, 2), a, "uniformoutput", false); toc # method 1
tic; cellfun (@sum, a, {2}, "uniformoutput", false); toc # method 2


first, a cell array of 100000 3x3 matrices is constructed. Then
cellfun is invoked to compute the row sum of each matrix.
Method 1 is the standard, Matlab-compatible way to do it. Method 2
uses a special feature of Octave's cellfun, which is able
to auto-expand singleton cells (and was implemented for this reason as well).

With recent tip, octave at g++ -O3 -march=native, Core 2 Duo @ 2.83 GHz, I get:

address@hidden:~/devel/octave/main> octave -q ttfh.m
Elapsed time is 1.08111 seconds.
Elapsed time is 0.145191 seconds.

i.e. method 1 is more than 7x slower than method 2. With the new
patch, I'm getting:

address@hidden:~/devel/octave/main> ./run-octave -q ttfh.m
Elapsed time is 0.127787 seconds.
Elapsed time is 0.129777 seconds.

i.e. both approaches are essentially equally fast.

Random remarks:
1. If root is a function name, a handle to that function is
constructed. Because handles don't work with legacy dispatch, the
optimization will be disabled if the function name has legacy dispatch
overloads.
2. Root can also be a defined value, in which case it is simply
reused. Most often this will mean another function handle, but it may
be a matrix as well.
3. Each bound argument must be either a defined variable or a
constant. Something like @(x) size (x, k+1) won't work (i.e. won't be
optimized), because Octave will not attempt
to make sure that the expression has no side effects.

The question for today is: is this optimization wanted in Octave
3.4.x? Although make check is OK, it may still have introduced nasty
hidden bugs, because it touches a sensitive area. Or, for that matter,
is it wanted at all? I know that some people (e.g. David Bateman)
often write @(x) func(x) in place of @func and so may be happy to see
that most of the penalty incurred by this practice will be eliminated
:)
Personally, I vote for including it even in 3.4.0, but I won't fight
hard for it.

And finally, I have no idea whatsoever whether this infringes on any
patents. But you knew that :)

Opinions?

regards

-- 
RNDr. Jaroslav Hajek, PhD
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz

binders.diff
Description: Text Data