Re: [Caml-list] Comparison of OCaml and MLton for numerics

[skaller <skaller@users.sourceforge.net>]

On Fri, 2007-06-01 at 10:57 -0400, Brian Hurt wrote:
>  And the third case, where inlining opens up new 
> possibilities for optimization- that almost has to be done by the 
> compiler, as it depends upon what optimizations the compiler can, and 
> will, apply to the newly inlined function.  This is something I trust 
> the compiler to do more than I trust even me to do correctly.

It's NOT so easy to predict how much optimisation will result
from inlining. Just think about it, you have a tree of inlining
opportunities, if do you really want to attempt to estimate the
coefficients on N inlining choices just to decide if you'll
inline or not?

I doubt it. The compiler will make one guess whether to inline
or not based on a some fast heuristic, and then commit.

Felix inlines based on the number of statements in a function.
The default threshhold is 50. Inlining is done bottom up.
Recursive calls to children are inlined, others are not.
Tail-rec optimisation is done before each inlining operation.

Then, a monormorphisation pass is done, and the inlining
process repeated.

The HARD problem I haven't solved at all is how to improve
the recursive function inlining rule: since only recursive
calls to children are inlined, recursive calls to siblings
are not. This is really bad, because a self-tail-rec optimisation
might apply after a sibling inline, but the opportunity is lost
because I don't know how to safely inline siblings.

This sounds easy .. just inline until you spot a self call.

But it isn't easy, because that doesn't work. This is because
inlining a function requires 'cloning' all its children,
and a recursive call can be left as a call to the
original function .. so the call isn't recursive anymore.
Sibling inlining can then spew an infinite expansion.

Typeclasses make a real mess here: instances need to be kept
around until you're sure they're not needed, which in general
is after the post monomorphisation inlining phase, and, replacing
a 'virtual' with a concrete call messes up tracking of recursion
as well .. I'm not even sure my algorithm is safe in respect
of typeclass instantiation if the typeclass instance function
is recursive on the typeclass.


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