I am looking at the tuple unravelling problem. This is related
to the standard deforestation problem (only hopefully easier).

Rougly, it goes like this: given definitions like:

typedef vec = array[double,3];

fun add(x:vec,y:vec)=>x.(0)+y.(0), x.(1)+y.(1), x.(2)+y.(2);
fun sub(x:vec,y:vec)=>x.(0)-y.(0), x.(1)-y.(1), x.(2)-y.(2);
fun neg(x:vec)=>-x.(0), -x.(1),-x.(2);
fun mul(x:vec,var y:double)=>x.(0)*y, x.(1)*y, x.(2)*y;
fun div(x:vec,var y:double)=>x.(0)/y, x.(1)/y, x.(2)/y;
fun mul(var y:double,x:vec)=>x.(0)*y, x.(1)*y, x.(2)*y;
fun sqr(x:vec)=>x.(0)*x.(0)+x.(1)*x.(1)+x.(2)*x.(2);
fun norm(x:vec)=>sqrt(sqr x);

and calculations like:

        x = a + b * c / d + e ...

an optimised calculation would roughly be:

        for i = 0 to 2 do:
                x[i] = a[i] + ...

i.e. 3 separate calculations, one for each component
of the assignment target.

However the code is written so that, for example,
the add function returns a tuple which is constructed.
When used as an argument, components are extracted.

With eager inlining, one temporary tuple is created.
With lazy inlining, the tuple is create 3 times, once
for each extractor:

        add(x,add (y,z)) => 
                result.[0] = x.[0] + add(y,z).[0]
                ...

In the functions above, the choice of lazy or eager is
encouraged by using 'var' for eager evaluation.

Optimising this is decidedly non-trivial!

if we use lazy inlining, plus the rule

        (x,_,).[0] = x

any sequence of 'add' operations can be split into 3 coordinate
strands. This still involves temporaries, but probably machine
registers if the arguments are integers, whereas the eager approach
uses triples. (Actually, gcc does a fairly good job with -O3 of
unravelling this).

Still, in the nbody problem Felix is 5 times slower than C,
which is almost certainly due to constructing and deconstructing
tuples at every step.

The choice between lazy and eager can probably be made on the basis
of whether 'unravelling' is possible.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

-------------------------------------------------------------------------
This SF.net email is sponsored by: Splunk Inc.
Still grepping through log files to find problems?  Stop.
Now Search log events and configuration files using AJAX and a browser.
Download your FREE copy of Splunk now >>  http://get.splunk.com/
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language

Reply via email to