Parallel.For, Parallel.ForEach and PLINQ

Counting the primes below 5,000,000 needed 353 ms of processor time in a for loop on the 18-processor computer these examples ran on, and 383 ms with Parallel.For, which spread the work over many processors and finished in 56 ms. A parallel loop does a little more work in all, and gets it done sooner.

You will spread loops and queries over threads, measure what that buys, and keep shared state from breaking them.

Parallel.For splits a loop’s iterations across threads

Parallel.For takes a range of integers and a body, runs the body for every number on several threads, and returns when all of them are done; Parallel.ForEach does the same for the items of any sequence. Both are data parallelismdata parallelism: Running the same operation on many pieces of data at the same time, each piece independent of the others, as Parallel.For, Parallel.ForEach and PLINQ do with the iterations of a loop or the items of a query.: the same operation on many pieces of data, each independent of the others. primes.cs counts the primes below 5,000,000 three ways, with a for loop, Parallel.For and PLINQ, keeping the fastest of five runs of each:

using System.Diagnostics;

// Count the primes below 5,000,000 three ways, five times each, and keep the fastest run of each: on a computer that
// is busy with other work, the fastest run is the one that other programs disturbed least. Each line also shows the
// processor time the run used, on all its threads together.
const int Limit = 5_000_000;
Console.WriteLine($"processors: {Environment.ProcessorCount}");

Run loop = Fastest(() =>
{
    int primes = 0;
    for (int n = 2; n < Limit; n++)
    {
        if (IsPrime(n))
        {
            primes++;
        }
    }

    return primes;
});

Run parallelFor = Fastest(() =>
{
    int primes = 0;
    Parallel.For(
        2,
        Limit,
        () => 0,                                         // localInit: each thread starts its own count at 0
        (n, _, local) => IsPrime(n) ? local + 1 : local, // the body updates only that thread's count
        local => Interlocked.Add(ref primes, local));    // localFinally: one shared addition per thread
    return primes;
});

Run plinq = Fastest(() => Enumerable.Range(2, Limit - 2).AsParallel().Count(IsPrime));

bool agree = loop.Count == parallelFor.Count && parallelFor.Count == plinq.Count;
Console.WriteLine($"primes below {Limit:N0}: {loop.Count:N0}; all three agree: {agree}");
Console.WriteLine($"{"",-28}{"wall time",10}{"processor time",16}");
Console.WriteLine($"{"for loop:",-28}{loop.WallMs,7:F0} ms{loop.CpuMs,13:F0} ms");
Console.WriteLine($"{"Parallel.For, local counts:",-28}{parallelFor.WallMs,7:F0} ms{parallelFor.CpuMs,13:F0} ms   {loop.WallMs / parallelFor.WallMs:F1}x faster");
Console.WriteLine($"{"PLINQ AsParallel().Count:",-28}{plinq.WallMs,7:F0} ms{plinq.CpuMs,13:F0} ms   {loop.WallMs / plinq.WallMs:F1}x faster");

static bool IsPrime(int n)
{
    if (n < 2)
    {
        return false;
    }

    if (n % 2 == 0)
    {
        return n == 2;
    }

    for (int d = 3; d * d <= n; d += 2)
    {
        if (n % d == 0)
        {
            return false;
        }
    }

    return true;
}

static Run Fastest(Func<int> work)
{
    work(); // a first run that is not timed: the code is compiled and the thread pool has its threads
    Run best = new(0, double.MaxValue, 0);
    Process self = Process.GetCurrentProcess();
    for (int i = 0; i < 5; i++)
    {
        self.Refresh();
        TimeSpan cpuBefore = self.TotalProcessorTime;
        var watch = Stopwatch.StartNew();
        int count = work();
        double wall = watch.Elapsed.TotalMilliseconds;
        self.Refresh();
        double cpu = (self.TotalProcessorTime - cpuBefore).TotalMilliseconds;
        if (wall < best.WallMs)
        {
            best = new Run(count, wall, cpu);
        }
    }

    return best;
}

record Run(int Count, double WallMs, double CpuMs);

processors: 18
primes below 5,000,000: 348,513; all three agree: True
                             wall time  processor time
for loop:                      1032 ms          353 ms
Parallel.For, local counts:      56 ms          383 ms   18.4x faster
PLINQ AsParallel().Count:       116 ms          447 ms   8.9x faster

All three found 348,513 primes. By the clock, Parallel.For was 18.4 times faster and PLINQ 8.9 times, but that flatters them: the loop, on one thread, had a processor for only 353 of its 1,032 ms, and other programs had it for the rest. The parallel versions used a little more processor time, 383 and 447 ms, to hand out the work and join the threads, and finished sooner by using many processors at once. Each thread counts its own primes and adds its count to the total once, at the end. Step through the stages of that call:

The overload with localInit and localFinally is the pattern for any total: start a value per thread, update it in the body without a lock, and combine the values once per thread, as Microsoft’s example of a loop with thread-local variables does. ParallelOptions adds a MaxDegreeOfParallelism and a cancellation token.

PLINQ runs a LINQ query in parallel, in whatever order it finishes

PLINQ is LINQ with one more call: AsParallel() on the source makes the rest of the query run on several threads, by splitting the source into partitions and merging their results. order.cs finds the primes below 200,000 with LINQ, with PLINQ and with PLINQ and AsOrdered, then throws an exception from inside a query:

// The primes below 200,000, found by LINQ, by PLINQ and by PLINQ with AsOrdered.
int[] numbers = [.. Enumerable.Range(2, 199_998)];

List<int> linq = [.. numbers.Where(IsPrime)];
List<int> plinq = [.. numbers.AsParallel().Where(IsPrime)];
List<int> ordered = [.. numbers.AsParallel().AsOrdered().Where(IsPrime)];

Console.WriteLine($"LINQ:                {linq.Count:N0} primes, first five {string.Join(", ", linq.Take(5))}");
Console.WriteLine($"PLINQ:               same primes: {plinq.Order().SequenceEqual(linq)}, same order: {plinq.SequenceEqual(linq)}");
Console.WriteLine($"PLINQ with AsOrdered: same primes: {ordered.Order().SequenceEqual(linq)}, same order: {ordered.SequenceEqual(linq)}");

// An exception thrown inside a PLINQ query reaches the caller inside an AggregateException.
try
{
    int largest = numbers.AsParallel().Select(n => n == 150_000 ? throw new InvalidDataException($"no price for item {n}") : n).Max();
    Console.WriteLine(largest);
}
catch (AggregateException e)
{
    string kinds = string.Join(", ", e.InnerExceptions.Select(inner => $"{inner.GetType().Name} ({inner.Message})"));
    Console.WriteLine($"{e.GetType().Name} holding: {kinds}");
}

static bool IsPrime(int n)
{
    if (n % 2 == 0)
    {
        return n == 2;
    }

    for (int d = 3; d * d <= n; d += 2)
    {
        if (n % d == 0)
        {
            return false;
        }
    }

    return true;
}

LINQ:                17,984 primes, first five 2, 3, 5, 7, 11
PLINQ:               same primes: True, same order: False
PLINQ with AsOrdered: same primes: True, same order: True
AggregateException holding: InvalidDataException (no price for item 150000)

PLINQ found the same 17,984 primes as LINQ, in another order: results come back as the partitions produce them. AsOrdered() restored the source order, which Microsoft’s introduction to PLINQ says usually costs extra work, because the results are buffered and sorted. The exception arrived inside an AggregateException, because several threads may fail at once. PLINQ also decides for itself: some shapes of query run on one thread unless WithExecutionMode(ParallelExecutionMode.ForceParallelism) says otherwise. A foreach over a query merges every result back onto the thread that runs the loop; query.ForAll(save) skips that merge and runs save on the query’s threads, in no order, so save must be safe to call from several threads at once. The three, side by side:

Two ideas explain how far a parallel loop can go. Amdahl’s lawAmdahl's law: The rule that the part of a program that cannot run in parallel limits its speed-up, however many processors are added: the serial part takes as long on many processors as on one. says how much the serial part of a program limits its speed-up. Partitioningpartitioning: How a parallel loop or query splits its input among its threads: in fixed ranges decided at the start, or in chunks handed to whichever thread asks next, which evens out work of uneven cost. is how a parallel loop splits its input among its threads, in fixed ranges or in chunks handed out on demand.

Measured speed-up, Amdahl's law and partitioning Pro: opens with a Pro, Premium or Ultimate pass

Shared-state bugs reproduced, and work too small to share Pro: opens with a Pro, Premium or Ultimate pass

A lab: a grayscale filter that must match byte for byte Pro: opens with a Pro, Premium or Ultimate pass

Practise

The self-check covers the first two sections, and begins with the idea your answers so far found hardest:

Interview questions

Fresher · When does Parallel.For make a loop slower?

When each iteration does too little work. Parallel.For has a cost of its own: it splits the range into chunks, hands them to threads, and joins the threads at the end. If the body is a few operations, that cost is larger than the work, and the plain loop wins; Microsoft’s guide to the pitfalls says loops with few iterations and fast bodies are unlikely to speed up, and to measure. It is also slower when the iterations share state that needs a lock or an Interlocked call each time, because the threads then queue for it, and when the body calls something that serialises them, such as Console.WriteLine. Parallel loops pay for independent work that costs much more than handing it out.

Key takeaways

• Parallel.For runs a body for every number of a range on several threads, and Parallel.ForEach does the same for a sequence; both return when every iteration is done.
• Keep a value per thread with localInit and localFinally, and combine the values once per thread, instead of sharing a total in the body.
• PLINQ runs a query in parallel with AsParallel(), returns results in no particular order unless AsOrdered() is used, and reports failures in an AggregateException.
• Parallel loops are for CPU-bound work; work that waits for I/O belongs to Parallel.ForEachAsync or Task.WhenAll.