Re: Realtime cost of call by value

[pkienzle]

On 5 Nov 2003 at 20:15, address@hidden wrote:
> I don't see how these "interpreter pragmas" would be more powerful;
> could you give an example? I guess I'm not following exactly what
> you're trying to say.

Yes, an example is in order.

How about:

        function x=sinh(x)
           x = (exp(x)-exp(-x))/2;
     end

I believe the current implementation of this function expands
to something like this as it walks the parse tree:

        # vectors: x
        t1 = exp(x)
        # vectors: x, t1
        t2 = -x 
        # vectors: x, t1, t2
        t3 = exp(t2)    
        # vectors: x, t1, t2, t3
        clear t2        
        # vectors: x, t1, t3
        t4 = t1 - t3    
        # vectors: x, t1, t3, t4
        clear t1 t3
        # vectors: x, t4
        t5 = t4/2
        # vectors: x, t4, t5
        clear t4
        # vectors: x, t5
        x = t5
        clear t5
        # vectors: x

This has a maximum of 4 copies of the data active.

In order to do better than that, we will need to rewrite the
octave internals so that rather than returning a new matrix,
each primitive takes a destination matrix in which it will
put its results.

Now with the appropriate cleverness, we can evaluate the
expression with only one extra copy:

        # vectors: x
        create empty t1 of size x
        # vectors: x, t1
        negate(x,t1)
        map(exp,t1,t1)
        map(exp,x,x)
        subtract(t1,x,x)
        clear t1
        # vectors: x
        divide(x,2,x)

With a slightly smart statement optimizer (one which walks
the RHS looking for exactly one occurrence of the LHS), we 
could write this as:

        t1 = exp(-x);
        x = (t1-exp(x))/2;

More cleverness would be required to handle the case where
the LHS occurs multiple times on the RHS.  Even more
cleverness would be required if we are looking inside
structures and cell arrays.  Even more cleverness would
be required if we are looking at slices of x.

Note that marking x as passed by reference will not help, 
unless the primitives we use are also pass by reference.  
If we want to reduce the number of temporary arrays created, 
we either need to  write a clever optimizer or give up on 
writing readable scripts.

So is it worth the effort?

Paul Kienzle
address@hidden



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------