On Tue, 2007-10-02 at 22:15 +0100, David Allsopp wrote:
> > A little weird to see such inherently functional construct as fold
> implemented imperatively. But it's fine with me, as long as it does the job.
> I
> > wonder, though, how would the performance of a line counter based on your
> code compare with the one suggested by Brian. 
> 
> It's faster, though only slightly - I was going to post an imperative
> solution earlier, too. Even in Ocaml, a recursive call (tail or otherwise)
> has some costs not present in a simple loop. However, I don't agree that
> it's more natural - "ugly" is more the word I'd use!

In Felix, tail-rec calls are generally faster than loops.
The reason is that the compiler is better able to reason
about the semantics and so it can do better optimisations.
OTOH loops degenerate to conditional goto-spaghetti and
would require SSA analysis to recover.

For example, given:

	fun f(x,y) ... f (a,b)

the implementation generates

	var x,y; 
	set_initial_values(x,y);
	start:
		...
		paropt x,y = a,b;
		goto start;

where 'paropt' serialises the parallel assignment
using an optimisation algorithm which tries to minimise
the number of assignments and temporaries used.

this has a significant impact on performance .. Felix version
of Ackermann's function is more then 2.5x faster than Ocamlopt,
and almost 2x faster than C. Ackermann has 2 tail-rec calls.

Trying to do this with loops is much harder because, unlike
the tail-rec formulation, the 'inputs' and 'outputs' connected
by the loops are not explicit, as they are when a function
is used and parameters and arguments define the input/output
relationship (and everything else local is a temporary with no
persistence: Felix doesn't not allow functions to have side
effects, so only local data is mutable).

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