Parallel LINQ
Adding more cores to PC microprocessors has become the preferred approach to increasing CPU
performance while minimizing incremental power consumption and thermal radiation. Prior to the
advent of multi - core processors, increasing clock speed was the only method of improving performance
of a specific CPU design. Decreasing the lithographic line width mitigates the increase in thermal
radiation as clock speed increases at the expense of building new CPU fabrication (fab) lines and plants.
Intel ’ s new 45 - nanometer (nm) process (code - named Penryn) supports up to 800 million transistors on a
single chip. Intel ’ s planning clock speeds of 3 GHz and greater for dual - core Penryn chips used in
desktop PC desktops and servers, but going below 45 nm and above 3 GHz will be extremely costly
compared with putting two Penryn chips in a package to create quad - core packages that share a 12 - MB
or larger Level 2 cache.
Operating systems and server applications, such as SQL Server 2000+, Windows Server 2003+, and
others, are designed to take advantage of multiple CPUs, whether in individual packages or on a
single die. Windows Vista accommodates quad - core CPUs but most client - side applications, written by
in - house developers or independent software vendors, aren ’ t designed to take full advantage of even
dual - core CPUs. Sophisticated multi - threaded applications aren ’ t easy to write or simple to test
thoroughly.
Parallel LINQ (PLINQ) is a component of the Microsoft Parallel Extensions to .NET Framework 3.5,
which in turn is part of the Microsoft Parallel Computing Initiative (PCI). The object of the PCI is to take
better advantage of multiple - core processors by taking the pain out of parallel (concurrent) processing of
LINQ to Objects, LINQ to XML, and LINQ to DataSet queries. PLINQ is less applicable to LINQ to SQL
and LINQ to Entities queries because queries are processed primarily by database servers. However,
PLINQ can speed processing heterogeneous queries with sequences from relational domains. PLINQ
parallelizes queries by relatively simple modifications to LINQ expression (comprehension) syntax and
only slightly more cumbersome modifications of method call syntax. LINQ ’ s declarative programming
methodology, which describes the result that ’ s wanted instead of how to accomplish the result, gives
PLINQ the flexibility to accomplish its objectives without resorting to complex programming structures.
The starting point for additional information on PLINQ and the Parallel Extensions is the Microsoft ’ s
Parallel Computing Center ( http://msdn.microsoft.com/en - us/concurrency/default
.aspx ). The Parallel Extensions also contain the Task Parallel Library (TPL) and a hidden
implementation of the Coordination Data Structures (CDS), which are beyond the scope of this
chapter ’ s declarative LINQ programming. The June 2008 CTP includes CDS documentation.
Programming with PLINQ
Using PLINQ with a project requires the following three operations:
1. Download and run the Microsoft Parallel Extensions to .NET Framework 3.5, June 2008 (or later)
Community Technology Preview. (Search for “ Microsoft Parallel Extensions ” with the quotation
marks.)
2. Add a reference to System.Threading.dll to add the System.Threading namespace to your
project.
3. Add using System.Threading; or Imports System.Threading to your classes that contain
LINQ queries.
4. Replace the Standard Query Operator ’ s IEnumerable < T > type for sequences with
System.Linq.ParallelEnumerable < T > by calling the System.Linq.ParallelEnumerable
.AsParallel < T > extension method. AsParallel and AsParallel < T > appear in IntelliSense ’ s
AutoComplete list between AsEnumerable < T > and AsQuerable .
The System.Threading namespace extends System.Linq with the following two namespaces to
implement PLINQ:
System.Linq extends .NET 3.5 ’ s System.Linq namespace with IParallelEnumerable < T >
and IParallelOrderedEnumerable < T > interfaces and ParallelEnmerable ,
ParallelQuery and ParallelQueryOptions classes. ParallelEnumerable provides the
SQO parallel processing extension methods. ParallelQuery provides the AsParallel() ,
AsParallel < T > () , and AsSequential < T > () methods. ParallelQueryOptions supports the
PreserveOrdering option to force parallel processing of the output sequence to following
the input sequence and the integer DegreeOfParallelism argument that specifies the
maximum number of threads. System.Linq also includes a number of related internal
sealed / Friend NotInheritable classes.
System.Linq.Parallel adds the Parallel namespace with an Enumable class of extension
methods and a large number of internal sealed / Friend NotInheritable helper classes.
Add the \Program Files\Microsoft Parallel Extensions Jun08 CTP\System
.Threading.dll file to Lutz Roeder ’ s Reflector application if you want to explore the classes in
detail. Note that Jun08 might have changed to a later date.
The IParallelEnumerable < T > interface derives from IEnumerable < T > and adds only the overhead
needed to enable binding to PLINQ ’ s ParallelEnumerable query provider. Here ’ s the basic syntax for
LINQ expression and method call syntax with the PreserveOrdering option and four threads maximum
specified:
C# 3.0
// Sequential (standard) query - method call syntax (C#)
var query = dataSource
[.Where(a = > a. Prop1Name == someValue )
.Orderby(a = > a. Prop2Name )
.Select(a)];
foreach (var a in query)
{
// Do something with a
}
// Parallel (pipelined) query - method call syntax
var query = dataSource
.AsParallel([QueryOptions.PreserveOrdering[, 4]])
[.Where(a = > a. Prop1Name == someValue )
.Orderby(a = > a. Prop2Name )
.Select(a)];
foreach (var a in query)
{
// Do something with a
}
// Parallel (pipelined) query - query expression syntax
var query = for a in dataSource.AsParallel([QueryOptions.PreserveOrdering[, 4]])
[where a. Prop1Name == someValue
orderby a. Prop2Name ]
select a;
foreach (var a in query)
{
// Do something with a
}
Processing Queries
PLINQ offers the following three query processing options:
Pipelined processing uses n - 1 threads to run the parallel query and one thread to enumerate
the query, where n is the number of processor cores in the machine. This method ensures
that the foreach / For Each...Next loop can process elements as they exit parallel processing,
which minimizes memory consumption for temporary storage of elements. When the
enumerator thread invokes MoveNext() method, the processing thread(s) deliver a result as
quickly as possible; the enumerator thread blocks until a result is available. Pipelined processing
is the default unless you invoke the ToArray() , ToDictionary() , ToList() , or ToLookup()
method or include the OrderBy() or OrderByDescending() SQO in your query. Pipelined
processing uses the basic query syntax shown in the preceding examples.
Stop - and - go processing starts with a call to MoveNext() . The enumerator thread then enlists
threads from the remaining cores to complete parallel query processing. This method stores
elements in memory; the first thread enumerates the output and the subsequent MoveNext()
invocation when parallel query processing completes returns the entire output. Additional
MoveNext() invocations return the same data from the buffer. You select stop - and - go
processing by invoking PLINQ ’ s GetEnumerator( pipelined ) overload with pipelined =
false . Stop - and - go processing is used for To...() methods and queries sorted with
OrderBy[Descending]() because these operators force all - at - once processing. Stop - and - go
processing uses the iteration syntax shown in the following example.
Inverted enumeration requires supplying a lambda function to run in parallel one time for each
element. Inverted enumeration doesn ’ t incur the overhead of merging the output from multiple
threads. Inverted enumeration requires substituting the ForAll API for foreach / For Each...
Next and the lambdas cannot share state. The later “ Ray Tracing ” section has an example of
inverted enumeration with the ForAll API.
C# 3.0
// Enumeration with stop-and-go processing (C#)
using (var q = query.GetEnumerator(false))
{
while (q.MoveNext())
{
// the first invocation starts query processing
// then enumerate the results with
operationOn(q.Current);
}
}
