Reducer interface

[Doug Lea]

On 09/17/11 19:43, Neal Gafter wrote:
> The operation this library calls "reduce" is more properly named "left fold"

I think the properness depends on whether you are in the data-parallel
vs functional-programming community :-)

> and, unless you can exploit algebraic properties of the function, is
> inherently sequential.

These reduction methods should indeed have specs saying that
results are are combined left-associatively.
Users can then decide whether this makes sense for their
application. I say it in this way because some functions
(like most involving floating point operations) are not
strictly associative but the results may be acceptable.

>
> When the element and output types are the same, and the function is known to
> be associative, you can use "parallel prefix" to compute the result in O(log
> n) time using O(n/log n) processors.

(Although in practice, parallel-prefix usually only starts
winning when you have more than about 8 cores.)

>
> On Sat, Sep 17, 2011 at 2:54 PM, Kasper Nielsen<kasperni at gmail.com>  wrote:
>
>> Hi,
>>
>> Can somebody explain to me how the Reducer interface works in a parallel
>> setting?
>> I'm using something like E reduce(E a, E b) myself.
>> And I fail to understand how you can use two different parameter types
>> unless you force all usage to be serial (non-parallel) application of
>> elements.

The flexibility in first argument type sometimes allows you
to do a map step in conjunction with reduce. Not often, but
still, there is no reason to preclude it.

-Doug