Re: anonymous functions optimization - wanted for 3.4.0?

[Jake]

Opinions?  Great work.  Probably 90% of my work in Octave is done using 
anonymous functions because I don't like bothering with separate m files unless 
I have to (uni requires separate m files for function definitions).  This is 
perfect.

-Jake

On Fri, 10 Sep 2010 11:52:44 +0200
Jaroslav Hajek <address@hidden> wrote:

> 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


-- 
Jake <address@hidden>