On Mon, 2006-09-04 at 12:56 -0700, Erick Tryzelaar wrote:
> skaller wrote:
> > the real problem is that the construction is loop
> > invariant .. but won't be lifted out of a loop
> > or recursion (unless you lift it manually).
> >
>
> What if we invert the "add" function for lists? Such as:
>
> fun add[T] (x:list[T], y:T):list[T] => Cons (x, y);
> noinline fun add[T] (x:T, y:list[T]):list[T] => rev$ Cons (y, rev x);
>
> This would then make this used the optimal path:
>
> Empty[int] + 4 + 3 + 2 + 1
This still doesn't fix the real problem:
while { something } {
val x = Empty[int] + 1 + 2 + 3 + 4;
blah x;
};
will needlessly construct x every pass: you can fix this
by manually lifting the invariant initialisation out
of the loop:
val x = Empty[int] + 1 + 2 + 3 + 4;
while { something } {
blah x;
};
Making the initialisation itself faster may be useful,
but it doesn't solve the real problem: Felix isn't
smart enough to recognize the list construction operators
are pure, the components are invariant, so the whole list
is invariant .. and even if it did it can't lift the
invariant out.
There is no serious** control flow analysis .. it doesn't
really even know the code is inside a loop.
So getting the technology for invariant code motion
optimisation implemented and working is probably more
important than optimising a specific data constructor.
** there is some 'micky mouse' analysis, but half
the cases it handles would probably be handled by
gcc anyhow.
At this stage, I don't consider this as important
as features, semantics, libraries, documentation etc.
The optimiser is complex, but it is fairly 'self-contained'
so various optimisations are well suited to 'student projects'
even if the algorithms are hard, and the Felix data structures
a bit messy to work with. If we have a few more compiler writers
one might take this on, but it isn't a 2 minute job :)
Maybe 2 months.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
Felix-language mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/felix-language
