Re: inlining tail-recursive functions (Re: [Caml-list] O'Caml vs C++: a little benchmark)

[John Max Skaller <skaller@ozemail.com.au>]

Oleg wrote:

> On Wednesday 28 August 2002 09:47 am, John Max Skaller wrote:
> 
>>> BTW does O'Caml inline tail-recursive functions?
>>>
>>Do you mean loop unrolling? I hear that it doesn't
>>do loop unrolling. [There's nothing to gain from
>>a simple inlining, unless the loop is only executed
>>once or twice - you'd only save a single function call]
>>
> 
> It's been mentioned that O'Caml can inline functions that are not recursive 
> (including inlining across module boundaries). Tail-recursive functions can 
> be, basically, transformed into non-recursive functions by the compiler. So I 
> was wondering if O'Caml inlined them. The benefits of inlining tail-recursive 
> functions should thus be the same as the benefits of inlining non-recursive 
> functions.


I don't think so. For a tail rec function transformed into
a loop, there is little difference between inlining
the loop, or just doing a standard call to a
function containing the loop .. assuming functional
code, and assuming the loop is executed many times.

If the loop is very short, there may be some advantage
in unrolling it.

The difference would only be a single function call,

which has negligible cost compared to a large number
of loop iterations.

There *might* be a small architectural advantage
inlining the loop, if that tends to localise
all the variables (more efficient caching of
memory blocks). This happens to be the case
in my Felix compiler, where a reference to a variable
from another function costs an extra indirection,
and probably requires two pages of virtual
memory instead of the one page and no indirection
required if the loop were inlined.

But Ocaml doesn't work the way Felix does, so I doubt
there would be any advantage (all values are separately
heap allocated anyhow, which is not true in Felix,
which uses 'frames' to reduce heap allocations]

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners