PLINQ Queries That Run in Parallel in .NET 4.5

Igor Ostrovsky - MSFT

November 10th, 20110 0

One interesting thing to know about PLINQ is that not all queries are guaranteed to execute in parallel (See PLINQ Queries That Run Sequentially for reference). You can think of the AsParallel method as a hint to run in parallel for query shapes that it believes will be faster. By default, PLINQ prefers to use a simple sequential algorithm over a potentially expensive parallel algorithm, and so some queries will execute sequentially, especially queries where the chain of operators do not lend themselves to parallelism. The bottom line is that PLINQ’s intent is to run your queries as fast as possible, so if there’s a good likelihood that the complexities of parallelism will slow it down, PLINQ will perform the query sequentially rather than in parallel.

In .NET 4.5, PLINQ’s algorithms have improved over .NET 4 such that its set of parallelizable queries has broadened and substantially fewer queries fall back to sequential execution. For example, the following query would execute sequentially in .NET 4 but now executes in parallel in .NET 4.5:

intArray.AsParallel()
    .Select(x => Foo(x))
    .TakeWhile(x => Filter(x))
    .ToArray();

Since the query executes sequentially in .NET 4, the query would not get any speedup even if the Foo() method is expensive. For some cases, the choice to fallback to a sequential implementation might be too conservative, and as a developer you might choose to override it. In order to force PLINQ to use a parallel algorithm in .NET 4, the user can call the WithExecutionMode operator:

intArray.AsParallel()
    .WithExecutionMode(ParallelExecutionMode.ForceParallelism)
    .Select(x => Foo(x))
    .TakeWhile(x => Filter(x))
    .ToArray();

In .NET 4.5, the behavior of the TakeWhile operator has changed, and so the query executes in parallel even without the WithExecutionMode hint.

Sequential Fallback in .NET 4 and .NET 4.5

One way to illustrate the improvements to the sequential fallback is to look at the list of operators that may cause the query to fallback to sequential. Whether or not the operator actually causes a sequential fallback depends on other operators in the query as well.

Operators that may cause sequential fallback in both .NET 4 and .NET 4.5 are marked in blue, and operators that may cause fallback in .NET 4 but no longer in .NET 4.5 are marked in orange.

So, in .NET 4.5, as long as the query does not contain positional operators or the ElementAt operator, it will not fall back to sequential.

The positional operators mentioned above are the operator overloads that pass the position of each element into the user delegate. So, while the ‘ordinary’ Select operator accepts a delegate of type Func<TInput, TOutput>, the positional Select accepts a delegate of type Func<TInput, int, TOutput>. The position of each element is passed into the delegate as the input second parameter.

The ForceParallelism execution mode is still available for those items called out above.

Potential Risks of the Change

The fact that some queries used to execute sequentially and now execute in parallel opens up the possibility of exposing more latent race conditions in users’ code.

Here is an example of a query that happens to work in .NET 4, but will not work in .NET 4.5:

List<int> list = new List<int>();
var q = src.AsParallel()
    .Select(x => { list.Add(x); return x; })
    .Where(x => true)
    .Take(100);

There is a bug in the query above: the delegate passed into the Select operator is not thread-safe. However, the query will still happen to work in .NET 4, because as an implementation detail PLINQ decides to execute the query sequentially. In .NET 4.5, the query will run in parallel, and so list.Add(x) could be called from multiple threads concurrently, potentially resulting in a corrupted List<T> instance.

However, the idea that user delegates may be called from multiple cores is a core premise of PLINQ, so hopefully no user code in the real world will be broken by the change.

Related Resources:

PLINQ Queries That Run Sequentially

MSDN Documentation for ParallelExecutionMode Enumeration

How to: Specify the Execution Mode in PLINQ

Understanding Speedup in PLINQ