pure functions and the parallel evaluation of reduce-like operations

[Doug Lea]

On 11/26/10 21:39, Jim Mayer wrote:
> In the recent debate on capturing mutable local variables the "reduce"
> function was used as an example application of functional programming,
> sometimes with an implication that the form could be evaluated in parallel.
>   It seems to me, though, that a parallel evaluation scheme is only
> applicable if the operator is associative (or, better, commutative and
> associative).

The applicability mainly depends on how deterministic you
require your program to be. For example, unless you use
"strictfp" (which I don't recall seeing recently in applications)
even sequential floating point calculations aren't necessary
replicable across platforms or runs, and parallel versions
would often require even more care or tolerance.
Also, performance-wise, there is almost nothing deterministic
about a given Java program, and potential parallelism is sure
to make performance estimation even harder.

It is an interesting empirical question how much less
determinism of both computations and performance
typical programs will tolerate.
(BTW, for some fun and extreme views of this, see
some of Martin Rinard's papers and talks. Although
google doesn't find any videos of them.)

-Doug