Parallel Aggregations in PLINQ

re: Parallel Aggregations in PLINQ

Thomas Danecker — Thu, 24 Jan 2008 17:54:02 GMT

I don't understand why you're building the Aggregate method that complicated. If you make func a binary method of the form TAccumulate x TAccumulate -> TAccumulate, you're getting an algebraic structure.

So, (TAccumulate, func) has to be a commutative Monoid which implies all the properties you described.

This can be easily achieved by introducing a valueSelector: TSource -> TAccumulate.

You're getting the following method signature:

public static TResult Aggregate<TSource, TAccumulate, TResult>(

this IEnumerable<TSource> source,

Func<TSource, TAccumulate> valueSelector,

TAccumulate identityElement,

Func<TAccumulate, TAccumulate, TAccumulate> func,

Func<TAccumulate, TResult> resultSelector

)

{

TAccumulate accumulator = identityElement;

foreach (TSource elem in source)

{

accumulator = func(accumulator, valueSelector(elem));

}

return resultSelector(accumulator);

}

Now you can split up the source and compute thread-local accumulators and use also func(accumulator1, accumulator2) to combine them.

I do not like the fact to provide two different accumulator functions. It makes no sense either because the second method must be quasi the same as the first because of the nondeterminism (i.e. every value could be processed by a seperate thread).

With this version, you can implement the Aggregate method like a binary tree where the two childs are always independent from the other.

func(

valueSelector(elem0),

valueSelector(elem1))

func(

valueSelector(elem2),

valueSelector(elem3)))

The leaves of the tree are just calls to valueSelector(elem). In this tree you have always the option to run a child in an seperate thread.

re: Parallel Aggregations in PLINQ

igoro — Thu, 24 Jan 2008 23:07:38 GMT

Thanks for your suggestion, Thomas.

We have thought about the approach you are proposing previously. I agree that it is logically cleaner, and has all the desired algebraic properties. Unfortunately, it also comes with a price: an extra delegate invocation for each element in the input.

Another possible issue is that your proposed approach would rule out aggregations with mutable accumulators. For example, say that you have an aggregation over an IEnumerable<char>, and you want to compute how many times each letter (A-Z) appears. TAccumulate might be an integer array with 26 elements, representing the count of each letter. Value selector would have to return an array of 26 integers, so we'd end up constructing an array for each input element. On the other hand, a (TAccumulate, TElement)->TAccumulate reduce function could simply increment one element in the array, and return the same array.

Note that as of the CTP release, PLINQ does not support mutable accumulators, but it is an extension we are considering. We would need an overload where the user provides a seedConstructor delegate instead of a seed instance, so that we can have multiple independent accumulators.

So, that's my take on this issue. However, the Aggregate design is far from closed, and we are are open to consider other solutions.

Igor

re: Parallel Aggregations in PLINQ

David Callahan — Fri, 01 Feb 2008 00:07:39 GMT

Another issue with simply mapping TSource => TAccumator is that operation of combining TSource's may be singificantly cheaper than combining TAccumator's (think Maxtrix-matrix multiplication instead of matrix-vector multiplication).

A different use of a function mapping TSource->TAccumaultor is to avoid the change of "seed" to "identify". Seed is nice because it gives semantics to zero-length sequences. A mapping from source to accumulator can be used to handle sequences of lenght 1 and avoid the need for a separate zero element or change in semantics of the seed elelement.