Parallel For Loops over Non-Integral Types

Stephen Toub - MSFT

In a previous post, it was demonstrated how for loops with very small loop bodies could be parallelized by creating an iterator over ranges, and then using Parallel.ForEach over those ranges.  A similar technique can be used to write parallel loops over iteration spaces of non-integers.  For example, let’s say I wanted to parallelize the following loop, where the iteration range is based on doubles:

for(double d = 0.0; d < 1.0; d += .001)
{
    Process(d);
}

Parallel.For only contains overloads for where the iteration variable is an Int32 or an Int64.  To accomodate doubles, one approach would be to translate the range into an integer-based range in order to use Parallel.For, and then within the body of the loop translate it into a double.  As an example, the previously shown loop could be rewritten as:

Parallel.For(0, 1000, i =>
{
    double d = i / 1000.0;
    Process(d);
});

Due to floating point arithmetic, this may not be exactly the same, but it may be close enough.  Another approach is to implement an iterator like the following:

private static IEnumerable<double> Iterate(
    double fromInclusive, double toExclusive, double step)
{
    for(double d = fromInclusive; d < toExclusive; d += step) yield return d;
}

With that Iterate method, now I can parallelize the sequential loop using Parallel.ForEach:

Parallel.ForEach(Iterate(0.0, 1.0, .001), d =>
{
    Process(d);
});

This same technique can be applied to a wide variety of scenarios.  Keep in mind, however, that the IEnumerator<T> interface isn’t thread-safe, which means that Parallel.ForEach needs to take locks when accessing the data source. While ForEach internally uses some smarts to try to ammortize the cost of such locks over the processing, this is still overhead that needs to be overcome by more work in the body of the ForEach in order for good speedups to be achieved. 

Parallel.ForEach has optimizations used when working on indexible data sources, such as lists and arrays, and in those cases the need for locking is decreased.  Thus, performance may actually be improved in some cases by transforming the iteration space into a list or an array, which can be done using LINQ, even though there is both time and memory cost associated with creating an array from an enumerable. For example:

Parallel.ForEach(Iterate(0.0, 1.0, .001).ToArray(), d =>
{
    Process(d);
});

Happy coding.

0 comments

Discussion is closed.

Feedback usabilla icon