Re: [Caml-list] Re: Ant: Efficiency of let/and

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

On Mon, 2005-09-26 at 12:05 -0400, Stefan Monnier wrote:
> > Syntactically and semantically there is no difference.  I was wondering if
> > the ocamlopt compiler took advatange of the implicit paralellism at all.
> 
> If someone tries to use such things as `and' or
> unspecified-argument-evaluation-order in the hopes that the compiler will
> extract some imagined parallelism is simply deluding himself.
> In some cases, the freedom to execute in any order does lead to better
> code, but that code rarely if ever uses any kind of parallelism.

This is not so at all. Limited Parallelism is indeed found in all 
modern processors, which can, for example, distribute multiple
instructions on several pipelines, decode in parallel with
computing values, or perform several integer and/or floating
operations simultaneously.

In fact, as far back as 197x, the Cyber 70 could do this,
in fact it relied on it. In particular, register calculations
and memory fetches and stores we always done in parallel,
automatically, until a join point. When you did a load,
for example, the next instruction would be executed
immediately, without waiting for the load to complete,
provided it didn't use the register being loaded
(and I think .. it would then proceed to the next instruction,
and execute THAT whilst suspending the previous one, provided
it used distinct registers .. but I'm not sure).

It may well be that this has no impact on Ocaml code.
However it certainly DOES have an impact on low level C code.

In addition, parallel assignment is a major benefit,
not because the assignments are done concurrently,
but because it can save memory. For example:

	x,y = 1,2

cf

	x,y = y,x

The first pair of assignments is faster and uses no temporaries,
the second requires a temporary. So an arbitrary parallel
assignment can, in fact, be optimised to reduce the number
of temporaries used, and thus the number of operations.

Parallel assignments as written aren't that useful, however
there is a particular optimisation of great benefit
which is requires parallel assignment: self-tail-recursion.

In this case, the assignment arises through reusing the
same closure, and the optimisation is of the form:

	x,y,x = f(x,y,z), g(x,y,z), h(x,y,x)
	goto start

In particular, the argument of the new invocation can
depend on the argument of the old invocation, and,
in tuple form the assignment would, without analysis,
require a temporary the size of the argument:

	tmp = f(x,y,z), g(x,y,z), h(x,y,z)
	x,y,z = tmp

Which, in the worst case, *doubles* the number
of assignments, and thus the cost of looping --
in a tight inner loop this can be critical.

In a language like Ocaml, a parallel operation can have
a major performance advantage, because it explicitly
indicates to the compiler that the order of evaluation
is irrelevant: due to side-effects and separate compilation,
the order of evaluation of sequential assignments is likely
to be fixed, and therefore cannot be optimised.

I do not know whether Ocaml does parallel assignment
optimisations on self-tail recursions .. but I can
tell you that Felix DOES. Perhaps this is why it
calculates Ackermann's function faster than Ocaml and C?
[I have no idea of the real reason .. but it does]

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